Problems & Puzzles: Puzzles

Puzzle 358. Ruth-Aaron pairs revisited

April is almost dying and I almost forget to show you this table, just partially linked to Ruth-Aaron pairs.

k  smallest n [n.(n+1)] prime factorization
1 1 2
2 2 2.3
3 5 2.3.5
4 14
5 384
6 1715
7 714
8 633555
9 Next?  

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 table above.

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 here.

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 Puzzle 173?

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 issue.


Contribution came from Farideh Firoozbakht, J. K. Andersen and Fred Schneider.

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: . On top of that Enoch Haga provided to me with two possible snail addresses & phones about two Mr. Crump, using (Haga) a useful link . 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.


Farideh wrote:

Q1. Next term of the sequence 1, 2, 5, 14, 384, 1715, 714, 633555,  greater
than 4*10^9.
Q3. If  x = 10^48+ 7270361 and n = (216*x + 221)*(3888*x^2 + 7752*x + 3863)
then (n, n+1)  is a large Ruth - Aaron pair (please see answer to question 4).
( 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 = p*q  then 
S(n) = p + q = 4 + r + s = S(n+1) , namely (n, n+1) is a Ruth - Aaron pair. 
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 composite.


Andersen wrote:

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 in:
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 = 4(2x+1)(48x^2+30x-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.


Fred wrote:

Question #1: I verified that there are no answers through Note the sequence
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.


Question #3:
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.


Question #4:

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 949(=13*79)

Pair solution for 3584*x^3+4320*x^2+1568*x+152/153 where p,q,r and s are prime

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


Question 5:
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 repetition.

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 k*2411#+1.
I used these to search Ruth-Aaron pairs with x = k*2411#, where x+1 is prime.
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 3109-digit n.

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 300000.


Giovanni Resta wrote pn July 18, 2013:

I searched for Ruth-Aaron triplets up to 10^13.

For the version with repeated primes I can only confirm that
up to 10^13 the only triplets are those starting at 417162 and 6913943284.

For the version without repeated primes I confirmed the two already known (89460294, 151165960539) and I found 3 new solutions:
3089285427491, 6999761340223, 7539504384825.

For the largest one we have
7539504384825 = 3^2 * 5^2 * 7^2 * 43 * 251 * 63361,
7539504384826 = 2 * 19 * 367 * 10181 * 53101,
7539504384827 = 17 * 457 * 26309 * 36887 and
3+5+7+43+251+63361 = 2+19+367+10181+53101 = 17+457+26309+36887.

I have submitted to OEIS these 5 numbers as sequence A227654.



Records   |  Conjectures  |  Problems  |  Puzzles