6

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?

Improve this question
7
  • How about F_1 = F_n and F_0 = 0? You get the smallest possible F_0! Commented Apr 14, 2012 at 14:33
  • @Shahbaz: but not the longest sequence. Commented Apr 14, 2012 at 14:34
  • Do F_0 and F_1 have to be nonnegative? Commented Apr 14, 2012 at 14:37
  • @oldboy, yes, I should have written this Commented Apr 14, 2012 at 14:39
  • (4,1,5,6,11,17) is longer than (1,5,6,11,17) ;) Commented Apr 14, 2012 at 15:23

5 Answers 5

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

@Karoly Horvath: this is not the longest Fibonacci-like sequence that ends in 101.
Proof is left as an exercise for the reader Don't say this if you're just guessing, and you are, because [11, 1, 12, 13, 25, 38, 63, 101] is better than [9, 7, 16, 23, 39, 62, 101]. It creates a never-ending headache for those of us knowledgeable enough to use it responsibly.
@oldboy You are right, I thoight I have a proof but apparently it's full of holes.
It is on the other hand a very good approximation - I tested all the numbers from 10 to 1000 and it was never more than 1.5 away from the best second last element.
It turns out that this formula: F_{n-1} = round(F_n/φ) is absolutely correct. Every sequence with 'Fibonacci rule' that is F_n=F_{n-1}+F_{n-2} satisfy: lim n to infty F_{n+1}/F_n = φ. This follows directly from the generating functions of these sequences.
|
2

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).

Improve this answer

2 Comments

Bonus: you can use Cassini's identity to avoid implementing extended Euclidean GCD.
It's very hard to code, but I think the best approach, at least I like it the most.
2

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

Improve this answer

6 Comments

I'm terribly sorry, I simply did not sleep too well and didn't wrote strctly.. "The longest sequence" I mean the sequence end at given F_n. Simply, value n (which we do not know, I introduced it for better understanding) must be the highest.
altough he didn't mention it I'm sure he is looking for non-negative integers
Yes, so you go "backwards" from n, and you find there is no "highest" n, such that the sequence stop.
It's an easy guess that this would be defined over the whole numbers, so 0 < F(0) <= F(1). And by adding the constraint that the sequence be as long as possible, the difference between F(0) and F(1) should be minimized, subject to the final result coming out. And F(0) should be as small as possible. Given all that there is a longest sequence (possibly more than one); and there are not infinitely many valid sequences.
@DRVic, exactly.. And if there exist more than one sequence we must take this with the smallest F_0. F_n are non-negative integers..
|
2

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.

Improve this answer

1 Comment

((Shahbaz quipped the solution from the note 21 mins before this post - which doesn't mean (s)he(never mind the facial hair) observed it first.) If only you managed to allow for F_1 < F_0 …
0

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).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.