1のみを並べて作った数(1, 111, 1111111, ...etc.)をrepunitと呼ぶ。また、k桁のrepunitをR(k)で表すことにしよう。例えば、R(6) = 111111。
10と互いに素である自然数nを考えたとき、R(k)がnで割り切れる、というようなkが必ず存在することを示せる。nに対応する最小のkをA(n)で表すことにしよう。例えば、A(7) = 6、A(41) = 5。
A(n)が10を超える最初のnは17である。
A(n)が100万を超える最初のnはいくつか？
まず、R(k) mod nを計算することを考える。R(k)をつくってから剰余を計算する必要はなくて、単に一桁ずつ足しながら計算していけばよい。つまり、
A(n)を探索するためには、上の方法で剰余を計算しつつ、剰余が0となるまでR(k)を伸ばしていけばよい。
また、である。nで割ったときの剰余は0からn-1までのn通りしかありえないうえ、repunitは同じ数を付け加えて伸ばしていくだけなので剰余の出方は循環する。そのため、R(k)がnで割り切れるとき、そのようなkのうち最小のものがnを超えることはない。
よって、ある値xより大きなA(n)を与えるようなnを求めるなら、探索はx+1から開始すればよい。
…
まあ白状するとよく分からなかったのでググりましたが！！！
最初R(k) mod nを計算する関数つくって馬鹿正直にぐるぐる回してたらさっぱり終わらなかった。その場のノリでとりあえずつくってとりあえず回しちゃう前にちょっとくらい計算量を計算する癖をつけたい。
A <- function(n){ if(n %% 2 == 0 || n %% 5 == 0) return(0) k <- 1 m <- 1 while(m != 0){ k <- k + 1 m <- (m * 10 + 1) %% n } k } limit <- 1e6 n <- limit while(a(n) < limit) n <- n + 1 n
6.5秒。
