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

初代Masteries

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

2013年7月のProject Euler [最終更新: 7月15日(月)]

7月15日(月)

Problem 58

反時計回りに並べた数字の対角線上の素数の割合が10%未満になる, 最初の辺の長さを求める問題.

use strict;
use warnings;

use Math::Prime::XS qw/is_prime/;

my $i = 1;
my $diagonal = 1;
my $delta = 2;
my $prime = 0;

END: while (1) {
    for (1..4) {
        $diagonal++;
        $i += $delta;
        $prime++ if is_prime($i);
    }
    last END if $prime > 0 && $prime / $diagonal <= 0.1;
    $delta += 2;
}

printf "%d\n", $diagonal / 2 + 1;

対角線の値を見ていくと, 1, 3, 5, 7, 9, 13, 17, 21, 25, 31, 37, 43, 49... と, 2, 2, 2, 2, 4, 4, 4, 4, 6, 6, 6, 6... の割合で増えていることがわかる. あとはその通り計算するように実装して, Math::Prime::XSで素数判定して, 素数とそうでないものの割合を比べるだけ.

7月8日(月)

Problem 57

漸化式 Tn = 1 + 1 / (1 + Tn-1) の最初の1000項について, 分子の桁数が分母の桁数を上回るものを探す問題.

Tn = 1 + 1 / (1 + Tn-1) を An / Bn とすると, An / Bn = 1 + 1 / (1 + An-1 / Bn-1) となるので, ここから An / Bn = 2 * Bn-1 + An-1 / Bn-1 + An-1 となるので, 2つの漸化式で分子と分母を表せる.

use strict;
use warnings;
use bigint;

my $denominator = 1;
my $numerator = 1;
my $count = 0;

for my $i (1..1000) {
    ($denominator, $numerator) = (2 * $numerator + $denominator, $numerator + $denominator);

    $count++ if length $denominator > length $numerator;
}

print "$count\n";

あとは実際に計算して, 桁数を比べていくだけ.

7月1日(月)

Problem 56

a, b < 100 において, a ^ b の答えの各桁の和が最大となるものを探す問題.

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

my $max = 0;
for my $i (1..99) {
    for my $j (1..99) {
        my $pow = Math::BigInt->new($i)->bpow($j);
        my $sum = sum(split //, $pow->bstr);

        $max = $sum > $max ? $sum : $max;
    }
}
print "$max\n";