Menu
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?
565
Is There a Formula for Finding Fibonacci Numbers? Yes, there is a formula for finding Fibonacci numbers. Fibonacci numbers follow this formula according to which, Fn = Fn-1 + Fn-2, where Fn is the (n + 1)th term and n > 1.
Each of your fingers has three bones in it called phalanges (phalanx for singular). When you measure the length of the phalanges in order from the wrist to the tip of each finger, you will find that the sequence of lengths is pretty close to a Fibonacci sequence.
Fibonacci Number Series: 0, 1, 1, 2, 3, 5, 8, 13,21,34,55,89,144,233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28567, 46368, 75025, 121393, 196418, 317811, …
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.
103
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).
41
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
29
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.
20
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
