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)...
Step 1:
Choose a prime number 'p'.
Step 2:
Let d = 20p+1
Step 3:
Let v = 5p(9p-8)
Step 4:
Let n = (d2+(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: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 sumStep 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=(d2+(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=(d2+(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:
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:
296603151077074197308684124715622560525294501766069587161483751777320391554230009758029564174782423278870115094641644418265512090475910
Have fun!
296603151077074197308684124715622560525294501766069587161483751777320391554230009758029564174782423278870115094641644418265512090475911
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)