14
\$\begingroup\$

Background

A Ruth-Aaron pair is a pair of consecutive positive integers n and n+1 such that the sum of the prime factors (counting repeated prime factors) of each integer are equal. For example, (714,715) is a Ruth-Aaron pair, since 714=2*3*7*17, 715=5*11*13, and 2+3+7+17=5+11+13=29. The name Ruth-Aaron pair was chosen by Carl Pomerance in reference to Babe Ruth's career home run total of 714, which stood as the world record from May 25, 1935 until April 8, 1974 when Hank Aaron hit his 715th home run. You can learn more about the fascinating history of these numbers in this Numberphile video.

Goal

Write a complete program or function which, given a positive integer n, outputs the nth Aaron number, where the nth number is defined to be the larger integer of the nth Ruth-Aaron pair. Thus the nth Aaron number is a(n)+1, where a(n) is the nth term in the OEIS sequence A039752.

Test cases

The first few Aaron numbers are

6,9,16,78,126,715,949,1331,1521,1863,2492,3249,4186,4192,5406,5561,5960,6868,8281,8464,10648,12352,14588,16933,17081,18491,20451,24896,26643,26650,28449,28810,33020,37829,37882,41262,42625,43216

Rules

\$\endgroup\$
  • \$\begingroup\$ To be sure, "counting multiplicity" means that 20 -> 2, 2, 5 not 2, 5 right? \$\endgroup\$ – HyperNeutrino Aug 7 '17 at 17:29
  • \$\begingroup\$ @Okx I was, I just noticed that when I refreshed his Youtube profile, he had exactly 1 more subscriber (not me) \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 17:30
  • \$\begingroup\$ @HyperNeutrino Yes. I'll edit to make more clear. \$\endgroup\$ – ngenisis Aug 7 '17 at 17:31
  • \$\begingroup\$ Can we choose between 0 and 1 indexing? \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 17:33
  • 3
    \$\begingroup\$ I too, watched today's Numberphile video \$\endgroup\$ – shooqie Aug 7 '17 at 17:43

12 Answers 12

7
\$\begingroup\$

05AB1E, 11 10 9 bytes

-1 byte thanks to Emigna
-1 byte thanks to Adnan

µN>Ð<‚ÒOË

Explanation:

µ            While the counter variable (which starts at 0) is not equal to the input:
 N>          Store the current iteration index + 1, and then create an array with
   Ð<‚       [current iteration index + 1, current iteration index]
      ÒO     Get the sum of the prime factors of each element
        Ë    If all elements in the array are equal,
             implicitly increment the counter variable

1-indexed.

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Explanation when you can, please :) \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 17:34
  • \$\begingroup\$ @Mr.Xcoder Added. \$\endgroup\$ – Okx Aug 7 '17 at 17:36
  • \$\begingroup\$ 10 bytes: µN>Ð<‚ÒO˽ \$\endgroup\$ – Emigna Aug 7 '17 at 17:41
  • \$\begingroup\$ @Emigna Ah, nice one. \$\endgroup\$ – Okx Aug 7 '17 at 17:44
  • 2
    \$\begingroup\$ @Adhnan Really? That's a crazy language feature. \$\endgroup\$ – Okx Aug 7 '17 at 18:03
5
\$\begingroup\$

Husk, 11 9 bytes

-2 bytes thanks to a clever golf by @Leo

€∫Ẋ¤=oΣpN

Try it online!

Explanation

  Ẋ     N   -- map function over all consecutive pairs ... of natural numbers           [(1,2),(2,3),(3,4),(4,5)...]
   ¤=       --   are the results of the following function equal for both in the pair?
     oΣp    --     sum of prime factors                                                   [0,0,0,0,1,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0]
 ∫          -- cumulative sum                                                           [0,0,0,0,0,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3]                
€           -- the index of the first value equal to the input
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice work, I was about to post substantially the same idea :) \$\endgroup\$ – Leo Aug 7 '17 at 18:24
  • 2
    \$\begingroup\$ A golfier version tio.run/##ARsA5P9odXNr///igqziiKvhuorCpD1vzqNwTv///zY \$\endgroup\$ – Leo Aug 7 '17 at 19:19
  • 1
    \$\begingroup\$ @Leo Ooh, €∫ is a really nice trick! And one that only works in a lazy language. ;) \$\endgroup\$ – Zgarb Aug 7 '17 at 19:36
  • \$\begingroup\$ @Leo Very clever. \$\endgroup\$ – H.PWiz Aug 7 '17 at 19:37
3
\$\begingroup\$

Pyth, 23 20 bytes

This is 1-indexed.

WhQ=-QqsPZsPhZ=+Z1;Z

Test Suite or Try it online!


Explanation

WhQ=-QqsPZsPhZ=+Z1;Z  - Full program. Takes input from Standard input.

WhQ                      - While Q is still higher than 0.
       sPZ               - Sum of the prime factors of Z.
          sPhZ           - Sum of the prime factors of Z+1.
      q                  - If the above are equal:
   =-Q                     - Decrement Q by 1 if they are equal, and by 0 if they are not.
              =+Z1;      - Increment Z on each iteration.
                   Z     - Output Z. 
\$\endgroup\$
3
\$\begingroup\$

Jelly, 12 bytes

;‘ÆfS€Eµ⁸#Ṫ‘

A monadic link taking and returning non-negative numbers

Try it online!

How?

;‘ÆfS€Eµ⁸#Ṫ‘ - Link: number, n
         #   - n-find (counting up, say with i, from implicit 1)
        ⁸    - ...number of matches to find: chain's left argument, n
       µ     - ...action: the monadic chain with argument i:
 ‘           -   increment = i+1
;            -   concatenate = [i,i+1]
  Æf         -   prime factors (with duplicates, vectorises)
    S€       -   sum €ach
      E      -   all (two of them) equal?
          Ṫ  - tail, the last matching (hence nth) i
           ‘ - increment (need to return i+1)
\$\endgroup\$
3
\$\begingroup\$

PHP, 93 92 91+1 bytes

while(2+$argn-=$a==$b)for($b=$a,$a=!$x=$n+=$k=1;$k++<$x;)for(;$x%$k<1;$x/=$k)$a+=$k;echo$n;

Run as pipe with -nR or try it online.

-2 bytes with 3-indexed (fist Aaron number for argument 3): remove 2+.

breakdown

while(2+$argn       # loop until argument reaches -2 (0 and 1 are false positives)
    -=$a==$b)           # 0. if factors sum equals previous, decrement argument
    for($b=$a,          # 1. remember factors sum
        $a=!            # 3. reset factors sum $a
        $x=$n+=         # 2. pre-increment $n and copy to $x
        $k=1;$k++<$x;)  # 4. loop $k from 2 to $x
        for(;$x%$k<1;       # while $k divides $x
            $x/=$k)             # 2. and divide $x by $k
            $a+=$k;             # 1. add $k to factors sum
echo$n;             # print Aaron number $n
\$\endgroup\$
3
\$\begingroup\$

MATL, 17 bytes

`@:"@Yfs]vd~sG<}@

1-based. Very slow.

Try it online!

Explanation

`        % Do...while
  @      %   Push iteration index k, starting at 1
  :      %   Range [1 2 ... k]
  "      %   For each j in [1 2 ... k]
    @    %     Push j
    Yf   %     Row vector of prime factors
    s    %     Sum
  ]      %   End
  v      %   Concatenate whole stack into a column vector
  d      %   Consecutive differences. A zero indicates a Ruth-Aaron pair
  ~s     %   Number of zeros
  G<     %   Is it less than the input? If so: next k. Else: exit loop
}        % Finally (execute right before when the loop is exited)
  @      %   Push current k
         % Implicit end. Implicit display
\$\endgroup\$
3
\$\begingroup\$

Mathematica, 97 bytes

(t=r=1;While[t<=#,If[SameQ@@(Plus@@((#&@@# #[[2]])&/@FactorInteger@#)&/@{#,#+1}&@r),t++];r++];r)&


Try it online!

\$\endgroup\$
  • \$\begingroup\$ It needs to output the larger of the pair according to the description; 6 returns 714 instead of 715, for example. \$\endgroup\$ – numbermaniac Aug 8 '17 at 7:36
  • 1
    \$\begingroup\$ @numbermaniac fixed! saved 2 bytes! \$\endgroup\$ – J42161217 Aug 8 '17 at 8:23
2
\$\begingroup\$

Pyth, 12 11 bytes

e.fqsPtZsPZ

Indexing from 1 removes a byte, and puts Pyth ahead of Jelly


Explanation

e.fqsPtZsPZ  - Full program. Takes input from Standard input.

e.f          - Last element of the list of the first $input numbers for which
   q         - Are equal 
    s   s    - The sum of
     PtZ PZ  - Prime factors of $number-1 and $number

\$\endgroup\$
1
\$\begingroup\$

Jelly, 17 bytes

ÆfS=’ÆfS$$µ³‘¤#ṖṪ

Try it online!

Explanation

ÆfS=’ÆfS$$µ³‘¤#ṖṪ  Main link, argument is z
              #    Find the first       elements that satisfy condition y: <y><z>#
           ³‘¤                    z + 1
          µ        Monadic link, where the condition is:
  S                The sum of
Æf                            the array of primes that multiply to the number
   =               equals
       S           The sum of
     Æf                       the prime factors of
    ’                                              the number before it
        $$         Last two links as a monad, twice
               Ṗ   k -> k[:-1]
                Ṫ  Last element (combined with `pop`, gets the second last element)

1-indexed

\$\endgroup\$
  • 1
    \$\begingroup\$ I am not sure 2-indexing is allowed by default rules. \$\endgroup\$ – Mr. Xcoder Aug 7 '17 at 17:36
  • \$\begingroup\$ @Mr.Xcoder Sure, fixed. \$\endgroup\$ – HyperNeutrino Aug 7 '17 at 17:40
1
\$\begingroup\$

Ruby, 89 86 bytes

->n{(1..1/s=0.0).find{|x|r,c=2,0
0while x%r<1?(x/=r;c+=r):x>=r+=1
(c==s)?0>n-=1:!s=c}}

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Japt, 19 bytes

1+_°k x ¥Zk x «U´}a

Uses 1-indexing.

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Python 2, 119 104 102 101 bytes

f=lambda n,k=2:n/k and(f(n,k+1),k+f(n/k))[n%k<1]
i=input();g=0
while-~i:i-=f(g)==f(g+1);g+=1
print(g)

Try it online!

-17 bytes thanks to @ovs!

-1 byte thanks to @notjagan

Credit goes to Dennis for the prime factorization algorithm. 1-indexed.


Note: This is extremely slow and inefficient. Inputs higher than 7 will crash unless you set import sys and do sys.setrecursionlimit(100000), but it works in theory.

\$\endgroup\$
  • \$\begingroup\$ 104 bytes by making f a function calculating the sum of prime factors \$\endgroup\$ – ovs Aug 7 '17 at 20:42
  • \$\begingroup\$ Would be great if you would track your bytecount (and maybe comment your edits). \$\endgroup\$ – Titus Aug 7 '17 at 20:49
  • \$\begingroup\$ (f(n,k+1),k+f(n/k))[n%k<1] for another -2 bytes. This makes it even slower. \$\endgroup\$ – ovs Aug 7 '17 at 20:53
  • \$\begingroup\$ -1 byte by switching i+1 to -~i. \$\endgroup\$ – notjagan Aug 8 '17 at 2:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.