「プロジェクトオイラー解説問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は自然数)と表現できます。
-答えは100Ｘ+19＝1219ですがとりあえずＸは不明として話を進めましょう。
条件を満たすＸは無数にあるのですがそのうちの一つを見つけることを考えます。
(100X+19) mod 23＝0なのですから
19 mod 23=-4
と
100X mod 23=4
と分解できることになります。
mod演算の性質から言って4でないと23で割り切れません。
条件を満たす100Xを一つ探すことについて考えてみます。
オイラーの定理より
-100^22 mod 23=1
となります、ほしかったのは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でこれは２３で割り切れる数です。
こんな大きな数どうするの？
と疑問に思うでしょうがここでmod演算が威力を発揮します。
4はあとで考えるとしてまずは100^21を処理することを考えましょう。
21を２進数で表すと
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で割ったあまりなので２２以下となります。
すると条件を満たすＸは剰余の世界では
100^5=(100*100^4) (mod 23)
100^21=(100^5*100^16)(mod 23)
となりこれをされに４倍して23で割った余りを考えると
X=(100^21*4) mod 23
がめでたく答えとなりＸは12とでます。
このようなＸはこの問題では0～22までの間に確実に一つ存在し一つしか存在しないのでめでたくＸが求まりました（p2は素数だからである）。
Ｐ１，Ｐ２の数字がほかの数になっても上記と同じ処理で答えがでます。
あとはこれをコード化するだけです。
楽しんでくださいね。
*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は自然数)と表現できます。
-答えは100Ｘ+19＝1219ですがとりあえずＸは不明として話を進めましょう。
条件を満たすＸは無数にあるのですがそのうちの一つを見つけることを考えます。
(100X+19) mod 23＝0なのですから
19 mod 23=-4
と
100X mod 23=4
と分解できることになります。
mod演算の性質から言って4でないと23で割り切れません。
条件を満たす100Xを一つ探すことについて考えてみます。
オイラーの定理より
-100^22 mod 23=1
となります、ほしかったのは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でこれは２３で割り切れる数です。
こんな大きな数どうするの？
と疑問に思うでしょうがここでmod演算が威力を発揮します。
----
***用語定義
A mod 23とあった場合は２項演算としてのmod.
A =B (mod 23)と末尾に（）付きであった場合は式の両辺にmodが適用されるとします
----
4はあとで考えるとしてまずは100^21を処理することを考えましょう。
21を２進数で表すと
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で割ったあまりなので２２以下となります。
すると条件を満たすＸは剰余の世界では
100^5=(100*100^4) (mod 23)
100^21=(100^5*100^16)(mod 23)
となりこれをされに４倍して23で割った余りを考えると
X=(100^21*4) mod 23
がめでたく答えとなりＸは12とでます。
このようなＸはこの問題では0～22までの間に確実に一つ存在し一つしか存在しないのでめでたくＸが求まりました（p2は素数だからである）。
Ｐ１，Ｐ２の数字がほかの数になっても上記と同じ処理で答えがでます。
あとはこれをコード化するだけです。
楽しんでくださいね。
