Problem 78 - Project Euler
引き続き分割数の問題。100万で割り切れる最初の分割数はなにか？という問題で、今度はすぐには答が出てこない。
15秒かかった。
Wikipedia(自然数の分割 - Wikipedia)見てこれなのでうむむ…
limit <- 1e6 pn.list <- numeric(limit) pn.list[1] <- 1 temp <- 1:limit lef <- (3*temp^2-temp)/2 rig <- (3*temp^2+temp)/2 lef <- lef[lef<limit] rig <- rig[rig<limit] pm <- (-1)^(temp+1) for(n in 2:limit){ pn.list[n] <- sum(pm[1:length(lef[lef<n])]*pn.list[n-lef[lef<n]], pm[1:length(rig[rig<n])]*pn.list[n-rig[rig<n]])%%1e6 if(pn.list[n]==0) break } n-1
