Problems & Puzzles: Puzzles

Puzzle 137.  Product of primes +1, a square


Here we ask for a sequence k primes {p1, p2, p3, ..., pk} such that each of the following:

p1+1, p1.p2+1, p1.p2.p3+1, ... & p1.p2....pk+1

are a square.

It's not hard to demonstrate that if the prime condition is released there are infinite sequences of this kind of infinite length (*).

But what happen when the prime condition is not released?

The largest sequence I have obtained is one having 6 prime members (k=6): {3, 5, 13, 193, 37633, 1416317953}

3+1 = 2^2
3*5+1 = 4^2
3*5*13 = 14^2
etc.

Questions:

1. Can you obtain other sequences of this kind with 6 or more prime members?

2. What is the earliest/largest sequence of this type not involving the prime 5

3.The size (k) of this kind of sequences can be any size, or is there an upper limit for it?

After receiving (Sunday 6/5/01) the Brette & Nash comments about my solution I realize that the both conditions (prime ness & square ness) are too demanding so I will relax a bit the square ness condition but only for the first member of the sequence 4. Can you get a larger sequence (k>6) if p1 +1 needs not to be a square.

______
(*) One more time this (prime condition released) is the subject of another "easy" puzzle from the always interesting  Frank Rubin's "The Contest Center".


Solution

Jean Brette discovered (6/5/01) that the first two terms p1, & p2, of the asked sequence are necessary 3 & 5.

1) p1+1 = a square implies : p1 = 3

2) so, the second equation becomes : 3 p2+1 = n^2, or : 3 p2 = (n +1)(n -1)

3) (n+1) or (n -1) must be a multiple of 3

- if (n+1) = 3 j , then 3 p2 = 3 . j .(3 j - 2) which is impossible. ( j = 1 gives p2 = 1)

- if (n - 1) = 3 j, then 3 p2 = (3 j + 2). 3 . j so j must be 1 and p2 = 5.

He extended his method to discover that p3 may be 13 or 17:

One can applies the same idea for p3.

We want p3 such that : 3 . 5 . p3 = (n + 1) (n -1) so (n + 1) or (n - 1) must be a multiple of 3

case 1 : (n + 1) = 3 j gives 5 . p3 = j .(3 j - 2) and j or (3 j - 2) must be a multiple of 5

- if it is j , then j = 5 and p3 = 13

- if it is (3 j -2) then j > = 4 which is impossible.

case 2 : (n -1) = 3 . j gives 5 . p3 = j .(3 j + 2 ) and j or (3 j + 2) must be a multiple of 5

- if it is j , then j = 5 and p3 = 17

- if it is (3 j +2) then j = 1 = p3 which is impossible.

***

By his own way, Chris Nash arrived (6/5/01) to similar but more general conclusions and results:

"1) Suppose p1.p2...pk+1 is x^2. Then x^2-1 is a product of primes, but x^2-1 factors as (x-1) (x+1). So another way to state the problem is that at every step, the set of primes must be able to be divided into two sets with product that differs by 2.

The easiest way to make sure this is true is to multiply all the existing numbers to get a product P. If either P-2 or P+2 is a prime, then we may add P to the set. It appears that your solution for 6 primes can be constructed with this method. (Curiously, note if you had taken 17 as the third member, the sequence would be 3,5,17,257,65537.... the Fermat numbers).

There may be other ways to extend the sequence, but I will return to that in a moment.

2) The first term must be 3, since p+1 must be a square, let's say x^2. So p=(x^2-1)=(x-1)(x+1), and since p is a prime, x must equal 2. Now it is not too difficult to see that the second term q *must* be 5.

Since 3q=(x-1)(x+1), the left hand side is a product of two primes, the right hand side is a product of two integers. Quickly we can eliminate the possibility either of the terms on the right equals 1. Hence x-1=3 and x+1=q, hence q must equal 5.

There are *no* solutions that do not begin with 3,5.....

3) It is now easy to complete the tests needed to generate *ALL* possible sequences of this type, since it is known the first two terms must be 3 and 5. The algorithm to generate all possible sequences is as follows:

  • Start with a given sequence of length n.
  • Generate all possible partitions of the sequence into two subsets S and T. There are 2^n ways of doing this (since for each term, place it in either S or T).
  • Calculate the product of primes in these subsets, call those products S and T for convenience.
  • If S-2 is divisible by T, test if (S-2)/T is prime, and if so, add it to the sequence to create a new sequence of length n+1.
  • If S+2 is divisible by T, test if (S+2)/T is prime, and if so, add it to the sequence to create a new sequence of length n+1.
  • I'll run the algorithm through later - but it's almost certain that

there are now only a finite number of solutions.... and I do not think any of them have k>6....

Later that day he programmed his algorithm and produced the following complete list of possible results: 

3 5 13
3 5 17

3 5 13 193
3 5 13 197
3 5 17 29
3 5 17 257

3 5 13 193 37633
3 5 17 29 821
3 5 17 29 7393
3 5 17 257 2621
3 5 17 257 65537 (the Fermat primes!)

3 5 13 193 37633 1416317953 (my solution)
3 5 17 29 821 6071297 (new Nash's solution)
3 5 17 257 2621 171767237
(new Nash's solution)

***

Its was exactly here when I decided to eliminate the condition p1+1 a square and added the question 4. After that Nash sent the following comments and concrete results:

"With the relaxed condition, p1 and p2 must still be a twin prime... Here are the first few results I have found with k=4 and p1 not 3:

5, 7, 37, 1297
179, 181, 32401, 1049760001
3389, 3391, 11492101, 132068362410001

Notice they are all of the "Fermat" form (like 3,5,17,257,65537), so each term is the product of all the previous ones, plus 2 = the previous square, plus one. (The other forms seem very difficult to occur). I have not seen a k=5 (yet).

If all solutions are of this form they would look like 'proth' primes (here n must be at least 1, and x must be a multiple of 3, since the first members are twin primes).

x.2^n-1
x.2^n+1
(x^2).2^(2n)+1
(x^4).2^(4n)+1
(x^8).2^(8n)+1

...etc....

x^8 is soon too big for proth.exe, but perhaps this is a way to search.

(If p1>3 I do not think there are any other forms of solution)... Now I seek a condition for x for k=5,6,7 to exist....  Here (8/5/01) is a k=5...

19379, 19381, 375584401, 141063641523360001, 19898950959831015581425689600000001

***

So all we need now is or one example of sequence of 7 members or the proof that no such sequence is possible.

***

Two days later (8/5/01) Nash programmed again his last exposed idea:

"I've now devised a search method for the larger k values. I am looking for solutions of the form

x-1
x+1
x^2+1
x^4+1
x^8+1
...

(I do not think any other form of solution is possible if p1 does not equal 3). All except the first are Generalized Fermat Numbers. It is not difficult to prove that x must be a multiple of 510, otherwise at least one of these first 5 terms will be even or divisible by the Fermat numbers 3, 5, or 17. You already have the first k=5 solution of this form (x=19380=510*38). So now I am looking for larger solutions with all these Generalized Fermat numbers prime.

The first solution for k=6 of this form with all these values primes is:

x = 510*2525500 = 1288005000. The last term of the sequence is 1288005000^16+1:

5736946278877355341964722591083608044626186143384444396057883/
2443476368069565047503906402587890625000000000000000000000000/
000000000000000000000001

The search continues for k=7 - I have written a sieve to test for small factors, so far I have tested up to x=8,000,000,000. Since the search now requires x^32+1 to be prime (which has over 300 digits) as well as all the other primes, including an initial twin, solutions are going to be rare, but I should be able to search up to x=2,000,000,000,000 quite quickly.

But perhaps the odds are against us now - after all, the k = 6 solution has 5 'consecutive' Generalized Fermat Numbers, of course there are only five (known) base 2 Fermat numbers (3,5,17,257,65537). Are six in some other base possible?

***

Did you see it! The challenge: to produce more than 5 consecutive GFN primes!!!.

The first 5 consecutive GFN primes now known are:

1288005000^(2^0) + 1
1288005000^(2^1) + 1
1288005000^(2^2) + 1
1288005000^(2^3) + 1
1288005000^(2^4) + 1

Now we have a new problem inside the original one... as always happen with fertile questions. Let's wait if our friend Nash brings happy news soon on this...

***

But I couldn't resist the temptation to ask to my friend Yves Gallot his opinion about this unexpected relation between this puzzle and the consecutive GFN primes. This is his answer (13/05/01):

 
I saw the unexpected relation and computed some estimates of the b such that b^1+1, b^2+1, ..., b^2^n+1 are all primes. You just have to take the formula given at http://perso.wanadoo.fr/yves.gallot/primes/stat.html and do the product for i=0 to n.
Then the number of GFN b^1+1, b^2+1, ..., b^2^n+1 such that all of them are prime in [2 B] is:
(1) C_1*C_2*...C_n / (2^1*2^2*...*2^n) Integ[ 1/log(b)^(n+1), {b, 2, B}]
if we compute B such that (1) = 1, we have an estimation of the computational effort required to find a solution:
 
n = 1: B = 3
n = 2: B = 4.5
n = 3: B = 34000
n = 4: B = 3.6 10^7
n = 5: B = 5 10^10
n = 6: B = 10^14
n = 7: B = 10^18
 
A solution for n= 5 (6 consecutive GF primes) is just waiting for us. But if we are not lucky, it is difficult today to find a solution with 7 primes and very difficult to do better. But as the integral of 1/log(b)^n is divergent, there is an infinite number of solution for every n.

By rereading the puzzle 137 page, I noticed the Chris Nash just searched for some sequences such that b-1, b+1, b^2+1, ... are prime. I tried to search for some sequences of consecutive GF primes only and quickly found that:
337536^1+1, 337536^2+1, 337536^4+1, 337536^8+1, 337536^16+1 are primes, 5 consecutive GF primes and b=337536 is "closer" to 3.6 10^7.
 
I am continuing the search for 6 consecutive GF primes!

***

Three days later Gallot announced:

"Hola Carlos, I just found 6 consecutive GF primes:

7072833120^1+1
7072833120^2+1
7072833120^4+1
7072833120^8+1
7072833120^16+1
7072833120^32+1

7,072,833,120 is the smallest b such that b^2^0+1, b^2^1+1, b^2^3+1, b^2^4+1, & b^2^5+1 are prime...

(Have you made a special program to find them?) Yes, but just a simple program which constructs b+1, checks if it is not divisible by few small factors and if it is a Fermat prime in base 2. Then continue with b^2+1, etc. As my estimate was 5 10^10, I didn't optimize the code, it was faster to let it run! The search took about 1 day on a Celeron 800...(Have you used some shortcut to find them like multiple of certain factor as explained by Nash?) No, I used no shortcut. The multiple explained by Chris Nash was because of b-1. (Will you attempt the 7 consecutives?) No, I don't think that it is possible with one or two computers. 7072833120 ~ 7 10^9 and the estimate was 5 10^10. For 7 consecutive primes the estimate is 10^14. With my program, it would take about 1000 days on a 800 MHz computer. It should be possible to optimize the code to do it really faster but today I don't have 10 or 20 free PCs to run the test during about one month... all my computers are searching for some large GF primes!"

***

J. K: Andersen wrote on May 10, 2007:

A090872(6) is 2072005925466, since these are primes:
2072005925466^1+1
2072005925466^2+1
2072005925466^4+1
2072005925466^8+1
2072005925466^16+1
2072005925466^32+1
2072005925466^64+1

Yves Gallot's estimate of 10^14 in puzzle 137 was too high.
 

***

 


Records   |  Conjectures  |  Problems  |  Puzzles