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"?
Best Answer
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.