# How many numbers are in the Fibonacci sequence

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"?

-
If you use the closed-form expression for the Fibonacci numbers it should be easy enough. –  TMM Sep 26 '11 at 16:19
Let's clarify: you're asking how many numbers less than or equal to a given number are Fibonacci? –  Ｊ. Ｍ. Sep 26 '11 at 16:19
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

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.

-
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
@Ross, $(-\phi)^{-1}$ is the same as $\psi = 1-\phi$. –  Srivatsan Sep 26 '11 at 16:39
@Ross: but I like the form that shows off $\phi$ nicely... ;) –  Ｊ. Ｍ. Sep 26 '11 at 16:53
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

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

-

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

-
We can get explicit formula using $\log$ and floor (or nearest integer) functions. –  André Nicolas Sep 26 '11 at 16:32
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