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] 6765fibonacci(30) # takes over 8 seconds## [1] 832040# fibonacci(40) # takes too longBut 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 8tail(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