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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 131 / 素数と立方数の関係

いくつかの素数 p では,適当な正の整数 n が存在して n^3+pn^2 が立方数になる。たとえば p = 19のとき 83+19x82=123 である。

このような性質を持つ各素数について, n の値は一意に定まる。また,100未満の素数では4つしかこの性質をもたない。

この性質を持つ100万未満の素数は何個あるだろうか?

Problem 131 - Project Euler


数学の問題でした。PCは最後の計算に使うだけです。

n^3+pn^2=n^2(n+p) の素因数分解を考えます。a と b の最大公約数を (a,b) であらわすと

 (n+p,n)=(p,n)=p,\,1

■(n+p,n)=p のとき

n=kp とおけます。

 n^3+pn^2=(kp)^3+p (kp)^2=p^3 k^2(k+1)

k と k+1 は互いに素なので,これは立法数になりません。

■(n+p,n)=1 のとき

n^3+pn^2=n^2(n+p) において n, n+p はともに立法数です。
n=x^3, n+p=y^3 とおいて n を消去すると

 p=y^3-x^3=(y-x)(y^2+yx+x^2)

p は素数かつ y^2+yx+x^2>1 なので y-x=1。y=x+1 として上式に代入すると

 p=(x+1)^3-x^3=3x^2+3x+1

この形の素数を数えれば終わりです。