読者です 読者をやめる 読者になる 読者になる

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 291 / Panaitopol素数

素数 p がある正の整数 x, y に対して

 p=\dfrac{x^4-y^4}{x^3+y^3}

をみたすとき,p を Panaitopol 素数 と呼ぶ。
5x10^15 未満の Panaitopol 素数はいくつあるか。

Problem 291 - Project Euler


問題131とほとんど同じ方法で解けてしまった。

x と y の最大公約数を g として
x=gX, y=gY(XとYは互いに素)
とおいて与式に代入します。

 p=\dfrac{(X-Y)(X^2+Y^2)}{X^2-XY+Y^2}g

a と b の最大公約数を (a, b) であらわして,約分の様子を調べます。

 (X^2+Y^2, X^2-XY+Y^2)=(X^2+Y^2, -XY)

X と Y は互いに素なので,X^2+Y^2 は X の1以外の約数でも Y の1以外の約数でも割り切れません。上式の値は1。

 ( (X+Y)^2, X^2-XY+Y^2)=(3XY, X^2-XY+Y^2)

これも1です。p が素数だということも考えると

 p=(X-Y)(X^2+Y^2),\, g=X^2-XY+Y^2

X-Y=1 が言えて,
 p=(Y+1)^2+Y^2=2Y^2+2Y+1

この形の素数を探します。


variee.hatenadiary.com