Problems & Puzzles: Problems

Problem 32. Fibonacci and his permuted - all composites sequences

I'll define a permuted Fibonacci sequence u'(k) this way:

u(k) = u(k-1) + u(k-2); u(0) = a, u(1) = b>a, k=>2

u'(k) = u'(k-1) + u'(k-2); u'(0) = b, u'(1) = a


1. if gcd(a, b) = 1, does exist a couple of values (a, b) such that u(k) and u'(k) are composite for all k?

2. If so, can you produce one of these (a, b) pairs?

(nota bene If you have any initial reluctance to accept that these kind of sequences may exist I would like to tell you that a small search done with a small code in Ubasic using the stepladder approach -See Problems 30 & 31- has produced the following partial solution: the pair a=26 and b= 8256175 produces 1060 composite members in each sequence u & u' before a prime number of 229 digits appear... )


A little - but maybe useless - history: The 1/1/2000 I asked to Chris Nash what kind of similarity  could exist between a Fibonacci and its permuted (term coined by Nash) sequences. His answer was:

"...Actually, they might not be similar at all! Here is a formula for u(n) in terms of u(1), u(2) and the "normal" Fibonacci numbers

u(n)=u(1)f(n-2) + u(2)f(n-1) u(n)=a.f(n-2)+bf(n-1) and u'(n)=b.f(n-2)+af(n-1) are two "permuted' sequences.

Then we have the following relations

u(n)+u'(n)=(b+a)f(n) and u(n)-u'(n)=(b-a)f(n-3)"

That day I was looking for other properties of u & u' - and not if it could exist a pair of values (a, b) such that u and u' could be all composites sequences. This very question only came up after the involuntary mistake of Jim Howell about the Graham's solution (see Problem 31). For me that was the spark that landed this question...why? because if an all composite Fibonacci sequence lacks this property just permuting the initial conditions (as Howell shown), then it's not trivial to ask for certain initial conditions that make both sequences all composite sequences...

This new idea was communicated from me to Nash and Jim the 1/5/2000. Then Nash also saw immediately that these two sequences are the exact analog counterpart of the two sequences of composites produced by the Brier numbers, according to his following comment "...'Brier-Fibonacci' sequence.... I like it! That is going to take some clever work... but there are some very clever people out there :-)


Four years after this problem was posed, Eric Brier found (September 10, 2004) the first pair of values (a, b) as the asked by question 2, responding by this same example the question 1, too. According to Eric this first solution must be reduced in short (the current digits-length of a & b are 181 and 180, respectively). As a matter of fact Eric is now working in preparing an official and organized presentation of his method and results, that will be published here soon.

Eric asked me to verify - independently to his own verification - his solution. What I can say is that - running a code of mine in Ubasic - starting with the Eric's a & b values the respective permuted Fibonacci sequences, u(k) and u'(k) are composite from k=0 to k=8905 where u and u' has reached to 2041 and 2042 digits long.

Here are - to your consideration - the a & b values reported by Eric:







Records   |  Conjectures  |  Problems  |  Puzzles