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.

Assuming I'm asked to generate Fibonacci numbers up to N, how many numbers will I generate? I'm looking for the count of Fibonacci numbers up to N, not the Nth number.

So, as an example, if I generate Fibonacci numbers up to 25, I will generate:

  • 1, 1, 2, 3, 5, 8, 13, 21
  • that's 8 numbers

How do I calculate this mathematically for an arbitrary "n"?

share|improve this question
    
If you use the closed-form expression for the Fibonacci numbers it should be easy enough. –  TMM Sep 26 '11 at 16:19
1  
Let's clarify: you're asking how many numbers less than or equal to a given number are Fibonacci? –  J. M. Sep 26 '11 at 16:19
3  
Maybe you could look up the formula called Binet's Formula. –  André Nicolas Sep 26 '11 at 16:19
    
With regards to the closed-form expression, such a formula you can see here: en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression –  Ilya Sep 26 '11 at 16:20
add comment

3 Answers 3

up vote 12 down vote accepted

As mentioned in the comments, Binet's formula,

$$F_n=\frac1{\sqrt{5}}(\phi^n-(-\phi)^{-n})$$

where $\phi=\frac12(1+\sqrt 5)$ is the golden ratio, is a closed-form expression for the Fibonacci numbers. See this related question for a few proofs.

As for counting how many Fibonacci numbers are there that are less than or equal to a given number $n$, one can derive an estimate from Binet's formula. The second term in the formula can be ignored for large enough $n$, so

$$F_n\approx\frac{\phi^n}{\sqrt{5}}$$

Solving for $n$ here gives

$$n=\frac{\log\,F_n+\frac12\log\,5}{\log\,\phi}$$

Taking the floor of that gives a reasonable estimate; that is, the expression

$$\left\lfloor\frac{\log\,n+\frac12\log\,5}{\log\,\phi}\right\rfloor$$

can be used to estimate the number of Fibonacci numbers $\le n$. This is inaccurate for small $n$, but does better for large $n$.


It turns out that by adding a fudge term of $\frac12$ to $n$, the false positives of the previous formula disappear. (Well, at least in the range I tested.) Thus,

$$\left\lfloor\frac{\log\left(n+\frac12\right)+\frac12\log\,5}{\log\,\phi}\right\rfloor$$

gives better results.

share|improve this answer
    
Nicely put. This is essentially mentioned in en.wikipedia.org/wiki/Fibonacci_number#Computation_by_rounding. –  lhf Sep 26 '11 at 16:36
    
Your second $\phi$ should be $1-\phi=\psi$ –  Ross Millikan Sep 26 '11 at 16:36
2  
@Ross, $(-\phi)^{-1}$ is the same as $\psi = 1-\phi$. –  Srivatsan Sep 26 '11 at 16:39
1  
@Ross: but I like the form that shows off $\phi$ nicely... ;) –  J. M. Sep 26 '11 at 16:53
1  
One caveat of this solution is that for large $n$ you may need a very good approximation of $\phi$. –  lhf Sep 26 '11 at 17:37
show 5 more comments

Assuming we take $F_0=0$ and $F_1=1$, for all $n\geq 0$, the value of the $F_n$ is the nearest integer to $\frac{\phi^n}{\sqrt{5}}$, where $\phi = \frac{1+\sqrt{5}}{2}$.

So, the number of Fibonnaci numbers less than $N$ is the number of $n\geq 0$ such that:

$$ \frac{\phi^n}{\sqrt{5}} \leq N+\frac{1}{2}$$

Solving this, we see that $n \leq \log_\phi(\sqrt{5}(N+\frac{1}{2}))$. That means that the number of $n$ is:

$$1+\lfloor{\log_\phi(\sqrt{5}(N+\frac{1}{2}))}\rfloor$$

share|improve this answer
add comment

I don't think you will be able to find a closed-form formula for the number of Fibonacci numbers less than $N$ - if you had chosen $N = 26$ instead of $N = 25$, you would have gotten the same answer, but if you had set $N = 34$, the answer would have suddenly jumped to $9$. As has been suggested before, you can use Binet's formula:

nth Fibonacci number $F_n= (\phi^n - (-\phi)^{-n})/(\sqrt 5)$ where $\phi = (1 + (\sqrt 5))/2$

Simply plug in values of $n$ until $F_n > N$; then the number you are looking for is $n-1$.

share|improve this answer
2  
We can get explicit formula using $\log$ and floor (or nearest integer) functions. –  André Nicolas Sep 26 '11 at 16:32
1  
The second $\phi$ should be $\psi=\frac{1-\sqrt{5}}{2}$. This is less than $1$ in absolute value and can be ignored for reasonable $n$ –  Ross Millikan Sep 26 '11 at 16:34
    
I corrected the answer according to Binet's formula: mathworld.wolfram.com/BinetsFibonacciNumberFormula.html –  Beni Bogosel Feb 25 '12 at 8:45
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.