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

PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 125 / 回文数の和

回文数 595 は連続する平方数の和で表すことができるという面白い性質を持つ。

6^2+7^2+8^2+9^2+10^2+11^2+12^2

1000 未満で連続する平方数の和で表せる回文数は11個あり,その合計は4164である。この問題では正の整数の平方のみを扱うため, 1=0^2+1^2 は含めないことに注意せよ。

回文数であり,かつ連続する平方数の和で表せる10^8未満のすべての数の合計を求めよ。

Problem 125 - Project Euler


「下手にリストをつくってはいけない」みたいな問題でした。

最初の解答がこちらです。平方数の和 f(n) の差のリストを作ったところ,106秒かかりました。


f(n) - f(n-1)≧10^8 で n の上限(n=7072)をおさえましたが,これだけでは差の最大値は
f(7072) - f(1)=117922753519
と12桁もの数になって,10^8を大幅に超えます。こういう無駄な数が大量に含まれている結果,計算時間がのびているのだと思います。

次の解答がこちら。For ループを二重に使って無駄な計算を避けました。結果は約3秒。30倍以上速くなりました。