PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 141 / 平方数でもある累進数 n の調べ上げ

正の整数 n を d で割った商と余りをそれぞれ q と r で表す。d, q, r を適当に並び替えたときに等比数列になる場合がある。

たとえば58を6で割ると商が9で余りが4である。4, 6, 9は公比3/2の等比数列になっている。このような n を累進数と呼ぶことにする。

いくつかの累進数9や 10404=102^2 は平方数になっている。100000未満の累進平方数の和は 124657 である。

10^12 未満の累進平方数の総和を答えよ。

Problem 141 - Project Euler

実例を作ってみよう

まずは定義どおりに立式して,累進平方数の具体例を見てみました。等比数列の条件は等比中項で処理しています。

この方法で総和を求めることもできますが,10^8までで約40秒かかります。


関数形を限定

等比数列の条件を

 d=kab,\, q=ka^2,\, r=kb^2

として処理します。公比の a/b は既約分数としてよいので,aとbは互いに素です。このとき,

 n=dq+r=kb(ka^3+b)

これが平方数になる組を探すと,約2分半で答えが出ます。