Problem 025: 1000-digit Fibonacci Number

From Project Euler:

The Fibonacci sequence is defined by the recurrence relation:

$Fn = F_{n−1} + F_{n−2}$, where $F_1 = 1$ and $F_2 = 1$.
Hence the first 12 terms will be:

$F_1 = 1$
$F_2 = 1$
$F_3 = 2$
$F_4 = 3$
$F_5 = 5$
$F_6 = 8$
$F_7 = 13$
$F_8 = 21$
$F_9 = 34$
$F_{10} = 55$
$F_{11} = 89$
$F_{12} = 144$

The 12th term, $F_{12}$, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

This problem can be solved analytically, and so runs in constant time. It all starts with Binet's formula, which states that the $n$th Fibonacci number $F_n$ has the expression:

$F_n = \frac{\phi^n - (-\phi)^{-n}}{2\phi - 1}$
where $\phi = \frac{1 + \sqrt{5}}{2}$

We're looking for the first one that has at least $d$ digits, so we want:

$\log_{10}(F_n) \ge d$
$\log_{10}\left( \frac{\phi^n - (-\phi)^{-n}}{2\phi - 1} \right) \ge d$

We want to get a closed-form expression for $n$ in terms of $d$, which is a challenge with this formula (if possible at all). Instead though if we realize that $(-\phi)^{-n}$ diminishes very quickly, we can do an optimization:

$\frac{\phi^n - (-\phi)^{-n}}{2\phi - 1} \approx \frac{\phi^n}{2\phi - 1}$ for larger $n$

This can give us a closed-form expression for $n$ in terms of $d$:

$n = \lceil \frac{d + \log(2\phi - 1)}{log(\phi)} \rceil$

Translating from math to Clojure:

(defn min-digits-fibonacci
  "Gets the first Fibonacci number with the specified number of digits."
  [num-digits]
  (let [phi (/ (+ 1.0 (Math/sqrt 5.0)) 2.0)]
    (int (Math/ceil (/ (+ (- num-digits 1)
                          (Math/log10 (- (* 2.0 phi) 1.0)))
                       (Math/log10 phi))))))

As expected, this runs very quickly:

$ lein run
Processing...
Index is: 4782
"Elapsed time: 2.180435 msecs"