Project Euler - Problem 30

問題

• 原文

  Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

• 日本語訳

  各桁を5乗した和が元の数と一致するような数の総和を求めよ.

解答

まず探索範囲の上限を定める必要があります。n桁の最大の整数a_n = 9_n-19_n-2...9₀を考えると、その各桁の5乗の和はb_n = 9⁵nと表せます。

• a_n+1 = 10a_n + 9
• b_n+1 = b_n + 9⁵

ですから、桁数nが大きくなるにつれてaがbよりも急激に大きくなるのが分かります。ある桁数n_maxを超えると、常にa_nmax > b_nmaxが成立するので、両者が等しくなることはなくなります。 実際に調べるとn_maxは6なので、探索範囲は高々0から999,999までとなります。

各桁の乗数の和は、桁の並びに関わらず各桁の数のみによって決まります。例えば2501、5012、(0)215のいずれも同じb_nを持つので、これを別々に計算するのは時間の無駄です。 そこで、このような数をすべて同値と見なす正規化を考えます。手っ取り早く桁の並べ替えで良いでしょう。各桁を昇順に並べ替え、その上で先頭に1個以上0があったら取り除くという処理です。先ほどの例に挙げた数字をこの方法で正規化すると、いずれも125となります。

この正規化された数のみを走査すれば良いわけですから、（0を含まない）n桁の数1つにつき同じ値をn!通り計算していたところが、1通りで済むことになります。

処理の手順をまとめると次のようになります：

1. 全ての正規化された数に対してb_nを計算し、連想配列に格納しておく。
2. 連想配列に格納された値を1つ取り出し、a_nとする。
3. a_nを正規化して連想配列から対応するb_nを引く。
4. a_n = b_nであれば解に加える。
5. 連想配列の値を全て走査するまで2.に戻って繰り返す。

下記のコードでは初期化の都合上、桁数ごとに連想配列を分けていますがアルゴリズム自体に違いはありません。

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw/say/;
use List::Util qw/sum/;

sub regularize($) {
  join '', grep { $_ != 0 } sort { $a <=> $b } split //, shift;
}

my $max_digits = 0;
my ($upper_limit, $sum);
do {
  $max_digits++;
  $upper_limit = 9 x $max_digits;
  $sum = $max_digits * (9 ** 5);
} while $upper_limit < $sum;

my @powers = map { $_ ** 5 } 0 .. 9;
my @sum_dicts = ({ '' => 0 }, { map { ($_ => $powers[$_]) } 1 .. 9 });
while ($#sum_dicts < $max_digits) {
  push @sum_dicts, { map {
    my $prev_key = $_;
    my $last_digit = substr $prev_key, -1, 1;
    map {
      ("$prev_key$_" => $sum_dicts[-1]{$prev_key} + $powers[$_])
    } $last_digit .. 9;
  } keys %{ $sum_dicts[-1] } };
}
say sum grep {
  my $sorted = regularize $_;
  $_ == $sum_dicts[length $sorted]{$sorted};
} grep { $_ > 1 } map { values %$_ } @sum_dicts ;