プロジェクトオイラー
http://projecteuler.net/index.php
Q129.
1がk個続く数R(k)を考える。例えば、R(6) = 111111。これらをnが最初に割り切れるのがR(k)だとしたとき、A(n) = kと書く。A(n)が最初に100万を超えるn。
問題を見たとき途方もない計算だと思ったが、ジョギングしながら考えていたらそうでもないことがわかった。
R(k) = (10k - 1)/9だから、10k ≡ 1(mod n)ならR(k)はnで割り切れる。ただし、kが3の倍数の場合は、9nの剰余を取らなければならない。べき乗の計算は剰余を取りながらバイナリ法を使えば簡単。しかし、バイナリ法を使う必要はなかった。
100万でなく100で考えると、101から調べていき、R(2)から101で割りきれるkを調べていく。最初に割り切れたkがA(n)となる。そのときに、R(2)の剰余を10倍し、そのnの剰余を取ればR(3)の剰余になるから、簡単な計算で求められる。
from itertools import countdef A(m):
if m % 3 == 0:
m *= 9
r = 10
for n in count(2):
r = r * 10 % m
if r == 1:
return nN = 10 ** 6
for n in count(N + 1):
if n % 2 == 0 or n % 5 == 0:
continue
a = A(n)
if a > N:
print n
break
