4

The definition of the Fibonacci numbers is given by:

$$\begin{align}f_1 &= 1;\\ f_2 &= 2;\\ f_n &= f_{n-1} + f_{n-2},\qquad (n >= 3); \end{align}$$

now we are given two numbers $a$ and $b$, and we have to calculate how many Fibonacci numbers are in the range $[a,b]$. How can we calculate it?

Daniel Fischer
  • 206,697
rock321987
  • 345
  • Naively just compute all Fibonacci numbers smaller or equal to $b$ and count. Maybe you should clarify what you mean by 'calculate'. A closed form dependent on $a$ and $b$ will probably not exist. – Simon Markett Oct 23 '13 at 10:22
  • Your definition of Fibonacci numbers is off by one from the standard indexing. Normally $f_2=1, f_3=2$. My answer uses the standard indexing. The final answer doesn't change as we are subtracting two indices. – Ross Millikan Oct 23 '13 at 10:43
  • 'calculate'means total fibonacci numbers between the range... – rock321987 Oct 23 '13 at 11:05
  • @RossMillikan...got it – rock321987 Oct 23 '13 at 11:06

2 Answers2

8

We know that $F_n\approx \frac {\phi^n}{\sqrt 5}$, so given $a$, the next larger Fibonacci number is $F_k$, where $k= \left \lceil\frac {\log (a\sqrt 5)}{\log \phi }\right \rceil$. Similarly the $F_m$ below $b$ is $m= \left \lfloor\frac {\log (b\sqrt 5)}{\log \phi }\right \rfloor$, then there are $m-k+1$ between $a$ and $b$. You have to think about what you want if $a$ or $b$ are themselves Fibonacci numbers.

Ross Millikan
  • 374,822
1

This question is asked in Skiena's programming challenges. Now, to find the $ n^{\text{th}} $ fibonacci number, we have the following closed form expression.

$$ \Large F(n) = \dfrac{1}{\sqrt{5}} \left( \left( \dfrac{1 + \sqrt{5}}{2}\right)^n - \left( \dfrac{1 - \sqrt{5}}{2} \right)^n\right) $$

Now, given $ F(n) $, we can find approximately the index of the closest fibonacci number to it. Therefore, we find one $ n_1 $ such that $ F(n_1) = a $ and another $n_2 $ such that $ F(n_2) = b $. Then our answer is $\mathsf{round(n_2)} - \mathsf{round(n_1)}$ where $ \mathsf{round(x)} $ find the nearest integer to $ x $.

adijo
  • 438