Euler 101

We are given a “true” sequence, that can be generated by:

generator <- function(n){
  1-n+n^2-n^3 + n^4 - n^5 + n^6 - n^7 + n^8 - n^9 + n^10
}

We collect that in a dataframe.

sekvens <- generator(1:11)
data <- data.frame(x = 1:11, y = sekvens)

Construct a generating function, OP(k,n), that correctly generates the first k terms of the sequence. Which n is the first where OP(k,n) does not correctly generate the value of the “true” sequence. That is, OP(2,n) correctly generate the first 2 terms of the “true” sequence, but for n = 3, it does not. Or, it might, but we are interested in the first n of OP(2,n) that does not do that. Having found that, we calculate the value of OP(n,2).

The answer is found as the sum of those values.

We do that by generating the polynomic expansion of x to the k-1 th degree, and fit that to the first k elements of the true sequence. That fit is then used to predict the values for the entire sequence (and an extra step). The first, that is the lowest, value in that prediction that is not equal to the true sequence, is the first that does not fit. The polynomial expansion cannot handle k = 1. But as that will simply repeat the number 1, and therefore the first term that does not fit the true sequence - will be one.

fits <- function(k){
  if(k == 1){return(1)}
  bop <- lm(y ~ poly(x, k-1, raw = TRUE), data[1:k,])
  test <- round(predict(bop, newdata = data.frame(x = 1:11)), digits = 2)
  min(test[!(test[1:11] == sekvens[1:11])])
}

We now have a function that we can use to find the first term that does not fit the true sequence for k = 1:10. The solution with the polynomial expansion cannot handle k = 1. But that will simply repeat the number 1, and the first term that does not fit - will be one.

answer <- sum(sapply(1:10, FUN= fits))