How to Calculate the Length of the nth Fibonacci Number (or Lucas Number)
The Fibonacci sequence is defined by the recursive relation F(n+2) = F(n+1) + F(n), where F(0) = 0 and F(1) = 1. The terms of the sequence up to n = 20 are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765. The closely related Lucas sequence is defined by the same recursion L(n+2) = L(n+1) + L(n) except with different initial conditions, L(0) = 2 and L(1) = 1.
While it is possible to compute each successive term using recursion, there is a faster way to compute the nth term of each sequence with explicit formulas for F(n) and L(n), the Binet Formulas.
Knowing the Binet Formulas also allows you to find the number of digits in each term of the Fibonacci sequence or Lucas series, without having to compute the nth term. The equations are given below, or you can use the calculator on the left to find the length of the nth Lucas or Fibonacci number.
The Binet FormulaLet φ be the golden section equal to [1+sqrt(5)]/2. Then the explicit formula for F(n) is
F(n) = [ φn - (-1/φ)n ]/sqrt(5)
This is classically known as the Binet formula, named after the French mathematician Jacques Binet. The formula was actually discovered much earlier by Euler and de Moivre. For the Lucas numbers, the explicit formula for L(n) is very similar:
L(n) = φn + (-1/φ)n
Length of a Fibonacci NumberIn base-10, the number of digits in an integer p is given by the formula
D(p) = ⌊log10(p) + 1⌋
D(p) = ⌊ln(p)/ln(10) + 1⌋
Let D(F(n)) be the length the nth Fibonacci number and D(L(n)) be the length of the nth Lucas Number. Then we have
⌊log10([ φn - (-1/φ)n ]/sqrt(5)) + 1⌋
≈ ⌊n⋅log10(φ) - log10(5)/2 + 1⌋
⌊log10(φn + (-1/φ)n) + 1⌋
≈ ⌊n⋅log10(φ) + 1⌋
© Had2Know 2010