Problems & Puzzles: Problems

Problem 31. Fibonacci- all composites sequence

All of us know the Fibonacci (Leonardo de Pisa, 1179-1240) classical sequence - related to the rabbit's problem stated in his Liber Abaci: 1, 1, 2, 3, 5, 8, 13, … etcetera, described by u(n+2) = u(n+1) + u(n); where u(1)=1, u(2)=1

Now it's known that u(n) is prime for n = 3, 4, 5, 7, 11, … (see the complete list at http://www.utm.edu/research/primes/glossary/FibonacciPrime.html )

Ian McLoughlin recently asked on the Mersenne mailing list: does exist a Fibonacci sequence such that all the members are composite numbers? if so what are the initial terms u(1) and u(2) of such Fibonacci composites sequence?

(As, Guri Harari pointed out the 18/02/2000, this problem is not trivial adding the condition that u(1) & u(2) are coprimes)

For sure you have already noticed that this is a kind of problem twin to the Brier numbers problem (Problems 29 & 30) and that's the reason because we have included this problem immediately after those ones.

Francois Perruchaud and Bill Daly both pointed out that in 1964 R.L.Graham constructed one example of such kind of sequences, for which:

u(1) = 1786772701928802632268715130455793

u(2) = 1059683225053915111058165141686995

But Graham made a mistake that corrected by D. E. Knuth (1990) produced the following right results:

u(1) = 331635635998274737472200656430763

u(2) = 1510028911088401971189590305498785

Click here to download an example that illustrates the method used by Graham

1. Despite the Graham's mistake does the sequence generated by his u(1) & u(2) numbers produces only composite numbers? If not, can you find the first (probable) prime in the sequence?

Hint: You can use the sequences feature of the PRIMEFORM code to answer this question

Knuth by his own produced a smaller result:

u(1)= 49463435743205655

u(2)= 62638280004239857

2. Are there smaller u(1), u(2) pair-values than those produced by Knut?

3.- What are the smallest u(1)=a, u(2)=b values such that a+b=minimum, for a Fibonacci-composite sequence ?

Chris Nash asked some days ago (18/12/99):

"4. Find a fib-sequence of all composites, minimizing max(u(1),u(2)). Find one that's provable, and no doubt there is a smaller one (like in the Sierpinski problem) you can conjecture is prime-free.

5. Repeat 3, except now fix u(1)=1."

"I believe there is a MUCH smaller solution than Graham's and suggest one exists around 10^5." adds Nash. This means that Nash thinks also that the Knut's solution is a kind of big…

I wonder if the "stepladder method" proposed at the problem 30 can helps in this problem also. As a matter of fact I started this method for tackling the second Nash's question - u(1)=1 - producing the following initial results.

Obviously in this table every new u(2) in the first column must produce a larger quantity of composite members than its predecessor until reach to  ba=1.

6. Would you like to extend this table? in particular  would you like to continue the search for u(2)=6883849 finding out if this the smallest solution for a fib-all composite sequence?

The search for u(1)=1 was in process when Nash realized that maybe this search must be dropped by a basic inconsistency: u(1)=1 is not a composite number, then if it happens that we succeed to find a u(2) number that produces only composite numbers after u(1), nevertheless the whole sequence can not be told as an fib-all composites sequence. That's why I started constructing a similar table (the stepladder method, again) as the before one but this time for u(1)=4, the first composite natural number. Here are my results 

For this search first I have made a code in Ubasic that produces the subsequent values in the table up to the limit of this package. After I reached to this limit I simply ask to my code that print all the u(2) values that arrive to the 2032 digits without finding a prime number. Then, for each one of these u(2) values printed out by Ubasic, I switch to continue the search in the Nash's PRIMEFORM code, the only public free code to make this kind of search (primality of members of an arbitrary sequence) for very large numbers, as far as I know...(is there another one?.... See  a recent email & answer received claiming that PARI-GP is "...a free general purpose maths package which can do much the same..." than PRIMEFORM. Click here.

7.  Would you like to extend this table? in particular, would you like to continue the search for u(2)=3967361 finding out if this the smallest solution for a fib-all composite sequence?

SOLUTION

Stop the press!!!... 24 hours later and almost at the same time Chris Nash pointed out that u(170) is divided by 3, and - by his part - Jim Howell realized that he used the u(1) Graham's value as u(2) and viciversa... So, the question 1 remains unsolved...phew!...(and it seems that these Graham's numbers are bewitched...:-)

***

Example

From: "Bill Daly" <bill.daly@tradition-ny.com>
To: <mersenne@base.com>
Sent: Monday, December 20, 1999 3:25 PM
Subject: Re: Mersenne: Fibonacci Series

…The sequence was found by R. L. Graham. Reference :

"A Fibonacci-like sequence of composite numbers", R.L. Graham, Math. Mag. 37, 1964.

U(1) = 1786772701928802632268715130455793

U(2) = 1059683225053915111058165141686995

U(N+2) = U(N+1) + U(N)

…

Unfortunately, Graham made a computational error in calculating U(1) and U(2), and the above values don't work as desired. The following will correct the error:

 U(1) =  331635635998274737472200656430763

 U(2) = 1510028911088401971189590305498785

 U(N+2) = U(N+1) + U(N)

The trick is to create a "covering" of the indices, i.e. a set of congruences such that every index satisfies at least one of the congruences. The best way to understand this is by this example. Note that F(4) is divisible by 3, and that every 4th term in the Fibonacci sequence is also divisible by 3, i.e. the period of 3 is equal to 4.

Using the U() series instead of the F() series, it can be verified that U(4n+2) is divisible by 3 for all n. Similarly,

 U(8n+4)   is divisible by    7

 U(16n+8)  is divisible by   47

 U(32n+16) is divisible by 2207

 U(64n+32) is divisible by 1087

 U(64n)    is divisible by 4481

This assures that U(2n) is composite for all n, since every even number is either 2 mod 4, 4 mod 8, 8 mod 16, 16 mod 32, 32 mod 64, or 0 mod 64. Note that F(8)/F(4) = 7, F(16)/F(8) = 47, F(32)/F(16) = 2207, F(64)/F(32) =  1087*4481.

For the odd indices, consider separately the cases 6n+1, 6n+3 and 6n+5. First, the period of 2 is 3, and U(6n+3) is divisible by 2 for all n (in fact, U(3n) is divisible by 2, but at this point we only need the odd values). For 6n+5, we have

 U(18n+5)  is divisible by   17 (actual period = 9)

 U(18n+11) is divisible by   19

 U(54n+17) is divisible by   53 (actual period = 27)

 U(54n+35) is divisible by  109 (actual period = 27)

 U(54n+53) is divisible by 5779

which covers all the cases U(6n+5). For 6n+1, we have

 U(30n+7)  is divisible by    5 (actual period = 5)

 U(30n+13) is divisible by   11 (actual period = 10)

 U(30n+19) is divisible by   61 (actual period = 15)

 U(30n+25) is divisible by   31

 U(60n+1)  is divisible by 2521

 U(60n+31) is divisible by   41 (actual period = 20)

which covers all the cases U(6n+1). This completes the coverage of all cases, thus U(n) is composite for all n.

Graham's error was that his original U(1) and U(2) gave U(64n+33) divisible by 1087, rather than U(64n+32). This doesn't mean necessarily that any U(n) was prime in his original sequence, only that U(n) could not easily be proved composite.

***

"Following the explanation of the 'fault' in Graham's construction, it is only necessary to test u(32), u(96), u(160)... and it is quite easy to set this up using PrimeForm. I tested all n<208288. NO PRIME was found. u(208288) has 43563 digits, and will take my P-200 about 15 hours to test. Perhaps this is a good place to stop :)"

***

At 19/04/2000 Imran Ghory wrote:

"In problem 31 you mention that as far as you know the only free code to 

test the primality for large number is PrimeForm, recently I came across 

a free general purpose maths package which can do much the same 

thing, it's called Pari-GP and is available from www.parigp-home.de  in 

two forms, as a C library and also as an interactive scripting language.



Using it as a scripting language I benchmarked it by getting it to check 

and log that primes exist in every Fibonacci sequence which has u(1)=1 

and u(2)<55575 and found it took about 50 minutes on a 486/66."

***

Rick Shepherd found - at last. April 2003)- one solution to question 2 (smaller solution than the Knut's one):

***

So, now - and since 1999 - John has the record for this question with a solution 12 digits long!. I have asked if smaller solutions could be found. This is what he responded:

Yes, I definitely believe smaller solutions could be found (maybe around 10^8 ? That's a wild guess). Finding the provably smallest solution would be very tricky, though...Another wild guess: a solution to Problem #32 could be found that's on the order of the square of solutions to #31 (i.e., around 10^16).

***

Wilfrid Keller wrote (June 2010):

In 2004, Maxim Vsemirnov has slightly improved John Nicol's record (near the end of your page), please see the attached paper.

From the attached paper sent by W.K. I copied this:

Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.7 "A New Fibonacci-like Sequence of Composite Numbers"

M. Vsemirnov, Sidney Sussex College Sidney Street Cambridge, England CB2 3HU United Kingdom

a = 106276436867, b = 35256392432

 Thank you, W!!!

***