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;

[code language=“r”]

recursively define the Fibonacci sequence

fibonacci <- function(x) { y <- ifelse(x > 1, fibonacci(x-1)+fibonacci(x-2), x) return(y) }

values in fibonacci < 4e6

z <- 4e6L

check i=20,30,40

fibonacci(20) # 6765 fibonacci(30) # 832040 fibonacci(40) # takes too long [/code]

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.

[code language=“r”]

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] } fibonacci.seq

sum of even values

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




See also