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

プロジェクトオイラー解説問134 - (2013/12/11 (水) 12:48:00) のソース

*Problem 134 「素数ペアの結合」 †
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20134

問題
----
連続する素数 p1 = 19, p2 = 23 について考える. 1219 は末尾の桁が p1 からなり p2 で割り切られる最小の数であることが確かめられる.
実際, p1 = 3, p2 = 5 を除けば, 全ての p2 > p1 なる連続する素数のペアについて, 末尾の桁が p1 からなり p2 で割り切られる数 n が存在する. S を n の最小のものであるとする.
5 ≤ p1 ≤ 1000000 を満たす連続する素数のペア全てに対し ∑ S を求めよ.

----

解説
この問題は具体的に考えると解けます。

p1=19とp2=23の場合で考えます。

p1=19ですから19の手前につく数字は100X (Xは自然数)と表現できます。
-答えは100X+19=1219ですがとりあえずXは不明として話を進めましょう。
条件を満たすXは無数にあるのですがそのうちの一つを見つけることを考えます。

(100X+19) mod 23=0なのですから

19 mod 23=-4
と
100X mod 23=4
と分解できることになります。
mod演算の性質から言って4でないと23で割り切れません。

条件を満たす100Xを一つ探すことについて考えてみます。

オイラーの定理より
-100^22 mod 23=1
となります、ほしかったのは4なのでこれをさらに4倍すると。

4*100^22 mod 23=4
これを書き直すと
100*(100^21*4) mod 23=4
となります。
100X mod 23=4
でしたから上式をそのまま代入すると
100X=100*(100^21*4)=4 (mod23)
となります。
すると一つの答えは
-100X+19=100*(4*100^21)+19でこれは23で割り切れる数です。
こんな大きな数どうするの?
と疑問に思うでしょうがここでmod演算が威力を発揮します。
----
***用語定義
A mod 23とあった場合は2項演算としてのmod.
A =B (mod 23)と末尾に()付きであった場合は式の両辺にmodが適用されるとします
----
4はあとで考えるとしてまずは100^21を処理することを考えましょう。
21を2進数で表すと
21=1+4+16
となることに着目します。
-100^21=100*100^4*100^16
と考えます。
今回は割り切れるかどうかだけが問題なので剰余の世界で考えても問題なく。
100^1=100 mod 23
100^2= 100*100 (mod 23)
100^4= (100^2*100^2) (mod 23)
100^8= (100^4*100^4) (mod 23)
100^16=(100^8*100^8) (mod 23)
を考えると
100^1~100^16まではすべて23で割ったあまりなので22以下となります。
すると条件を満たすXは剰余の世界では
100^5=(100*100^4) (mod 23)
100^21=(100^5*100^16)(mod 23)
となりこれをされに4倍して23で割った余りを考えると
X=(100^21*4) mod 23
がめでたく答えとなりXは12とでます。
このようなXはこの問題では0~22までの間に確実に一つ存在し一つしか存在しないのでめでたくXが求まりました(p2は素数だからである)。
P1,P2の数字がほかの数になっても上記と同じ処理で答えがでます。

あとはこれをコード化するだけです。
楽しんでくださいね。