Generating "own" Fibonacci sequence

6
votes

I've got an unusual (I think) problem. For a given number F_n (I don't know the value of n), I have to find numbers F_0, F_1 such that F_{n}=F_{n-1}+F_{n-2}. The additional difficulty is that this sequence should be as long as possible (value n for F_n should be the highest) and if there exist more then one solution I must take this with the smallest F_0. In short I must generate my "own" Fibonacci sequence. Some examples:

in: F_n = 10; out: F_0 = 0; F_1 = 2;

in: F_n = 17; out: F_0 = 1; F_1 = 5;

in: F_n = 4181; out: F_0 = 0; F_1 = 1;

What I observed for every sequence (with "Fibonacci rule") F_n there is:

F_n = Fib_n * F_1 + Fib_{n-1} * F_0

Where Fib_n is the n-th Fibonacci number. It is true especially for Fibonacci sequence. But I do not know whether this observation is worth anything. We don't know n and our task is to find F_1, F_0 so I think we have gained nothing. Any ideas?

5
algorithmfibonacci
How about F_1 = F_n and F_0 = 0? You get the smallest possible F_0! - Shahbaz
@Shahbaz: but not the longest sequence. - Gareth Rees
Do F_0 and F_1 have to be nonnegative? - oldboy
@oldboy, yes, I should have written this - xan
(4,1,5,6,11,17) is longer than (1,5,6,11,17) ;) - n. 1.8e9-where's-my-share m.

5 Answers

3
votes

Fn-1 = round(Fn/φ)

where φ=(√5+1)/2.

Proof is left as an exercise for the reader ;^P

Update This is incorrect, back to the drawing board.

Update 2 Let's compute backwards from Fn and Fn-1.

Fn-2 = Fn - Fn-1
Fn-3 = Fn-1 - Fn-2 = Fn-1 - (Fn - Fn-1) = 2Fn-1 - Fn
Fn-4 = Fn-2 - Fn-3 = (Fn - Fn-1) - (2Fn-1 - Fn) = 2Fn - 3Fn-1
Fn-5 = Fn-3 - Fn-4 = (2Fn-1 - Fn) - (2Fn - 3Fn-1) = 5Fn-1 - 3Fn
Fn-6 = Fn-4 - Fn-5 = (2Fn - 3Fn-1) - (5Fn-1 - 3Fn) = 5Fn - 8Fn-1

Notice the pattern? It is easy to compute any member of the sequence out of the real Fibonacci sequence and the last two members. But we only know the last member, how can we know the one before last?

Let's write down the requirement Fi>0 in terms of Fn-1.

Fn-2 = Fn - Fn-1 > 0 ⇒ Fn-1 < Fn
Fn-3 = 2Fn-1 - Fn > 0 ⇒ Fn-1 > Fn/2
Fn-4 = 2Fn - 3Fn-1 ⇒ Fn-1 < 2Fn/3
Fn-5 = 5Fn-1 - 3Fn ⇒ Fn-1 > 3Fn/5

So we have a sequence of bounds on Fn-1 in written terms of the real Fibonacci sequence, each one tighter than the previous. The very last bound that is still satisfiable determines Fn-1 that corresponds to the longest sequence. If there's more than one number that satisfies the last bound, use either the smallest or the largest one , depending on whether the sequence has even or odd length.

For instance, if Fn=101, then
101*5/8 < Fn-1 < 101*8/13 ⇒ Fn-1 = 63

The previous (incorrect) solution would imply Fn-1 = 62, which is close but no cigar.

2
votes

Your equation

F_n = Fib_n * F_1 + Fib_{n-1} * F_0

is a linear Diophantine equation in two variables F_1 and F_0. The link presents an efficient algorithm to compute a description of the solution set that allows you to find a solution, if one exists, with F_1 >= 0 and F_0 >= 0 and F_0 minimum. You can then attempt to guess n = 0, 1, ... until you find that there's no solution. This approach is polynomial in log(F_n).

2
votes

I'm not sure what you are looking for. The recursive series you mention is defined as:

Fn = F{n-1} + F{n-2}

Clearly, if the staring values can be anything, we can arbirarlily choose F{n-1}, which will give F{n-2} ( = Fn=F{n-1}). Knowing that F{n-1} = F{n-2} + F{n-3}, follows that F{n-3} can be computed from F{n-1} and F{n-2}. This means that you can trace the numbers back to infinity, thus there is no "longest" sequence and there are infinitely many valid sequences.

In a way you are calculating an inverse Fibonacci sequence with initial values F{n} and F{n-1} where F{i} = F{i+2}-F{i+1}, i forever decreasing

UPDATE: If you are looking to constrain the solutionspace to results where all F{i} are non-negative integers, you will get only a handful (most of the time singleton) solutions.

If you calculate the original Fibonacci numbers (Fib{i}), soon you get F{n} < Fib{i-1}; clearly you do not need to go any further. Then you can try all possible combinations of F{0} and F{1} such that F{n} <= Fib{i} * F{1}+ Fib{i-1} * F{0} -- there are only a finite amount of possibilities for non-negative F{0} and F{1} (you can obviously rule out F{0}=F{1}=0). Then see which i(s) is(are) highest amongst the ones that satisfy equality -- you get F{0} and F{1} as well

2
votes

F_n = Fib_n * F_1 + Fib_{n-1} * F_0

Where Fib_n is the n-th Fibonacci number. It is true especially for Fibonacci sequence. But I do not know whether this observation is worth anything. We don't know n and our task is to find F_1, F_0 so I think we have gained nothing.

Well, you're looking for the longest sequence, this means you want to maximize n.

Create a lookup table for fibonacci numbers. Start with the biggest n such that Fib_n <= F_n, the previous entry in the table is fib_n{n-1}. Now the only variables are F_1 and F_0. Solve the linear Diophantine equation. If it has a solution, you finished. If not, decrease n by 1 and try again, till you find a solution.

Note: a solution always exists, since F_2 = 1 * F_1 + 0 * F_0 has the solution F_2 = F_1.

0
votes

Mimic the computation of Fibonacci numbers with a matrix (but with different initial values). [[0 1] [1 1]] to power k will yield [F_{n+k}, F_{n+1+k}] when multiplied by [F_{n}, F_{n+1}].

Since raising of a matrix to a power is an O(log n) (assuming multiplications of integers is O(1)), you can perform the whole calculation in O(log n) time until matrix coefficients start to dominate the computation.

I don't know how large the numbers with which you are working happen to be, but the nth power of this matrix is [[F_{n-1} F_n] [F_n F_{n+1}]]. And log(F_n) ~ n/5 (so the billionth Fibonacci number will have roughly 200 million digits).