Problems & Puzzles: Puzzles

Puzzle 164. Sequences of Fermatian primes

The following puzzle has been posted by Daniel Gronau. It's about the Fermat Numbers, usually described by the function: Fn = 2^(2^n)+1, for n=0, 1, 2, .... Gronau wrote:

"There is an alternative description - a recursive one - of Fermat numbers:

f(n+1) = 2 + f(0)*f(1)*f(2)*...*f(n).
f(0) = 3

Following this "rule" we get the five (known) Fermat successive numbers & primes:

3, 5, 17, 257, 65537.

So I asked myself if we can get again five successive primes if we substitute f(0) with a prime other than 3.

The answer was: YES! As a matter of fact I found five successive primes solutions for the following f(0) values: 19379, 9443669, 11054759, 15992069, 22482329, 32557379, 51102509, ..."

Daniel wondered if the quantity of successive primes obtained by this recursive procedure were limited or not.

I (C.R.) found several f(0) values producing six successive primes. Here are the first 3 of them:

1) 1288004999
2) 1417870889
3) 1619225519


1. Can you find 3 more f(0) solution for sequences of six successive Fermatian primes?

2. Can you find f(0) solutions for sequences with seven and eight successive Fermatian primes


Sudipta Das notices that the recursive expression of the Fermatian numbers, given by Gronau:

f(n+1) = 2 + f(0)*f(1)*f(2)*...*f(n).
f(0) = 3

Can be transformed in a closed expression:

f(n) = (f(0)+1)^(2^(n-1)) + 1, for n>0 
f(0) = 3

Sudipta claims that this expression "is much easier to program and to test for primality, than the recursive form"


Shyam Sunder Gupta has found 3 more f(0) prime values producing sequences of six consecutive primes:



Both Shyam and Sudipta point out that f(0) must leave a remainder of 29 when divided by 30.


Jim Fougeron made an extensive search and here are his results:

I have found no "order 7" or "order 8". I have search ALL ranges up to > 1.6767 trillion. Within this range, there were 217 numbers which satisfied 6 consecutive primes, and 13927 numbers which satisfied 5 consecutive primes (not counting the 217 order 6 numbers). I tested some of the 7th candidate numbers (factoring), and it appears that there is no "pattern" which would eliminate a 7th number being prime (i.e. all were not divisible by 3 or 13 > or 101, ...). It also appeared that the 7th number's behave as to be partly factored, similar to the Fermat numbers, the General Fermat numbers, or the Mersenne type numbers. The prime density would certainly be more than simply a "random" 300 to 400 digit number. At 200+ order 6's I did "expect" to see an order 7 result, but none were found :((((

I did also observe a few "rules" for this sequence. 

1. The f(0) and f(1) must be a twin, since f(1) = f(0)+2

2. f(0)%10 must be 9 : (except for f(0)=3)
if f(0)%10 is even, then f(0) is not a prime
if f(0)%10 is 1, then f(10)%10=3 and 3*1+2 is 5, so f(2) is divisible by 5
if f(0)%10 is 3 then f(1)%10=5 so it is not prime (except if f(0)=3)
if f(0)%10 is 5 then f(0) is not prime (except if f(0) is 5)
if f(0)%10 is 7 then f(1)%10 is 9 and 7*9+2 is 65%10=5.
if f(0)%10 is 9 then f(1)%10 is 1 and f(2)%10 is 9 and f(3,4,...)%10
is 1

3. f(n) as n grows it will end with many 0's followed by a single 1 digit, so MANY (most) of these primes, even when large, will be VERY easily provable (N-1 will be 10^many*something with 10^many often being larger than N^1/3 which allows easy N-1 proving)


I asked to Jim: "Can you also add the type of program (language), computer and time spent in your search? One more question: trillion is like in our system 10^18?". And his answer was:

1 trillion is 2^12 (1,000,000,000,000).  I am currently at 3.845*10^12 and
have found 187 more order 6 values, but no order 7's yet.

I have coded this in VC++ using my own 64 bit Erat primegenerator to find
the twins, and then Miracl large integer library to prp test the "larger"
numbers.  Coding took a few hours, and runtime to 10^12 took 3 Athlon 750mhz
PC about 16 hours each.  I have optimized my code better, and now a single
PC running for about 30 hours pushed from 1.2*10^12 to 3.8*10^12.  Note that
the size of the f(4+) is increasing now, so testing the numbers is slowing
down.  I do expect a series of length 7, but not sure how high I will have
to push to find it.  I will not be searching for a length 8 item ;)  I will
leave that to someone else.  I currently have over 400 length 6 results found.

Here is some new information.  [higher modular requirements for f(0)]

The f(0) numbers in the series (other than f(0)==3) MUST be of the form
f(0)==509 mod(510)    That is why 9 mod(10) and 29 mod(30) were both "valid".
510 is 2*3*5*17 so any number which is made up exclusively of these factors
(10=2*5, 30=3*2*5, 85=17*5, ...) would all "satisfy" the f(0) to be n-1 mod(n).
However, 509 mod(510) is the optimal (maximal) case.


A few hours later Jim informed a beautiful result:

Carlos, here is an update on puzzle 164

I have processed from f(0)=3 to f(0)=4319420014079 and here are the results:
There were 29777 length 5 finds
There were 456 length 6 finds
There is 1 length 7 find.  That find is:


Note f(6) is a 402 digit prime.  Also note that f(0) is the smallest value
which is prime for length 7.  All primes are proven.


What a splendid work!


The 24/3/2002 Phil Carmody came with an example for length 8: f(0)+1=7,190,597,297,273,100

"... something like 3 weeks on my PPro200, and than a final burst on my Duron 900 for a week finally yielded >550 length 7 results before providing a single solitary length 8 result:

f(0)+1 = 7,190,597,297,273,100


The filters required for this test are quite unusual, compared with the usual tasks I've thrown at GenSv, and so I've had to make some tweaks to the code to improve the efficiency in the sieve in these kinds of situations. The thing I'm most proud of is the fact that the largest term is titanic!



Records   |  Conjectures  |  Problems  |  Puzzles