Generating "own" Fibonacci sequence
algorithm, fibonacci
Solution
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)`.
Problem
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?