Creating your own Fibonacci sequence

Question

I have an unusual (I think) problem. For a given number F_n (I don’t know the value of n) I need to find the numbers F_0, F_1 ​​such that F_ {n} = F_ {n-1} + F_ {n-2}. An additional difficulty is that this sequence should be as long as possible (the n value for F_n should be the highest), and if there is more than one solution, I must take this with the smallest F_0. In short, I have to create 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 each sequence (with the "Fibonacci rule") F_n is:

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

Where Fib_n is the nth Fibonacci number. This is true, in particular, for the Fibonacci sequence. But I do not know if this observation is worth it. We do not know n, and our task is to find F_1, F_0, so I think we got nothing. Any ideas?

Answer 1

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 . A link is an effective algorithm for calculating a description of a set of solutions that allows you to find a solution, if one exists, with the minimum values F_1 >= 0 and F_0 >= 0 and F_0 . Then you can try to guess n = 0, 1, ... until you find that there is no solution. This approach is a polynomial in log(F_n) .

Answer 2

F _n-1 = round (F _n /?)

where? = (? 5 + 1) / 2.

The proof remains as an exercise for the reader; ^ P

Refresh This is incorrect, return to the drawing board.

Update 2 . Calculate back from F _n and F _n-1 .

F _n-2 = F _n - F _n-1
F _n-3 = F _n-1 - F _n-2 = F _n-1 - (F _n - F _n-1 ) = 2F _n-1 - F _n
F _n-4 = F _n-2 - F _n-3 = (F _n - F _n-1 ) - (2F _n-1 - F _n ) = 2F _n - 3F _{n-1 sub>
F n-5 = F n-3 - F n-4 = (2F n-1 - F n ) - (2F n - 3F n-1 ) = 5F n-1 - 3F psub>
F n-6 = F n-4 - F n-5 = (2F n - 3F n-1 ) - (5F n-1 - 3F n ) = 5F n - 8F n- 1 sub>}

Pay attention to the template? It is easy to calculate any member of a sequence from a real Fibonacci sequence and the last two members. But we only know the last member, how can we recognize him to the last?

Write the requirement F _i > 0 through F _n-1 .

F _n-2 = F _n - F _n-1 > 0 → F _n-1 <F <sub> psub>
F _n-3 = 2F _n-1 - F _n > 0 → F _n-1 > F <sub> psub> / 2
F _n-4 = 2F _n - 3F _n-1 → F _n-1 <2F <sub> psub> / 3
F _n-5 = 5F _n-1 - 3F _n → F _n-1 > 3F <sub> psub> / 5

So, we have a sequence of estimates on F _n-1 in written terms of a real Fibonacci sequence, each of which is more rigid than the previous one. The last estimate that is still being performed determines F _n-1 , which corresponds to the longest sequence. If there is more than one number that satisfies the last boundary, use either the smallest or the largest, depending on whether the sequence has an even or odd length.

For example, if F _n = 101, then 101 * 5 / F _n-1 <101 * 8/13 → F _n-1 = 63

The previous (wrong) solution would imply F _n-1 = 62, which is close, but not cigars.

Answer 3

I'm not sure what you are looking for. You mentioned the recursive series:

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

It is clear that if the desired values ​​can be arbitrary, we can arbitrarily choose F{n-1} , which gives F{n-2} ( = Fn=F{n-1}) . Knowing that F{n-1} = F{n-2} + F{n-3} it follows that F{n-3} can be calculated from F{n-1} and F{n-2} . This means that you can track numbers to infinity, so there is no "longest" sequence and there are infinitely many valid sequences.

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

UPDATE: If you want to limit the solution space to results in which all F{i} are non-negative integer values, you will only get a few (in most cases single-user) solutions.

If you count the original Fibonacci numbers ( Fib{i} ), soon you will get F{n} < Fib{i-1} ; it is clear that you do not need to go any further. Then you can try all possible combinations of F{0} and F{1} so that F{n} <= Fib{i} * F{1}+ Fib{i-1} * F{0} - there is only a finite number possibilities for non-negative F{0} and F{1} (you obviously can exclude F{0}=F{1}=0 ). Then look at which i (s) are the highest among those that satisfy equality: you also get F{0} and F{1}

Answer 4

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

Where Fib_n is the nth Fibonacci number. This is true, especially for the Fibonacci sequence. But I do not know whether this observation is worthless. We do not know n, and our task is to find F_1, F_0, so I think we got nothing.

Well, you are looking for the longest sequence, that means you want to maximize n .

Create a fibonacci number lookup table. Start with the largest n , such as Fib_n <= F_n , the previous entry in the fib_n{n-1} table fib_n{n-1} . Now the only variables are F_1 and F_0 . Solve the linear Diophantine equation . If you have a solution, you are done. If not, decrease n by 1 and try again until you find a solution.

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

Answer 5

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

Since raising a matrix to a power is O (log n) (assuming that the multiplication of integers is O (1)), you can do the whole calculation in O (log n) until the matrix coefficients begin to dominate the calculation.

I don’t know how large the numbers you work with are, 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 approximately 200 million digits).