PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 136 / 単体差分

x, y, z を等差数列となるような正の整数とする。正の整数 n が n=20 と与えられたとき方程式
x^2 - y^2 - z^2 = n
はただ一つの解を持つ。

13^2 - 10^2 - 7^2 = 20

100未満の n で方程式がただ一つの解を持つ n は25個ある。

5000万未満の n で方程式がただ一つの解を持つ n は何個あるか?

Problem 136 - Project Euler

類題解答の流用

第135問の類題です。時間を気にしなければ,同じ方法で解けます。

variee.hatenadiary.com

公差を d として x=y+d, z=y-d とおきます。

 y^2-4dy+n=0

各変数の条件は次の通り。

  • y は n の約数
  • d は d=(y+n/y)/4 とあらわせる
  • z=y-d>0 より 3y^2 > n
  • n を4で割った余りは0か3

「y が1個だけ」で解くと約8分。

1分におさめる

1分におさめるには数学的につめる必要があります。「n を4で割った余りは0か3」をもっとくわしく調べます。

■ nが4の倍数のとき

y^2-4dy+n=0 から y は偶数です。n=4m, y=2Y とおきます。

d=\dfrac{1}{2}\left(Y+\dfrac{m}{Y}\right)

以下,必要に応じて d を d(Y) のように書きます。

上式から Y が m の約数であること,Y と m/Y の偶奇が一致することがわかります。m が奇数ならば Y も奇数なので,偶奇の条件は自然にみたされますが,m が偶数のときは違います。m の偶奇で場合分けして処理します。

ア)m が奇数のとき
m = m1 * m2 (1< m1< m2)と書けたとします。
Y=1, m1, m2, m1 m2 が考えられ,対応する d を求めると
d(m2), d(m1 m2) の2つが条件をみたすことがわかります(計算略)。

d がただ1つしかないためには m = m1 * m2 という分割ができないこと,つまり m が1または奇素数であることが必要です。これが十分条件でもあることは容易に示されます。

 n=4,\, 4\cdot \text{(奇素数)}

イ)m が偶数のとき

m=2kとおきます。

d=\dfrac{1}{2}\left(Y+\dfrac{2k}{Y}\right)

Y は偶数です。Y=2Y' とおくと

d=\dfrac{1}{2}\left(2Y'+\dfrac{2k}{2Y'}\right)=Y'+\dfrac{k}{2Y'}

k は偶数です。k=2k' とおくと

d=Y'+\dfrac{k'}{Y'}

k'=k1*k2 (1< k1< k2)と分解できたとすると,Y'=k2, k1*k2 のとき,ア)と同様なまずいことがおきます。k' は1か素数です。十分条件を考えると,k'=2 が不適なことがわかるので

 n=4m=16k'=16,\, 16\cdot \text{(奇素数)}

■ nが4で割って余り3のとき

この場合も n が分割できたらまずいことが言えます。

 n= \text{(4で割って余り3の素数)}


以上をまとめると,n は次の3つのどれかです(p は奇素数)。

  1. 4, 16
  2. 4p, 16p
  3. 4で割って余り3の素数

1. と2. を PrimePi でまとめて計算すると,答えは4秒で出ます。