PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 135 / 同一差分

正の整数 x, y, z が等差数列として与えられたとき,
x^2 - y^2 - z^2 = n
がちょうど2個の解を持つような最小の正の整数は n=27 である。
34^2 − 27^2 − 20^2 = 12^2 − 9^2 − 6^2 = 27

n=1155 は方程式がちょうど10個の解を持つ最小の値である。

ちょうど10個の解を持つような n は 100万までにいくつ存在するか?

Problem 135 - Project Euler


公差を d として x=y+d, z=y-d とおくと,与式は次のようになります。

 4dy-y^2=n\quad \therefore y^2-4dy+n=0

これから次のことがわかります。

  • y は n の約数
  • d は d=(y+n/y)/4 とあらわせる
  • z=y-d>0 を整理すると 3y^2 > n

「n は10個以上の約数をもつ」で候補をしぼった後,「d は整数」かつ「3y^2 > n」をみたす y がちょうど10個ある n を探します。


追記(2017/05/04)

ちょっと手直ししました。

  • 一部の関数をコンパイル
  • 並列化
  • n の候補のしぼりこみ

数学的に意味があるのは n の候補のしぼりこみです。y^2-4dy+n=0 から
 n\equiv -y^2\pmod{4}

平方数を4で割った余りは0か1なので,n を4で割った余りは0か3です。以上の変更で約4倍の速さになりました。




次の第136問