プロジェクトオイラー 問１２３

プロジェクトオイラー(Project Euler)の問題をpythonでやってみます。
日本語翻訳サイトは、プロジェクトオイラー日本語 でネット検索です。

問１２３「素数の自乗で割った余り」
p_n を n 番目の素数とする. (p1 = 2, p2 = 3, ...)
r を (p_n - 1)ⁿ + (p_n + 1)ⁿ を p_n² で割った余りとする.

例えば, n = 3 のとき, p₃ = 5 であり, 43 + 63 = 280 ≡ 5 mod 25.
余り r が 10⁹ より大きくなる n の最小値は 7037 である.
余り r が 10¹⁰ より大きくなる最初の n を求めよ.



注意！！！
自力で解きたい人へ
以降の記述には解法に関するネタバレが含まれます。



私の回答例は以下の通りです。

def f(rmin):
	for i, p in enumerate(P()):
		n = i + 1
		if n % 2:
			r = (2*n*p) % (p*p)
			if r > rmin: return n, p, r
		
def P():
	L, i = [2], 1
	yield 2
	while True:
		i += 2
		for j in L:
			if not i%j: break
		else:
			L.append(i)
			yield i
			
if __name__=="__main__":
	rmin = 10**10
	n, p, r = f(rmin)
	print "n =", n, "(素数p =", p, ", 余りr =", r, ")"

１．関数f(rmin)
・最小の余りrminを受け取り、問題に合うn番目の素数pとそのときの余りrについて、n,p,rを返します。

・この問題は問１２０の続きの問題です。
　問１２０では、
(a - 1)ⁿ + (a + 1)ⁿ を n² で割った余りをrとしていましたが、
　本問では、
(p_n - 1)ⁿ + (P_n + 1)ⁿ を p_n²で割った余りをrとしています。

・問１２０の式に、a=p_nを代入すると以下のことがわかります。
　余りrは、nが偶数か奇数かでパターンが異なります。
　nが偶数の場合、余りrはaに関わらず 2 です。
　nが奇数の場合、余りrは 2np_n をp_n²で割った余りです。
　
・pは素数なので、2以外はすべて奇数です。
　題意から答えは明らかに2よりも大きく、必ず奇数です。
　このため、nが偶数のときは処理せず飛ばします。

２．関数P()
・素数を小さい方から昇順に返すジェネレーターです。呼び出しの都度、次の素数を返却します。
・問１０８で作成した関数を改良しました




解答はこのすぐ下の行です。文字の色を白にしてます。選択状態にすると見えます。
n = 21035 (素数p = 237737 , 余りr = 10001595590 )