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$
7
  • $\begingroup$ Isn't it one longer if you start with $a_0=2$, $a_1=0$? $\endgroup$
    – HSN
    Jul 1, 2013 at 13:44
  • 1
    $\begingroup$ It should be Fibonacci-like so a(0) <= a(1) <= a(2) <= ... <= a(n) $\endgroup$
    – Kostek
    Jul 1, 2013 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$ Jul 1, 2013 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, 2013 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, 2013 at 13:47

5 Answers 5

7
$\begingroup$

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

$\endgroup$
8
  • $\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, 2013 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, 2013 at 13:59
  • $\begingroup$ you mean 1.618... ? $\endgroup$
    – Kostek
    Jul 1, 2013 at 14:08
  • $\begingroup$ Yes, that's the one. $\endgroup$
    – Empy2
    Jul 1, 2013 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$ Jul 1, 2013 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .