Project Euler Q2 :: Even Fibonacci numbers

Explanation. Standard caveat: don’t look here if you are trying to do these yourself.

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.

Getting a little trickier already. I initially attempted this one by a recursive brute-force search of each step in the sequence;

## recursively define the Fibonacci sequence
fibonacci <- function(x) {
   y <- ifelse(x > 1, fibonacci(x-1)+fibonacci(x-2), x)

## values in fibonacci < 4e6
z <- 4e6L
## check i=20,30,40
fibonacci(20) # 6765
fibonacci(30) # 832040
fibonacci(40) # takes too long

But of course these solutions are supposed to be calculable in about a minute so I’ve taken a wrong turn.

It quickly became obvious that I was needlessly re-calculating each step to add another, which is silly, as this explicitly needs all of them each time. I decided to store the sequence as a data.frame to keep the iteration number alongside it. Note that I use the more correct definition of the sequence which starts with 1, 1, 2. That’s not going to be an issue here, as we’re summing the even values anyway.

## this is silly, why recompute every time?
fibonacci.seq <- data.frame(n=integer(), f=integer())
fibonacci.seq[1,] <- c(1,1)
fibonacci.seq[2,] <- c(1,1)
w <- 2
f <- fibonacci.seq$f[w]
while(f < z) {
 w <- w + 1
 fibonacci.seq[w,] <- data.frame(n=w, f=fibonacci.seq$f[w-1]+fibonacci.seq$f[w-2])
 f <- fibonacci.seq$f[w]

## sum of even values
sum(fibonacci.seq[fibonacci.seq$f %% 2 == 0, "f"]) # 4613732


Leave a Reply