PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 123 / 素数の自乗で割った余り

pn を n 番目の素数とする(p1 = 2, p2 = 3, ...)。 r を (pn - 1)^n + (pn + 1)^n を pn^2 で割った余りとする。

たとえば n = 3 のとき p3 = 5 であり,

4^3 + 6^3 = 280 ≡ 5 (mod 25)

余り r が 10^9 より大きくなる n の最小値は 7037 である。

余り r が 10^10 より大きくなる最初の n を求めよ。

Problem 123 - Project Euler


第120問と非常によく似た問題です。

variee.hatenadiary.com

途中の議論も同じです。n は奇数であることと

 r=mod[2np_n,\, p_n{}^2 ]

が言えます。2以外の素数がすべて奇数であること考えると 2n < p_n は明らかなので 2np_n < (p_n)^2 が言えて,

 r= 2np_n

これが 10^10 を超えるような最小の奇数が答えです。