Problems & Puzzles:
Ruth-Aaron pairs revisited
April is almost
dying and I almost forget to show you this table, just partially
linked to Ruth-Aaron pairs.
|| smallest n
||[n.(n+1)] prime factorization
In this table, I have collected just the
smallest pair of consecutive numbers, n & n+1 such that the
product n(n+1) contains the first k primes.
Please notice that these pairs are not full
Ruth-Aaron pairs because they are not obliged to the condition
about the sum of the prime factors.
1. Find the next row in the
Now I will switch to full Ruth-Aaron pairs:
2. Can someone of you tell me
where can I find Joe K. Crump? (Joe, can you contact me?)
3. Please send the largest
Ruth-Aaron pair calculated by you.
Hint: You may use the strategy described by
Pomerance et alia
4. Can you provide a strategy
other than the given by Pomerance and friends?
5. Can you produce a larger
Ruth-Aaron triplets than the given in the
BTW, it's false the claim that the Ruth-Aaron
pairs has been proved to be infinite many of them. I promise to
change this row once I understand exactly what happened with this
Contribution came from Farideh Firoozbakht, J. K. Andersen and Fred
Regarding Q2, I have not made full contact with Mr. Crump but, instead,
with a very interesting link provided by J. K. Andersen where I have been
able to find his 'lost' interesting pages:
www.archive.org . On top of that
Enoch Haga provided to me with two possible snail addresses & phones about
two Mr. Crump, using (Haga) a useful link
www.ancestry.com . One of these days
I will call these two Mr. Crump living in Charlotte, NC., just to ask for
him. It would be very nice to find out he is doing well now.
Q1. Next term of the sequence 1, 2, 5, 14, 384, 1715, 714, 633555, ...is
Q3. If x = 10^48+ 7270361 and n = (216*x + 221)*(3888*x^2 + 7752*x +
then (n, n+1) is a large Ruth - Aaron pair (please see answer to
( n = 8398080000000000000000000000000000000000038094196
, n is a 150-digit number)
Q4. If p = 216*x + 221, q = 3888*x^2 + 7752*x + 3863, r = 54*x + 53 &
s = 3888* x^2 + 7914*x + 4027, then
p*q + 1 = 4*r*s = 839808*x^3 + 2533680*x^2 + 2547600*x + 853724.
p + q = 4 + r + s = 3888*x^2 + 7968*x + 4084
Hence, if for some x all the four numbers p, q, r & s are primes and n =
S(n) = p + q = 4 + r + s = S(n+1) , namely (n, n+1) is a Ruth - Aaron
I found other functions for p, q,r & s such that p + q = 4 + r + s &
p*q + 1 = 4*r*s
but for each x at least one of the four numbers p, q, r & s is
1. k=9 has no solution with n < 10^150. Either n or n+1 must be
divisible by at most 4 of the 9 primes. I multiplied at most 4 of the
primes in all multiplicity combinations and tested whether the
product+/-1 was divisible by the remaining primes.
In all such cases there were other unwanted factors above 23, e.g. 103
n = 29181870080 = 2^21*5*11^2*23, and n+1 = 3^4*7^2*13*17^2*19*103.
Modular arithmetic could have speeded up the search but the solution
chance seems tiny.
3. The strategy by Pomerance and friends is to find x such that all 4
parentheses are prime in: n = (8x+5)(48x^2+24x-1), and n+1 =
x = 651028062*797#/5 gives a solution with 1016 digits in the pair.
The GMP library made prp tests. PrimeForm/GW proved the primes.
5. The next triplet with repetition:
6913943284 = 2x2x37x89x101x5197
6913943285 = 5x283x1259x3881
6913943286 = 2x3x167x2549x2707
2+2+37+89+101+5197 = 5+283+1259+3881 = 2+3+167+2549+2707 = 5428
There are no more triplets with or without repetition below 24x10^9.
Question #1: I verified that there are no answers through Note the
which contains the max pairs such that there are both are p(n) smooth
where p(n) is the nth prime. While trying to extend this sequence, I
became curious about this question and verified that there were no
solutions between p(9) and p(17) such that all primes through p(n)
were shared between consecutive integers by checking all the p(n)-smooth
numbers through the max in the linked sequence.
Using the Pomerance and friends strategy and seed x=10^100+398258486,
384x^3+432x^2+112x-5/4 is a 302-digit solution pair:
p,q,r and s were verified prime in PARI/GP.
Note: I found 3 solutions between 10^100 and 10^100+40*10^6. It should
be easy to find a higher solution.
I found three more answers based on the Pomerance and friends method
pair solution for 384x^3+432x^2+128*x+4/5 where p,q,r and s are prime
The first answer is at x=1 giving:
p=3, q=79, r=73 and s=13 which give the pair: 948(=4*3*79) and
Pair solution for 3584*x^3+4320*x^2+1568*x+152/153 where p,q,r and s
The first solution is at x=65, giving
Which give the pair: 1002610072, 1002610073
f(x) = 3584*x^3 + 1536*x^2+135/136 where p,q,r and s are prime
The first solution is at x=53, giving:
Which give the pair: 545791591,545791592
There are no other "with repetition" triplets through 5.5x10^9
Later, on May12, J. K. Andersen sent "New strategy and larger
Ruth-Aaron pair". As a matter of fact this pair is for sure today (May,
2006) the largest RA pair ever gotten and published. Please write
us if we are wrong on this issue.
Question 3 and 4. Let S(n) be the sum of the prime factors of n.
The following strategy works whether they are added with or without
Let x be any natural number, and a = S(x+1)-S(x).
Assume q = x*a-1 and r = (x+1)*a-1 are both primes.
Let n = (x+1)*q.
n+1 = (x+1)*q+1 = (x+1)*(x*a-1)+1 = x*((x+1)*a-1) = x*r
S(n) = S(x+1)+S(q) = S(x+1)+x*a-1 = S(x)+a+x*a-1
S(n+1) = S(x*r) = S(x)+S(r) = S(x)+(x+1)*a-1 = S(x)+a+x*a-1
This shows S(n) = S(n+1), so (n, n+1) is a Ruth-Aaron pair.
The method by Pomerance et al. is a special case of the above.
Their formula corresponds to primes s = x/4 and p = x+1.
To search large solutions with q and r prime, x and x+1 must have
known factorizations, so a can be computed.
One way to find such x and x+1: Let x be a product of known primes,
where x+1 is prime.
In an unrelated search for 8 titanic primes in arithmetic progression,
Markus Frind and Paul Underwood computed millions of prp's on the form
I used these to search Ruth-Aaron pairs with x = k*2411#, where x+1 is
a = S(x+1)-S(x) = x+1-S(k)-S(2411#) = k*2411#-S(k)-398770.
k=3947712031 with S(k)=2610 gives a solution.
n = (x+1)*q = (x+1)*(x*(x-2610-398770)-1) = (x+1)*(x*(x-401380)-1),
where x = 3947712031*2411#. n has 3108 digits.
k=4941451234 with S(k)=145336820 gives another solution with
PrimeForm/GW made prp tests and primality proofs of x+1, q and r.
Question 5. There are only the 3 known triplets below 10^11, among
106770 pairs with repetition, and 104637 without repetition.
One day after, JKA reported at last one new solution to Q5:
A triplet without repetition:
151165960539 = 3x11x11x83x2081x2411
151165960540 = 2x2x5x7x293x1193x3089
151165960541 = 23x29x157x359x4021
3+11+83+2081+2411 = 2+5+7+293+1193+3089 = 23+29+157+359+4021 = 4589
The search was exhaustive to 10^11. From 10^11 to 10^12 it only tested
without repetition, and only numbers with all prime factors below