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):
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.
***
|
