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"

Problem 002: Even Fibonacci Numbers

From Project Euler:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

There are typically two ways to work with Fibonacci numbers. You can either use the formula to generate the nth Fibonacci number, a formula that involves taking powers of the golden ratio $\phi$; or you can just simply start from the beginning and iterate through them.
For this one, we'll iterate through and accumulate values as we go along. A simple approach here would be to generate the list of Fibonacci numbers that are less than 4 million, filter out the odd ones, then reduce the list. Something like this:

(<<- (gen-fibs-to 4000000)
     (filter even?)
     (reduce +))

This has a time complexity of O(n), but it also has a space complexity of O(n). We can do better than that. Instead of first generating all the Fibonacci numbers, we can instead just stream through, accumulating values as we need to. A common pattern to do this is to define a local function that accepts an accumulator value, and add the even numbers to it. We quit when we've passed our limit.

(defn sum-even-fibs [n]
  (letfn [(accum [a b sum n]
            (if (>= b n)
              sum  ; we've passed the limit, return the total
              (accum b (+ a b)
                     (+ sum (if (even? b) b 0))
                     n)))]
    (accum 1 2 0 n)))

(println (sum-even-fibs 4000000))

Running this program gives us the correct answer very quickly (note that on my machine the JVM takes about 1.5s to start up):

$ time clj 2.clj 
4613732

real 0m1.532s
user 0m3.136s
sys 0m0.096s