Problem 122

• Problem 122 - PukiWiki

さっぱり解ける気がしないので色々調べている過程でKnuthのpower tree methodというものの存在を知った．それでどうにか理解したものの残念なことにこの問題を単純なpower treeで解くことはできない．
結局Evaluation of Powers | COME ON CODE ONにあるアルゴリズムを使ったのだが，δ_nを計算するときに使っているリストがどのようにして求められているのか，なぜこのリストが必要なのかを理解できていない．とりあえず30msで答えは出たけど今ひとつという感じは否めない．

library(gmp)
limit <- 200
I <- numeric(limit)
lambda <- numeric(limit)
v <- numeric(limit)
lambda[1] <- 0
v[1] <- 1
for(i in 1:limit){
  lambda[2*i] <- lambda[2*i+1] <- lambda[i]+1
  v[2*i] <- v[i]
  v[2*i+1] <- v[i]+1
}
I <- lambda + v -1
lambda[1:200]
floor(log(1:200, 2))
t <- c(23, 43, 59, 77, 83, 107, 149, 163, 165, 179)
for(i in 2:limit){
  if(isprime(i)){
    l <- Inf
  }else{
    p <- as.numeric(min(factorize(i)))
    l <- I[p] + I[i/p]
  }
  if(is.element(i, t)){
    delta <- 1
  }else{
    delta <- 0
  }
  I[i] <- min(I[i-1]+1, l) - delta
}
sum(I[1:200])