ProjectEuler Problem 87

Problem 87 - Project Euler 問題のページ
Problem 87 - PukiWiki 日本語訳

普通に総当りで解いた。整数を p1^2 + p2^3 + p3^4 で表す場合、同じひとつの整数でも複数の表し方があることを見逃していて失敗。ハッシュ変数導入でクリア。

145 =  2^2 + 5^3 + 2^4 =   4 + 125 + 16
145 = 11^2 + 2^3 + 2^4 = 121 +   8 + 16

3重ループそれぞれで素数を引っぱってきて、普通に計算。同じ数が 2回以上出てきたときのために、結果の値をハッシュのキーにぶち込んで、プログラム終了直前でハッシュにキーが何個あるか調べる富豪コード。

#! /usr/bin/perl
use strict;

my $lim = 50000000;
#my $lim = 50;

my (%h, $in2, $in3, $in4, $p2, $p3, $p4, $s);

open($in2, "-|", "primes 2") or die;
while (<$in2>) {
        chomp;
        $p2 = $_ ** 2;
        last if ($p2 >= $lim);

        open($in3, "-|", "primes 2") or die;
        while (<$in3>) {
                chomp;
                $p3 = $_ ** 3;
                last if ($p2+$p3 >= $lim);

                open($in4, "-|", "primes 2") or die;
                while (<$in4>) {
                        chomp;
                        $p4 = $_ ** 4;
                        $s = $p2+$p3+$p4;
                        last if ($s >= $lim);
                        print "$s = $p2 + $p3 + $p4\n";
                        $h{$s} += 1;
                }
                close($in4);
        }
        close($in3);
}
close($in2);

print scalar(keys %h), "\n";

計 59038回、primes コマンドを起動します。