Ruth-Aaron Pairs / A006145

[Ralf Stephan]

You wrote 
> algorithm sits at http://www.spacefire.com/numbertheory/ruthaaron.htm  
> and the server at spacefire has been unresponsive to my attempts.

Use the wayback machine. The last update they have is from Dec 16 2003:
I'll quote it in case...

http://web.archive.org/web/20040227211418/http://www.spacefire.com/numbertheory/ruthaaron.htm

   Ruth-Aaron pairs - and an algorithm by Joe K. Crump
     _________________________________________________________________

   Ruth-Aaron pairs, like {714, 715}, are consecutive numbers {n, n+1}
   such that the sum of the prime factors of each are equal.

   For instance:
   714 = 2 * 3 * 7 * 17
      Sum-of-Factors(714) = 2+3+7+17 = 29
   715 = 5 * 11 * 13
      Sum-of-Factors(715) = 5+11+13 = 29
   
   They were named "Ruth-Aaron" pairs after the famous baseball player
   Hank Aaron got his 715th homerun which defeated Babe Ruth's long-time
   record of 714 homeruns. A mathematician by the name of Carl Pomerance
   noticed the interesting property that the product of the two numbers
   714 and 715 was also the product of the first seven primes
   (2*3*5*7*11*13*17). Then a student of his observed the sum of the
   prime factors of each were equal. And the story continued (see link
   section at bottom)...
     _________________________________________________________________

   Inspired on April 12th 2002 by a recent puzzle on PrimePuzzles.net, I
   started experimenting with Ruth-Aaron pairs. I was able to create a
   simple algorithm you can use to generate some extremely large
   Ruth-Aaron pairs; let's look at it in action first then I'll show you
   how it was derived.

   Step 1: Choose a prime number 'p'.
   Step 2: Let d = 20p+1
   Step 3: Let v = 5p(9p-8)
   Step 4: Let n = (d^2+(4v+1)d-4)/2
   Step 5: Let M = n(n+2v)
   Step 6: If any of the following numbers are NOT prime go back to step
   1. {n}, {n+2v}, {2n-d}, {90p2-61p-6}
   Step 7: All Done. The numbers M and M-1 form a Ruth-Aaron pair!
     _________________________________________________________________

   E.g. In the algorithm above, if you take
   p=123433 you'll find the RA pair:
   11458500073142461852512836718403514710
       Factorization=2 * 5 * 123433 * 1371205964591 * 6770079890682260057
   11458500073142461852512836718403514711
       Factorization=3385039945342364359 * 3385041316545983729

   The sum of the prime factors for each number is 6770081261888348088

   Continuing with more primes p and this specific version of the
   algorithm you'll find more pairs as follows:

   11458500073142461852512836718403514710
   11458500073142461852512836718403514711
   3187793133764126630012112493446934643110
   3187793133764126630012112493446934643111
   41579401268121198749220796887033346345510
   41579401268121198749220796887033346345511
   25535656878510947884218726327567312941635030
   25535656878510947884218726327567312941635031
   ...
   177561956785815018149935855412093504515834133110
   177561956785815018149935855412093504515834133111
     _________________________________________________________________

   Here's how I derived the algorithm:

   Step 1:
   I setup an arbitrary form for a number M in the Ruth-Aaron pair to be
   a product of two prime factors as follows:
       M = n(n+2v)

   Step 2:
   Since the sum of factors of M above is 2n+2v, I setup a form for a
   consecutive number to have a large prime factor (2n-d) close to the
   sum
       M-1 = (2n-d)*Something

   Step 3:
   For this to be satisfied, (2n-d) must divide M-1=n(n+2v)-1. Using some
   clever substitution I found that choosing n=(d^2+(4v+1)d - 4)/2 will
   always satisfy this condition because (M-1)/(2n-d) will then simplify
   to 2 v (1+x)+x (2+x)  where d=2x+1. This can then replace the
   'Something' above.

   Step 4: Since M is odd, M-1 is divisible by 2. Furthermore we need the
   sum of prime factors to be even and so I added an additional
   restriction that M-1 be divisible by 5 (arbitrary). This is to balance
   out the number of odd prime factors in M-1 as we will see. So we
   express M-1 as:
       M-1 = 10*(2n-d)*[(2 v (1+x)+x (2+x))/10]

   Step 5: In order for us to be able to construct a sequence of
   solutions we need some key variable all the others will be based on. I
   choose a prime p such that p divides M-1. So:
       M-1 = 10*p*(2n-d)*[(2 v (1+x)+x (2+x))/(10*p)]

   Step 6: Now let's lock down the factors involved by assuming the
   following expressions will simultaneously be prime: {n}, {n+2v},
   {2n-d},{(2 v (1+x)+x (2+x))/(10*p)}. We can then setup the Ruth-Aaron
   equation with sum of factors on each side in terms of p, x, and v as
   follows:

       2+5+p+(2v(1+x)+x(2+x))/(10*p)+(2n-d) == 2v+2n

   This is where adding the additional factor of 5 in Step 4 comes in
   making this possible. Otherwise the left-side would be odd and
   right-side even. Solving for v we find that

       v = (10p2 - 20p(x-3) + x(2+x)) / (20p - 2(1+x))

   Since we are in complete control of the variables involved, I chose x
   = 10p to simplify v in terms of p. Setting x=10p, v then simplifies to

       v = 5p(9p-8)

   Step 7: Now we are all set. We can construct all the variables
   involved by choosing p. After we choose p,  we calculate v=5p(9p-8),
   x=10p, d=2x+1, n=(d^2+(4v+1)d-4)/2, then M=n(n+2v).

   If any of the expressions in Step 6 aren't prime, we just chose
   another p until they are. :)

   The above may make more sense to you by writing down our newly
   constructed M and M-1 explicitly in terms of p and factoring to give
   the following:

   M = (1800p3 - 1310p2 - 50p - 1) (1800p3 - 1220p2 - 130p - 1)
   M-1 = 2 * 5 * p * (90p2 - 61p - 6) (3600p3 - 2620p2 - 120p - 3)

   And you find that we really have is a Ruth-Aaron polynomial. The sum
   of the factors of M and the sum of the factors of M-1 are both equal
   to:

   3600p3 - 2530p2 - 180p - 2

   Obviously we can make different assumptions in the construction above
   and come up with several variants of this algorithm (and polynomial).
   For instance using a different prime 'q' instead of 5 in Step 4 and an
   appropriate v.
     _________________________________________________________________

   Update:
   After this analysis, I did some further research on what is known
   about Ruth-Aaron pairs as of April 17, 2002. It turns out that I
   wasn't the only one who constructed a Ruth-Aaron polynomial (and thus
   an algorithm for generating RA pairs).  Carl Pomerance, David E.
   Penney, and Carol Nelson on a joint paper for the journal of
   Recreational Mathematics in the Spring of 1974 (Vol 7, No. 2), found
   the following polynomial:

   f(x) = 384x3 + 432x2 + 112x - 5
   f(x) = (8x+5) (48x2 + 24x - 1)
   f(x)+1 = 4 (1+2x) (48x2 + 30x - 1)

   FactorSum =48x2 + 32x + 4

   They probably found the polynomial via inspection as their paper
   didn't address how they came up with it. It is much simpler than the
   one I derived, albeit not as adaptable to different forms.
   Nevertheless, not to be out-done I put together a computerized search
   and found a simpler Ruth-Aaron cubic as follows:

   f(x) = 48x3 - 36x2 - 8x + 1
   f(x) = (1+4x)(12x2 - 12x + 1)
   f(x)-1 = 4x(12x2 - 9x - 2)

   FactorSum = 12x2 - 8x + 2

   However after translating this requiring x to be odd it ends up being
   a cousin of the Pomerance/Penney/Nelson cubic after all!

   f(x) = 384x3 + 432x2 + 128x + 5
   f(x) = (5+8x)(48x2+24x+1)
   f(x)-1 = 4(1+2x)(48x2+30x+1)

   Note: There are several such consecutive polynomials where the
   irreducible divisors add up to be the same BUT whose polynomial
   factors cannot all be simultaneously prime. For instance, f(x) = 4x3 -
   2x2 - 4x is such a case as well as f(x) = 18x3 - 12x2 - 3x + 1.
     _________________________________________________________________

   Update 5/30/2003:
   I put together a generalized pair of RA polynomials for
   investigational purposes. I'll list it here for posterity:

   f(x) = (4kx+5)(12k2x2+12kx-1)
   f(x)+1 = 4(kx+1)(12k2x2+15kx-1)
   where k is even and NOT divisible by 5. Using odd k will often
   generate RA pairs too, so keep that in mind for programmatic use.
     _________________________________________________________________

   It's interesting being able to generate a Ruth-Aaron pair that is out
   of range to be factored by off-the-shelf methods (e.g. 180+ digits).
   Folks that get just the numbers can't even prove they are Ruth-Aaron.
   :)  I say "off-the-shelf" because you can actually create a very-fast
   algorithm to factor Ruth-Aaron numbers.

   For your amusement here is a 135-digit Ruth-Aaron pair:

   2966031510770741973086841247156225605252945017660695871614837517773203
   91554230009758029564174782423278870115094641644418265512090475910
   2966031510770741973086841247156225605252945017660695871614837517773203
   91554230009758029564174782423278870115094641644418265512090475911

   Have fun!
     _________________________________________________________________

   Links:
       A homepage on Ruth-Aaron numbers (geocites.com)
       Playing around with Ruth-Aaron pairs (maa.org)
       Ruth-Aaron Summary (mathworld.wolfram.com)
       Maris-McGwire-Sosa Numbers (aol.com)
       Ruth-Aaron Triplets (primepuzzles.net)
     _________________________________________________________________

   - Joe K. Crump, MCSD
   [mcp_sd_c.gif]
     _________________________________________________________________

   Number Theory Home