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

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

Project Euler - Problem 30

Problem 30

なんだかんだで30問目まで到達ですね. もうちょっと頑張ってみましょう!

さて, 今回の問題は, 各桁を5乗した数の和がもとの数と同じになるような数の和を求める問題.

my $i = 1;
while (1) {
    my $sum;
    $i++;
    $sum += 9 ** 5 for 1..$i;
    print "$i: $sum\n";
    last if $sum <= 9 x $i;
}

こんな感じで, 答えに該当し得る数の範囲を求めると...

1: 59049
2: 118098
3: 177147
4: 236196
5: 295245
6: 354294

...というわけで, 354300あたりまでを検索範囲にしてみます.

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

my %pows;
my $answer;

my $call;
sub sum_of_pows {
    my ($n) = shift;
    return sum(map {$_ ** 5} split //, $n);
}

for my $n (2 .. 354300) {
    my $pow;
    my $regularize = join '', sort {$a <=> $b} grep {$_ != 0} split //, $n;
    if (defined $pows{$regularize}) {
        $pow = $pows{$regularize};
    } else {
        $pow = sum_of_pows($n);
        $pows{$regularize} = $pow;
    }

    $answer += $n if $pow == $n;
}

print "$answer\n";

'1234'も'1243'も'4321'も, 各位の5乗の和を取るsum_of_pow関数の答えは同じなので, 予め調整して'1234'に変換するようにしました.
演算結果は%powsに格納しておいて, sum_of_pows関数での計算を減らしています.