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:
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?
Jim Howell has solved (4/1/2000) the solution to question 1 of this Problem. According to this result, definitively Graham did not found in 1964 a Fibonacci all composites sequence. Here is his email
"Starting with Graham's numbers, U(170) is prime.
Note: this is a prime, not just a probable prime"
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...:-)
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.
Chris Nash has tested the "incorrect" Graham solution using PRIMEFORM nevertheless without finding any prime up the 208288 th4 member of this sequence, a number of 43563 digits. He has stopped this search (12/02/2000)
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):
Are there smaller u(1), u(2) pair-values than those produced by Knuth? The answer is (surprisingly) "Yes -- easily."
Currently on prob_031.htm is: "Knuth by his own produced a smaller result: u(1)= 49463435743205655. u(2)= 62638280004239857"
If the above is correct, just work backwards twice to get u(-1) and u(0), then make them the new u(1) and u(2):
u(1) = 36288591482171453[=41*885087597126133]
In fact, the same thing can be done with the corrected Graham numbers (but only one step in this case) ... if the following given numbers (Knuth's corrections) are both correct:
u(1) = 331635635998274737472200656430763
u(1) = 1178393275090127233717389649068022 [2*67*4481*131849*13159146953*1131112849369]
and u(2) = 331635635998274737472200656430763 (previous u(1))
Note well that Graham's original numbers as shown have u(1) > u(2).
David Kokales wrote (Set. 2004):
John Nicol sent (Oct. 4, 2004) the following very interesting contribution.
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:
Wilfrid Keller wrote (June 2010):
From the attached paper sent by W.K. I copied this:
Thank you, W!!!