PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 129 / レピュニットの非整除性

1のみからなる数をレピュニット数という。長さ k のレピュニット数を R(k) であらわす。
R(6) = 111111

GCD(n, 10) = 1 なる正の整数 n が与えられたとき,R(k) が n で割り切られるような k が常に存在することが示せる。A(n) をそのような k の最小のものとする。
A(7) = 6, A(41) = 5

A(n) が10を超える最小の n は17である。

A(n) が100万を超える最小の n を求めよ。

Problem 129 - Project Euler

mod でいいかえ

設定の整理からはじめます。R(k) は k 桁のレピュニット数です。

 R(k)=\dfrac{10^k-1}{9}

n はこれを割り切ります。

 n\, \left|\, \dfrac{10^k-1}{9} \right.\ \Leftrightarrow\ 9n | (10^k-1)

 \therefore 10^k \equiv 1\pmod{9n}

これをみたす k の最小値が A(n) です。乗法的位数を求める関数
MultiplicativeOrder で簡単に求められます。k の範囲をまったく限定しなくても5秒で答えが出ました。


検索範囲のしぼりこみ1

続いて,n の範囲をしぼりこむことを考えます。条件は

 10^k \equiv 1\pmod{9n}

オイラーの定理(≒フェルマーの小定理)より

 10^{\phi(9n)}\equiv 1\pmod{9n}

 \therefore A(n) \leqq \phi(9n) \leqq 9n-1

A(n)>10^6 となる条件を求めるには,9n-1>10^6 をみたす n について調べれば十分です。n=111112 から調べ始めたら4.7秒でした。5.2秒→4.7秒と1割の短縮ではあまりうれしくないですね。

検索範囲のしぼりこみ2

次の手順で A(n)≦n-1 が示せます。

  1. A(1)~A(n-1) はすべて nを法として0と合同でないと仮定
  2. A(i)≡A(j) (mod n) をみたす i, j (i< j) が存在する
  3. A(j)-A(i) は n で割り切れる
  4. n は 2, 5 と互い素なので A(j)-A(i) の下の桁から0を削って得られる A(j-i) は n で割り切れる
  5. これははじめの仮定と矛盾

n=10^6 から調べれば十分だとわかります。ぐっと速くなって 0.0002 秒でした。