15
\$\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\$
11
  • \$\begingroup\$ To be sure, "counting multiplicity" means that 20 -> 2, 2, 5 not 2, 5 right? \$\endgroup\$
    – hyper-neutrino
    Aug 7, 2017 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, 2017 at 17:30
  • \$\begingroup\$ @HyperNeutrino Yes. I'll edit to make more clear. \$\endgroup\$
    – user61980
    Aug 7, 2017 at 17:31
  • \$\begingroup\$ Can we choose between 0 and 1 indexing? \$\endgroup\$
    – Mr. Xcoder
    Aug 7, 2017 at 17:33
  • 3
    \$\begingroup\$ I too, watched today's Numberphile video \$\endgroup\$
    – shooqie
    Aug 7, 2017 at 17:43

14 Answers 14

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\$
6
  • 1
    \$\begingroup\$ Explanation when you can, please :) \$\endgroup\$
    – Mr. Xcoder
    Aug 7, 2017 at 17:34
  • \$\begingroup\$ @Mr.Xcoder Added. \$\endgroup\$
    – Okx
    Aug 7, 2017 at 17:36
  • \$\begingroup\$ 10 bytes: µN>Ð<‚ÒO˽ \$\endgroup\$
    – Emigna
    Aug 7, 2017 at 17:41
  • \$\begingroup\$ @Emigna Ah, nice one. \$\endgroup\$
    – Okx
    Aug 7, 2017 at 17:44
  • 2
    \$\begingroup\$ @Adhnan Really? That's a crazy language feature. \$\endgroup\$
    – Okx
    Aug 7, 2017 at 18:03
6
\$\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\$
4
  • 1
    \$\begingroup\$ Nice work, I was about to post substantially the same idea :) \$\endgroup\$
    – Leo
    Aug 7, 2017 at 18:24
  • 3
    \$\begingroup\$ A golfier version tio.run/##ARsA5P9odXNr///igqziiKvhuorCpD1vzqNwTv///zY \$\endgroup\$
    – Leo
    Aug 7, 2017 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, 2017 at 19:36
  • \$\begingroup\$ @Leo Very clever. \$\endgroup\$
    – H.PWiz
    Aug 7, 2017 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
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\$
2
  • \$\begingroup\$ It needs to output the larger of the pair according to the description; 6 returns 714 instead of 715, for example. \$\endgroup\$ Aug 8, 2017 at 7:36
  • 1
    \$\begingroup\$ @numbermaniac fixed! saved 2 bytes! \$\endgroup\$
    – ZaMoC
    Aug 8, 2017 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\$
2
  • 1
    \$\begingroup\$ I am not sure 2-indexing is allowed by default rules. \$\endgroup\$
    – Mr. Xcoder
    Aug 7, 2017 at 17:36
  • \$\begingroup\$ @Mr.Xcoder Sure, fixed. \$\endgroup\$
    – hyper-neutrino
    Aug 7, 2017 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\$
4
  • \$\begingroup\$ 104 bytes by making f a function calculating the sum of prime factors \$\endgroup\$
    – ovs
    Aug 7, 2017 at 20:42
  • \$\begingroup\$ Would be great if you would track your bytecount (and maybe comment your edits). \$\endgroup\$
    – Titus
    Aug 7, 2017 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, 2017 at 20:53
  • \$\begingroup\$ -1 byte by switching i+1 to -~i. \$\endgroup\$
    – notjagan
    Aug 8, 2017 at 2:09
0
\$\begingroup\$

Japt, 14 bytes

Èk x ¶Yk x}iU1

Try it

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

Gaia, 13 bytes

⟨:)ḍΣ¤ḍΣ=⟩#e)

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.