Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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 it – rock321987 Oct 23 '13 at 11:06
up vote 1 down vote accepted

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

share|cite|improve this answer
Is the PDF in the link really freely available or is it a copyright violation? – lhf Apr 29 '14 at 12:13
I'll change the link, since I am not sure. – adijo Apr 29 '14 at 12:20

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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