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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 348 / 平方数と立方数の和

多くの数は平方数と立方数の和として表せる。2通り以上の方法で表せるものもある。

いずれも1より大きな平方数と立方数の和としてちょうど4通りの方法で表せる回文数を考えよう。たとえば 5229225 は回文数であり,ちょうど4通りの異なる方法で表せる。

  • 2285^2 + 20^3
  • 2223^2 + 66^3
  • 1810^2 + 125^3
  • 1197^2 + 156^3

このような回文数を小さいものから順に5つ求め, その和を入力せよ。

Problem 348 - Project Euler

普通に計算して解きました。x^3+y^2=k とおくと,これは楕円曲線です。数学的につめて解く人は,これが第1象限内の4個の格子点を通る条件を求めたりするんでしょうか?

最初にやったのがこちら。適当に範囲を決めて解を5個探しました。

なんとなくやったのですが,i^2+j^3 のリストを作るよりも i^2 と j^3 のリストを別々に作って足す方が10秒くらい速いです。

次は計算時間を短くすることと最小性を示すことを考えます。

x^3+y^2 の値を上からおさえて For ループを二重に回すのがスジだと思いますが,平方根や立方根を何度も何度も計算するせいかこれは遅いです。
x^3+y^2 ≦ 796767697 でやったら 380秒かかりました。曲線のグラフが次のようになることを考えると,長方形状の領域で調べてもそんなに効率は悪くなさそうなので,x, y の範囲を別々に指定して計算し直します。

f:id:variee:20170520221603p:plain

89秒かかりました。1分の壁は超えられず。