PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 142 / 完全平方数コレクション

x+y, x-y, x+z, x-z, y+z, y-z がすべて平方数となる整数の組 x > y > z > 0で, 最小の x+y+z を求めよ。

Problem 142 - Project Euler


与えられた数を順に a^2, b^2, ..., f^2 とおいて x, y, z について解きます。

  • x=(a^2+b^2)/2=(c^2+d^2)/2
  • y=(a^2-b^2)/2=(e^2+f^2)/2
  • z=(c^2-d^2)/2=(e^2-f^2)/2

整理すると

  • b^2=c^2-e^2
  • d^2=a^2-e^2
  • f^2=a^2-c^2
  • aとb, cとd, eとfは偶奇が等しい
  • a^2>b^2, c^2>d^2, e^2>f^2, a^2>c^2>e^2
  • x+y+z=(a^2+c^2+e^2)/2

はじめの3式を使うと,偶奇と大小の条件が整理できます。

 a^2\equiv c^2+e^2\pmod{2},\, c^2+e^2>a^2

この方法で計算してみたら7分半かかりました。


a, c, e のかわりに a, b, c を使うと,「aとbは偶奇が等しい」が言えて速くなりますが,それでも5分以上かかります。

  • d^2=a^2+b^2-c^2
  • e^2=c^2-b^2
  • f^2=a^2-c^2
  • aとbは偶奇が等しい
  • a^2>c^2>b^2, 2c^2>a^2+b^2
  • x+y+z=c^2+(a^2-b^2)/2

また,この方法では c^2+(a^2-b^2)/2 を求めるのですが,「a は大きいが,a≒b のため全体としては小さな値をとる」ケースが考えられ,最小値を求めているとはいえないと思います。

ピタゴラス数を使うともっと速くなりますが,私の腕では3分くらいにしかなりませんでした。1分の壁は厚いです。