7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't it one longer if you start with $a_0=2$, $a_1=0$? $\endgroup$ – HSN Jul 1 '13 at 13:44
  • 1
    $\begingroup$ It should be Fibonacci-like so a(0) <= a(1) <= a(2) <= ... <= a(n) $\endgroup$ – Kostek Jul 1 '13 at 13:45
  • $\begingroup$ What's wrong with $a(0)=0,a(1)=1$ for k=2? I'm not sure there is a pattern to finding the smallest $a(0),a(1)$ which can yield k$. If the number is a fibonacci number, then that sequence is the longest to reach that number. $\endgroup$ – Foo Barrigno Jul 1 '13 at 13:45
  • $\begingroup$ Might be good to add that condition. I just read Fibonacci-like as satisfying $a_n=a_{n-1}+a_{n-2}$. $\endgroup$ – HSN Jul 1 '13 at 13:46
  • $\begingroup$ @FooBarrigno About k = 2 I have made a mistake, so remove it you right those are correct answer but still I don't know how to reverse computing of it let's sat what's answer for 10^9-7 ? $\endgroup$ – Kostek Jul 1 '13 at 13:47
7
$\begingroup$

My guess is to pick $a(n-1)$ so that $a(n)/a(n-1)$ is close to the Fibonacci ratio.

$\endgroup$
  • $\begingroup$ Can you write something more, because don't really get it. Let's say I have following k = 123124123 how find a(0), a(1) with conditions stated in original post. $\endgroup$ – Kostek Jul 1 '13 at 13:50
  • $\begingroup$ Instead of guessing $a(0)$ and $a(1)$, start at the top. If you have $a(n)$ and $a(n-1)$, then you can find $a(n-2)=a(n)-a(n-1)$. Then you can find $a(n-3)$ and so on, each is the difference of the two before. Eventually you will hit negative numbers, so you stop. There is a ratio that Fibonacci numbers approach; do you know it? $\endgroup$ – Empy2 Jul 1 '13 at 13:59
  • $\begingroup$ you mean 1.618... ? $\endgroup$ – Kostek Jul 1 '13 at 14:08
  • $\begingroup$ Yes, that's the one. $\endgroup$ – Empy2 Jul 1 '13 at 14:11
  • $\begingroup$ Not that it helps, but the smallest I could find for your number was $a(0)=435,a(1)=6683$, it has a length of 23. I found it using this approximation. My guess is that it's the unique longest sequence and I've chosen the smallest $a(0)$. In general, there may be more than one longest sequence, then you simply choose the smallest. The lengths of the sequences increased as $a(n-1)$ increased or decreased away from the estimate. $\endgroup$ – Foo Barrigno Jul 1 '13 at 14:17
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.