「プロジェクトオイラー問１２９」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問１２９ - (2014/03/09 (日) 06:20:54) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20129

*Problem 129 「レピュニットの非整除性」 †
1のみからなる数をレピュニットという. R(k) を長さ 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 を求めよ


解法
111、、、111を９倍すると999、、、9999.
10＾ｔ-1＝999、、、999
オイラーの定理より
10＾φ(n) mod n=1
φ(n)の約数が候補になる。
ｎで割れる最小の長さの111、、111を９倍しても一桁大きい111、、111を超えない。

そして１００万を超えた最初の素数nはφ（n）の約数はｎ-1のみでいきなり１００万以上を満たす。
よって１００万より大きい最初の素数が答え。