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)
   return(y)
}

## values in fibonacci < 4e6
z <- 4e6L
## check i=20,30,40
fibonacci(20)
## [1] 6765
fibonacci(30) # takes over 8 seconds
## [1] 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]
}
head(fibonacci.seq)
##   n f
## 1 1 1
## 2 1 1
## 3 3 2
## 4 4 3
## 5 5 5
## 6 6 8
tail(fibonacci.seq)
##     n       f
## 29 29  514229
## 30 30  832040
## 31 31 1346269
## 32 32 2178309
## 33 33 3524578
## 34 34 5702887
## sum of even values
sum(fibonacci.seq[fibonacci.seq$f %% 2 == 0, "f"])
## [1] 4613732
### CORRECT

devtools::session_info()

## ─ Session info ──────────────────────────────────────────────────────────
##  setting  value                       
##  version  R version 3.5.2 (2018-12-20)
##  os       Pop!_OS 19.04               
##  system   x86_64, linux-gnu           
##  ui       X11                         
##  language en_AU:en                    
##  collate  en_AU.UTF-8                 
##  ctype    en_AU.UTF-8                 
##  tz       Australia/Adelaide          
##  date     2019-08-13                  
## 
## ─ Packages ──────────────────────────────────────────────────────────────
##  package     * version date       lib source                           
##  assertthat    0.2.1   2019-03-21 [1] CRAN (R 3.5.2)                   
##  backports     1.1.4   2019-04-10 [1] CRAN (R 3.5.2)                   
##  blogdown      0.14.1  2019-08-11 [1] Github (rstudio/blogdown@be4e91c)
##  bookdown      0.12    2019-07-11 [1] CRAN (R 3.5.2)                   
##  callr         3.3.1   2019-07-18 [1] CRAN (R 3.5.2)                   
##  cli           1.1.0   2019-03-19 [1] CRAN (R 3.5.2)                   
##  crayon        1.3.4   2017-09-16 [1] CRAN (R 3.5.1)                   
##  desc          1.2.0   2018-05-01 [1] CRAN (R 3.5.1)                   
##  devtools      2.1.0   2019-07-06 [1] CRAN (R 3.5.2)                   
##  digest        0.6.20  2019-07-04 [1] CRAN (R 3.5.2)                   
##  evaluate      0.14    2019-05-28 [1] CRAN (R 3.5.2)                   
##  fs            1.3.1   2019-05-06 [1] CRAN (R 3.5.2)                   
##  glue          1.3.1   2019-03-12 [1] CRAN (R 3.5.2)                   
##  htmltools     0.3.6   2017-04-28 [1] CRAN (R 3.5.1)                   
##  knitr         1.24    2019-08-08 [1] CRAN (R 3.5.2)                   
##  magrittr      1.5     2014-11-22 [1] CRAN (R 3.5.1)                   
##  memoise       1.1.0   2017-04-21 [1] CRAN (R 3.5.1)                   
##  pkgbuild      1.0.4   2019-08-05 [1] CRAN (R 3.5.2)                   
##  pkgload       1.0.2   2018-10-29 [1] CRAN (R 3.5.1)                   
##  prettyunits   1.0.2   2015-07-13 [1] CRAN (R 3.5.1)                   
##  processx      3.4.1   2019-07-18 [1] CRAN (R 3.5.2)                   
##  ps            1.3.0   2018-12-21 [1] CRAN (R 3.5.1)                   
##  R6            2.4.0   2019-02-14 [1] CRAN (R 3.5.1)                   
##  Rcpp          1.0.2   2019-07-25 [1] CRAN (R 3.5.2)                   
##  remotes       2.1.0   2019-06-24 [1] CRAN (R 3.5.2)                   
##  rlang         0.4.0   2019-06-25 [1] CRAN (R 3.5.2)                   
##  rmarkdown     1.14    2019-07-12 [1] CRAN (R 3.5.2)                   
##  rprojroot     1.3-2   2018-01-03 [1] CRAN (R 3.5.1)                   
##  sessioninfo   1.1.1   2018-11-05 [1] CRAN (R 3.5.1)                   
##  stringi       1.4.3   2019-03-12 [1] CRAN (R 3.5.2)                   
##  stringr       1.4.0   2019-02-10 [1] CRAN (R 3.5.1)                   
##  testthat      2.2.1   2019-07-25 [1] CRAN (R 3.5.2)                   
##  usethis       1.5.1   2019-07-04 [1] CRAN (R 3.5.2)                   
##  withr         2.1.2   2018-03-15 [1] CRAN (R 3.5.1)                   
##  xfun          0.8     2019-06-25 [1] CRAN (R 3.5.2)                   
##  yaml          2.2.0   2018-07-25 [1] CRAN (R 3.5.1)                   
## 
## [1] /home/jono/R/x86_64-pc-linux-gnu-library/3.5
## [2] /usr/local/lib/R/site-library
## [3] /usr/lib/R/site-library
## [4] /usr/lib/R/library


rstats 

See also