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

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.

 u(2) Quantity of composite numbers before a prime (or a probable prime) appears in the sequence u(n+2) = u(n+1)+u(n);  u(1) = 1 8 3 24 6 25 10 64 18 142 24 669 39 890 48 1002 50 1131 51 1435 60 1989 114 3972 407 29174 881 55575 9067 1090902 11010 (result from Chris Nash who programmed his PRIMEFORM code on request) 1714656 13910 (idem) 6883849 >48647 (idem, 1/1/2000) ? ? b a=1 Infinite

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

 u(2) Quantity of composite numbers before a prime (or a probable prime) appears in the sequence u(n+2) = u(n+1)+u(n);  u(1) = 4 21 4 45 7 51 8 261 16 305 20 785 23 891 38 1095 364 8979 367 30069 643 100759 788 124185 3004 720575 31397 (Using PRIMEFORM after 2032 digits) 3967361 >47384 (9909 digits at 2/1/2000, using PRIMEFORM after 2032 digits) ... ? b a=4? infinite

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

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.

U(170)=227571173880488750152174908764292947833329361113905950362505677262337

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

***

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.

***

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)

"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):

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]
u(2) = 13174844261034202[=2*4481*1470078583021]

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(2) = 1510028911088401971189590305498785

then become

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

I found that the Fibonacci sequence for u(1)=4, u(2)=3967361 probably has 89503 consecutive composites. I say probably because the 89504th term is 3-PRP, but I wasn't able to prove its primality. Perhaps someone else would care to prove its primality, but at 18712 digits, I think it's out of my range for this form.

***

John Nicol sent (Oct. 4, 2004) the following very interesting contribution.

I wanted to update this puzzle...

Although in 1990, Donald Knuth discovered the composite Fibonacci sequence:
u(1)= 62638280004239857 and
u(2)= 49463435743205655,

Note that on above, these terms u(1) and u(2) have been inadvertently reversed [that's the way they appear in the R. K. Guy's book, p. 11, CR]. This means Rick Shepherd's note is likely invalid, since the reversed terms are unlikely to constitute a composite Fibonacci sequence [or they are valid making the proper reversing, CR]

In addition, in 1990 Herbert Wilf found the smaller 17-digit pair:
u(1) = 20615674205555510 and
u(2) = 3794765361567513.

And in 1999 John Nicol (that's me) found the smaller 12-digit pair:
u(1) = 407389224418 and
u(2) = 76343678551.

References:
Herbert S. Wilf, Letters to the Editor, Mathematics Magazine 63 (1990), 284 John W. Nicol, A Fibonacci-like sequence of composite numbers, The Electronic Journal of Combinatorics v. 6(1) (1999), R44.
abstract: http://www.combinatorics.org/Volume_6/Abstracts/v6i1r44.html

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!!!

***

 Records   |  Conjectures  |  Problems  |  Puzzles

 Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.