PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 168 / 数の循環

自然数 142857 を考える。最後の桁 7 を一番前に持っていく,すなわち,右に循環させると 714285 を得る。

714285 = 5*142857

これは 142857 の珍しい性質を示している。右に循環させた数の約数になっている。

10 < n < 10^100 の n について,この性質をもつ数の総和の下5桁を答えよ。

Problem 168 - Project Euler

nの一般形は?

10^100ともなるとループを回すわけにはいかないので,n がどんな形の数なのかを考えます。変換前後の数を x, y であらわして,
x =10a+d (d は1以上9以下,a は m 桁)
とおきます。
y=d*10^m+a

y=kx とすると
(10^m-k)d=(10k-1)a

問題文中の例にならって k=5 とします。
(10^m-5)d=49a

■d=7 のとき

 10^m-5=7a\quad \therefore 10^m\equiv 5 \pmod{7}

フェルマーの小定理を使って解くと,

 m=6M+5\quad \therefore a=\dfrac{10^{6M+5}-5}{7}

 x=10a+d=\dfrac{10^{6M+5}-5}{7}\cdot 10+7=\dfrac{10^{6M+6}-1}{7}

142857 は M=0 のときの値です。

■d≠7 のとき

 10^{m}\equiv 5 \pmod{49}

が必要。フェルマーの小定理から m=42M'+41 とおけます。m は a の桁数なので m=41, 83 です。

(10^m-5)d=49a から

 x=10a+d=\left(\dfrac{10^m-5}{49}\cdot 10+1\right)d=\dfrac{10^{m+1}-1}{49}d

d の係数は m 桁で,首位の数字は2。x は m+1 桁なので
d=5, 6, 8, 9
これらの中に条件をみたすものはありませんでした。

PCにやらせよう

このやり方を続けるとすべての場合について一般項を出すことも可能ですが,それでは Mathematica を使っている意味がありません。
d=7, d≠7 どちらの場合も最終的に得られた x が同じ形をしていることに注目します。

(10^m-k)d=(10k-1)a と x =10a+d から

 x=\dfrac{10^{m+1}-1}{10k-1}d

これが題意をみたす条件を考えます。ループの回数は m が99回,k と d が9回ずつの合計約8000回です。大して時間はかからないはず,と思ってやってみたら0.05秒でした。