※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「プロジェクトオイラー問129」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問129 - (2014/03/09 (日) 06:12:53) の最新版との変更点

追加された行は青色になります。

削除された行は赤色になります。

 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を9倍すると999、、、9999.
-10^n-1=999、、、999
+10^t-1=999、、、999
 オイラーの定理より
 10^φ(n) mod n=1
 φ(n)の約数が候補になる。
+nで割れる最小の長さの111、、111を9倍しても一桁大きい111、、111を超えない。
+
 そして100万を超えた最初の素数nはφ(n)の約数はn-1のみでいきなり100万以上を満たす。
 よって100万より大きい最初の素数が答え。