PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 134 / 素数ペアの結合

連続する素数 p1=19, p2=23 について考える。1219は末尾の桁が p1 からなり p2 で割り切れる最小の数である。

p1=3, p2=5 を除けばすべての p2>p1 なる連続する素数のペアについて, 末尾の桁が p1 からなり p2 で割り切られる数 n が存在する。S を n の最小のものであるとする。

5≤p1≤1000000 をみたす連続する素数のペアすべてに対して ∑S を求めよ。

Problem 134 - Project Euler


p1=19, p2=23 から S=1219 を求める過程を一般化すればOK。

S を求めることは 100x+19 ≡ 0 (mod 23)をみたす x の最小値を求めることです。

まず,100は10^(19の桁数) なので
10^IntegerLength[Prime[n]]
とあらわされます。

x は 100 の mod 23 での逆元(Mathematica では ModularInverse)であらわせます。
 100x \equiv -19\quad \therefore x\equiv -19\cdot (100)^{-1} \pmod{23}
自然数にしたいので,もう一度 Mod[23] をとって x とします。

あとは p1=19=Prime[8], p2=23=Prime[9] を Prime[n], Prime[n+1] に変えればおしまいです。