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

Question:

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


Solution:

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:

3998094509
4997719499
7369307219

***

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:

f(0)=4109355036959
f(1)=4109355036961
f(2)=16886798819788522966041601
f(3)=285163974380011052145033104437715842266772930560001
f(4)=
813184922842035997316061285984072393325394068447975735939012051758969
56396923659519570581913600000001
f(5)=
661269718737608038306331633156409174030623576506013895765168627135044
165565655941249372213421363090241527339594205302044863667773950048188
0593852970658833909784236964257314836927437864960000000000000001
f(6)=
437277640919315243514787851517751082721195257036696929098144568407957
920797032668040071454163950082962790256662644321871244216898947128310
396937497654368156594418147998528995865975591284432223136928623664627
293496717205649428628521123863684172634387233026153590991365834794438
361887012729368899010291270461836799147284907986146416473268907016127
38703984886086481563195801600000000000000000000000000000001

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.

Jim.

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