Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
    
@RossMillikan...got it –  rock321987 Oct 23 '13 at 11:06
add comment

2 Answers

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|improve this answer
    
Is the PDF in the link really freely available or is it a copyright violation? –  lhf Apr 29 at 12:13
    
I'll change the link, since I am not sure. –  adijo Apr 29 at 12:20
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.