1のみからなる数(1, 11, 111, ...)をrepunitと呼び、k桁のrepunitをR(k)と表す。
R()について考える。
R(10), R(100), R(1000)は17で割り切れないが、R(10000)は17で割り切れる。一方、どのようなnをもってきてもR(
100,000未満の素数のうち、R(
pを素数とすると、定義からはpで割り切れる(c.f.Problem 129 - もうカツ丼でいいよな)。
またProblem 129で見たように、repunitを延長していくと剰余が循環するという性質から、xを正整数とすればもpで割り切れる。
ここでもし
となるようなx, nが存在するなら、R()はpで割り切れる。
またnより大きな任意の自然数mについてR()もpで割り切れる。
R(k)がpで割り切れるとき、となる(p=3をのぞく。c.f.Problem 132 - もうカツ丼でいいよな)。
そのため、もしR()がpで割り切れるならば、ある値より大きなmの全てについて
が成り立つ。
mの上界を適当に決めよう。
A(p)はp-1を割り切るのだから、最大でもp-1。そして今回pは未満なので、A(p)も
未満。
そこで、5桁の数qを何倍かしてにすることを考えよう。
手順としては、qを何倍かして最下位の桁を0にする、さらに何倍かして2桁目を0にする、さらに何倍かして…という感じで進めることを想定する。
この「何倍か」は少し考えると2か5でなければならないことが分かる。
5桁を0にあわせるには最大でも倍すればよい。ただ、そうすると4桁くらい桁が増えるので、それをあわせるのに
倍、さらにあふれた分を…
とやっていくとざっくり見積もって倍以内には
に到達できることが分かる。つまりxは
より小さく、
またpは10^5以下なので
左辺を適当にでっかくすると
というわけでmの上界は20と見積もれる。
とならないような未満の素数を足し合わせればよい。なお、3が例外であることに注意する(c.f.Problem 132 - もうカツ丼でいいよな)。3がR(
)の因数となりえないことは問題文中からも分かる。
library(gmp) limit <- 1e5 sieve <- logical(limit) sieve[1] <- TRUE sieve[seq(4, limit, by=2)] <- TRUE for(i in seq(3, sqrt(limit), by=2)){ if(!sieve[i]) sieve[seq(i*2, limit, by=i)] <- TRUE } p.list <- (1:limit)[!sieve] is.divide <- function(x){ powm(10, pow.bigz(10, 20), x) == 1 } tmp <- sapply(p.list, is.divide) sum(p.list[!tmp]) + 3
550ms。
