Fibonacci-like sequence Today I have to deal with something which reminds Fibonacci sequence. Let's say I have a certain number k, which is n-th number of certain sequence. This sequence however is created by recursive formula that we know from Fibonacci $a(n) = a(n-1) + a(n-2)$, where $n \ge 2$ and $a(0) \le a(1) \le \dots \le a(n)$. So let's say $a(n) = k$. Now I have to find $a(0)$, $a(1)$ that are initial number of this sequence, however the sequence should be longest possible and in case there are many of them which are of the same length $a(0)$ should be smallest possible. Some example:
$k = 10$
I can simply say $a(0) = 0$, $a(1) = 10$ so $a(n) = k$ is a part of this sequence since $a(0) + a(1) = a(2) = 10$. But it's not the longest possible. For instance choose $a(0) = 0$, $a(1) = 2$, now $a(2) = 2$, $a(3) = 4$, $a(4) = 6$, $a(5) = 10$, it's also valid sequence and length is $6$ and as far as I know it cannot be longer.
Any idea how to do so for any $k$? Might be math formula or some algorithm.
 A: My guess is to pick $a(n-1)$ so that $a(n)/a(n-1)$ is close to the Fibonacci ratio.
A: As Michael says, look at the sequence in the other way : the reverse of a Fibonacci sequence satisfies the recurrence relation $a(n) = a(n+1) + a(n+2)$, or $a(n+2) = a(n)-a(n+1)$.
Pick $a(0) = k$. You want to choose a value for $a(1)$ such that when you define $a(n+2) = a(n) - a(n+1)$, you get the longest possible streak of positive integers.
Define $b(n) = a(n+1)/a(n)$. Then $b(n+1) = 1/b(n)-1$. $a(n)$ gets negative when $b(n-1)$ gets negative, so you want to pick $a(1)$ (and so $b(0)$) such that the sequence $b(n)$ is positive as much as possible.
You obtain such a sequence by choosing $b(0)$ as close to $1/\phi = \frac {\sqrt 5-1} 2$ as possible :
let $f(x) = 1/x-1$. Then $f \circ f(x) = (2x-1)/(1-x)$, which is increasing from $(0;1)$ to $(-1;\infty)$, and you want the sequence to stay inside $(0;1)$ for as long as possible.
$f$ has its only fixpoint at $1/\phi$ so this is where you want to start.
Hence you must pick either $a(1) = \lfloor a(0)/\phi \rfloor$ or $a(1) = \lceil a(0)/\phi \rceil$. Choose whichever gives you the longest positive sequence.
A: I will assume that $a(0), a(1)$ must be nonnegative integers; otherwise there is no maximum length.
These are known to have the form $$a(n)=\alpha \phi^n + \beta \psi^n$$
where $\alpha,\beta$ are real numbers depending on the initial conditions, $\phi=\frac{1+\sqrt{5}}{2}$, and $\psi=\frac{1-\sqrt{5}}{2}$.  Because $|\psi|<1$, the $\beta \psi^n$ term has vanishingly small absolute value, hence $a(n)\approx[\alpha \phi^n]$, where $[\cdot]$ denotes rounding to the nearest integer, and the approximation is exact for all but finitely many $n$.
Hence a good approximation for the desired $n$ for which $a(n)=k$ is $$\frac{\ln k}{\ln \phi}\approx 2.078 \ln k$$
A procedure, also suggested by Michael, to produce such starting values (I don't have a closed form) is to reverse-engineer this process.  Suppose we have $k=100$.  Then $\frac{k}{\phi}\approx 61.8$.  Hence I'd recommend the sequence, in reverse, begins with $100, 62$.  Having two terms we may continue as $100,62,38,24,14,10,4$.  This has length $7$, while my estimate is $9.57$.  
A: By brute force, for $0 \leq k < 10^5$ the distance between the optimal choice of $a(n-1)$ and $k/\phi$ is always in the range $\pm 0.72$, and is within 0.5 around 90% of the time.  So if you need precise answers it might be worthwhile to get a theoretical bound on this error, which would let you just check three or so possible values for $a(n-1)$ at most.  I'd imagine getting an exact expression would be quite difficult.
A: I admit this require a list of fibinocci numbers but more accurate method:
if are given a number k, choose largest possible two consecutive fibinacci no's $a_{k},a_{k+1}$ such that,$a_k<a_{k+1}$ and $a_k+a_{k+1}<k$.
if you can form a diphontine,$$a_k.x+a_{k+1}.y=k(x<y)$$then a(0)=x,a(1)=y
e.g.,
if k=30 fibinacci numbers less than thirty are (1,1,2,3,5,8,13,21)
series 1: s
$$3(6)+2(6)=30$$
So,check $$6,6,6+6,12+6,18+12=30$$ 
series 2:
$$3(8)+2(3)=30$$
so,$$3,8,11,19,30$$
remember 100th fibinacci number contain 21 digits you have to check 99(relatively small) combinations for such large number
