PEをMathematicaで

Project Eulerに挑戦してみよう

Project Euler 171 / 各桁の平方の和が平方数となる数を求める

正の整数 n について,f(n) を各桁の数字の平方の和と定義する。

f(3) = 3^2 = 9
f(25) = 2^2 + 5^2 = 29
f(442) = 4^2 + 4^2 + 2^2 = 36

0 < n < 10^20について,f(n)が平方数となるような n の和の末尾9桁を求めよ。

Problem 171 - Project Euler


10^20-1 個もの数についてまともに f(n) を求めるわけにはいかないので,漸化式を使って解きました。

1→12のようにして桁数を増やしていくことにします。n-1 桁→ n 桁の変化に注目すると,n 桁で条件をみたす数は次のようにして作れます。

  • (各桁の平方の和)=(平方数) な数の末尾に0をつける
  • (各桁の平方の和)=(平方数-1) な数の末尾に1をつける
  • (各桁の平方の和)=(平方数-4) な数の末尾に2をつける
  • ……
  • (各桁の平方の和)=(平方数-81) な数の末尾に9をつける

ある数 x の一の位に新しい数 y を加えることで,和は
 x \rightarrow 10x+y
のように変化します。このときの和の変化をまとめて一気に処理するため,
f[n,k]={a, b} で

n 桁で各桁の数字の平方の和が k の数が a 個あり,その和は b

をあらわして集計しました。

20桁の数を相手にする割に意外に狭い範囲の計算ですみます。f(n) が最大になるのは n=99...9 (20桁) のときで,その値は
 9^2 \times 20=1620

f[n,k] の k は 1620 通りの値しか取りませんし,平方数は 1^2~40^2 の 40 個しかありません。