15
$\begingroup$

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

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

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.

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

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ We can get explicit formula using $\log$ and floor (or nearest integer) functions. $\endgroup$ – André Nicolas Sep 26 '11 at 16:32
  • 1
    $\begingroup$ 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$ $\endgroup$ – Ross Millikan Sep 26 '11 at 16:34
  • $\begingroup$ I corrected the answer according to Binet's formula: mathworld.wolfram.com/BinetsFibonacciNumberFormula.html $\endgroup$ – Beni Bogosel Feb 25 '12 at 8:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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