Project Euler, Problem 2 Generalized

Project Euler, problem 2 involves the Fibonacci sequence. Specifically: find the sum of the even-valued Fibonacci numbers which do not exceed four million.

One way to tackle this is to generate all the Fibonacci numbers and check for divisibility while accumulating. However a look at the Fibonacci sequence might reveal a better way:*



There is obviously a pattern: every third number (beginning with 0) is divisible by 2. Furthermore, every fourth number is divisible by 3, every fifth number is divisible by 5, every sixth number is divisible by 8 etc. In fact, this pattern of divisibility continues for all the Fibonacci numbers. (The proof is left as an exercise to the reader.)

This suggests that we can create formulae which generate sequences of these divisible numbers. It is easiest to do this by generating pairs of numbers; e.g. 2,3;8;13;34,55 for the case of 2, etc. If we label the divisible Fibonacci number E, and the next Fibonacci N (“E” for “even” in the original problem and “N” for “next”), we get the following formulae. It is easy to see how the Fibonacci sequence has been smuggled in as the coefficients of the functions.

2: E+2N, 2E+3N
3: 2E+3N, 3E+5N
5: 3E+5N, 5E+8N
Etc.

So we can use these coefficients to construct a generator for a particular subset of the Fibonacci numbers. For example here is a generator for the sequence in the original problem. (As always, this code is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

let euler2 n = 

  let rec fib e o =

    seq {

      yield e

      yield! (fib (e+o*2) (e*2+o*3)) }

  fib 0 1

  |> Seq.takeWhile ((>) n)

  |> Seq.sum

let x = euler2 4000000       

This is obviously easy to generalize, based on the coefficients:

let euler2WithCoefficients (c0,c1) = 

  let rec fib e o =

    seq {

      yield e

      yield! (fib (c0*e+c1*o) (c1*e+(c0+c1)*o)) }

  fib 0 1

And it can be further generalized, based on an internal generalization of the coefficients (e.g. the Fibonacci sequence – I used a simple, stack-based fib to make the code simpler). Here is a solution to the original problem using this last generalization.

let euler2General n = 

  let rec fib = function

    | 0 -> (0,1)

    | n -> 

      let f,s = fib (n-1)

      s,(f+s)

  if n<=0 then failwith "n must be greater than zero."

  let c0,c1 = (fib (n-1))

  let rec fibseq e o =

    seq {

      yield e

      yield! (fibseq (c0*e+c1*o) (c1*e+(c0+c1)*o)) }

  fibseq 0 1

let euler2Solution = 

  euler2General 3 // Remember, fib #3, not div by 3!

  |> Seq.takeWhile ((>) 4000000) 

  |> Seq.sum 

And of course, this is a generalization based on offsets in the Fibonacci sequence; it can only be used for divisibility by numbers actually in the Fibonacci sequence.

So how well does this meet with my ideal of “fluent” code, or “code so obviously like the problem and solution that domain expert can understand it”? Well, it is more complicated and difficult than Project Euler problem 1, but a lot of the complexity above comes from the formula which yields Fibonacci-divisible numbers. A straightforward solution to the specifics of problem 2, testing for divisibility, is simpler. But when you think about it, analysis like that above is part of the knowledge base of most domains, so experts may already be more familiar with those analyses than with naïve solutions.

For more on the Euler problems in F# (and other interesting stuff), I commend you to the ongoing series and comments at Mark Pearl's blog.

-Neil

*I chose to begin the Fibonacci sequence at 0,1 and to begin the indexing at 0. I just find this simpler Plus, it has the appealing set of coincidences that Fibonacci 1 is 1, 5 is 5, 10 is 55, and 12 is 144!. The ideas delineated above also work with other foundations and indexing sequences if the appropriate adjustments are made.