僕のIT革命

問題 原文 What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1? 日本語訳 整数と(1,2,...,n) (n > 1) との連結積として得られる9桁のPandigital数の中で最大のものを答えよ. 解答 乗数が1, 2, ..., n (n > 1)で桁数は9なので、被乗数mは1から9999の範囲です。 範囲が分かれば後は簡単で、m×1から順に積を連結していって、丁度9桁となったときにPandigital数であればいいわけです。 Pandigital数 を定義通り考えれば「1から9のすべての数字が1回以上現れる数」ですが、この問題では桁数の制約からいずれの数字も1回ずつしか現れないため、「同じ数字が重複して出現せず、0が現れない数」に読み替えることができます。Perlだとこちらの方が正規表現マッチングが高速でした。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/max/; say max map { my $cat = ''; for (my $mul = 1; length $cat < 9; $cat .= $_ * $mul++) {} (length $cat == 9 and $cat !~ /0/ and $cat !~ /(\d).*\1/) ? $cat : () } 1 .. 9999;

問題 原文 Find the sum of the only eleven primes that are both truncatable from left to right and right to left. 日本語訳 右から切り詰めても左から切り詰めても素数になるような素数は11個しかない. 総和を求めよ. 解答 考え方は Problem 35 と同じで、切り詰めていくと途中で合成数になることが分かっている数を最初に除外しています。 0、4、6、8のいずれかの数字を含む場合は明らかに途中で偶数になりますが、2と5は少し特別で、数の一番上の桁にのみ現れた場合は除外できません。何故なら： 左から切り詰めたときは最初に取り除かれるので関係がない。 右から切り詰めていって最後の1桁になったとき、2と5は素数である。 からです。具体的には23と53がこのケースに該当するので、間違って除外すると処理が終わりません。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::Util qw/sum/; use List::MoreUtils qw/all none/; sub is_prime($) { state %memos; my $n = shift; return 0 if $n < 2; return 1 if $n == 2; return 1 if $n == 3; return $memos{$n} if exists $memos{$n}; $memos{$n} = none { $n % $_ == 0 } 2 .. sqrt $n; } sub is_truncatable_prime($) { my $n = shift; return 0 if length $n == 1; return 0 if $n =~ /[0468]/; return 0 if $n =~ /.[25]/; return 0 unless is_prime $n; all { is_prime substr($n, $_) and...

問題 原文 Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2. 日本語訳 100万未満で10進でも2進でも回文数になるような数の総和を求めよ. 解答 nで割り切れる数はn進法で表すと下の桁が0になります(e.g. 100 10 、32=20 16 、8=1000 2 )。 このような数は反転させると(先頭の0は無視するので)桁数が変わってしまうため、回文数になりません。よってこのような数は最初に除外できます。 この問題の場合、2か10で割り切れる数は解にならないことが分かります。10で割り切れるときは当然2でも割り切れるので、実際には2で割り切れるか調べれば十分です。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; sub is_palindromic($) { my $n = shift; $n eq reverse $n; } say sum grep { is_palindromic $_ and is_palindromic sprintf '%b', $_; } grep { $_ % 2 != 0 } 1 .. 1_000_000; 追記 値の範囲ですが、1,000,000まで探索する必要はありませんでした。 1から999まで探索して、それを反転させた数値と連結すれば偶数桁の回文数、その間に1つ数字を入れれば奇数桁の回文数が得られるので、探索範囲を絞った上に10進数の回文数判定も省けます。 少し長いですが、70倍ほど高速化できました。 use Scalar::Util qw/looks_like_number/; say sum grep { $_ <= 1_000_000 and is_palindromic sprintf '%b', $_; } map { my $half = $_; map { $half . $_ . reverse...

問題 原文 How many circular primes are there below one million? 日本語訳 100万未満の巡回素数は何個か? 解答 回転させた数値がすべて素数ということは、すべての桁が奇数でなければいけません(ただし2を除く)。 追記 匿名氏にコメントでご指摘頂いたのでコードを一部修正しました。 いずれかの桁に5がある場合も、回転させると必ず5の倍数が現れるので除外できます。 もっと追記 前の修正に間違いが入っているのをご指摘頂いたので修正しました。 5自体は素数なので、巻き添えで除外してはいけません。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::MoreUtils qw/all none/; sub is_prime($) { state %memos; my $n = shift; return 0 if $n < 2; return 1 if $n == 2; return 1 if $n == 3; return $memos{$n} if exists $memos{$n}; $memos{$n} = none { $n % $_ == 0 } 2 .. sqrt $n; } sub rotate($) { my $n = shift; substr($n, 1) . substr($n, 0, 1); } sub rotations($) { my $n = shift; my %seen = ($n => 1); $seen{$n} = 1 until exists $seen{$n = rotate $n}; keys %seen; } sub is_circular_prime($) { state %memos; my $n = shift; return 0 if $n =~ /[024568]/ and $n != 2 and $n != 5; return $memos{$n} if exists $memos{$n}; my ...

問題 原文 Find the sum of all numbers which are equal to the sum of the factorial of their digits. 日本語訳 各桁の数の階乗の和が自分自身と一致するような数の総和を求めよ. 解答 Problem 30 とほぼ同じ問題なので、その時の解答を基にして考えます。 前回の問題と違うのは、0! = 1なので0を含む数字を含まない数字と同一視できない点です。 そこで正規化の際に0を省くのをやめて、例えば251と2501はそれぞれ125と0125として別に扱うことにします。 また0! = 1!なので、例えば110と100のように各桁の階乗の和が同じになる数が存在し、これを重複して数えないようにしなければなりません。 既に数えた値を連想配列で覚えておいてもいいのですが、 List::MoreUtils の uniq 関数で重複要素を前もって削除する方が高速でした。 #!/usr/bin/env perl; use strict; use warnings; use feature qw/say/; use List::Util qw/sum reduce/; use List::MoreUtils qw/uniq/; sub factorial($) { our ($a, $b); my $n = shift; return 1 if $n == 0; return reduce { $a * $b } 1 .. $n; } my @facts = map { factorial $_ } 0 .. 9; my $max_digits; for ($max_digits = 1; 10 ** $max_digits <= $max_digits * $facts[9]; $max_digits++) {} my @sum_dicts = ({}, { map { ($_ => $facts[$_]) } 0 .. 9 }); until ($#sum_dicts == $max_digits) { push @sum_dicts, { map { my $prev_key ...

問題 原文 The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s. We shall consider fractions like, 30/50 = 3/5, to be trivial examples. There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator. If the product of these four fractions is given in its lowest common terms, find the value of the denominator. 日本語訳 49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである. 我々は 30/50 = 3/5 のようなタイプは自明な例だとする. 1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある. その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ. 解答 どうも「自明でない分数」の基準がよく分かりませんが、「分子・分母に共通する数字を取り除いたとき、元の分数と同じ値になるような分数(ただし分子・分母が10の倍数である場合を除く)」みたいです。 分数を (numerator, denominator) というリストの形で扱うことにして、「共通する数字を取り除いた1桁/1桁の分数で、通分した結果が元の分数のそれと等しい」という長ったら...

問題 原文 Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital. 日本語訳 掛けられる数/掛ける数/積に1から9の数が1回ずつ出現するような積の総和を求めよ. 解答 n桁×m桁の数の積はn+m-1桁かn+m桁になる(e.g. 10×10=100, 99×99=9,801)ので、桁数の合計が9になるとき、積の桁数は4桁であることが分かります。つまり、調べる積の範囲は1,000から9,999までとなります。 あとは数字が重複していないかどうかの判定ですが、積・乗数・被乗数を並べて数字列を作り、小さい順に並べ替えて123456789になれば重複していないことになります。 例えば4396=28×157の場合、並べて書くと439628157という数字列ができます。これを並べ替えると123456789になりますから、4396は答えの1つであることが分かります。 乗数の取り得る範囲は1から積の平方根の間ですが、1の時は積と被乗数が同じになるので明らかに答えではありません。従って2から開始すると少しだけ早くなります。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; use List::MoreUtils qw/any/; say sum grep { my $n = $_; any { join('', sort split //, $n . $_ . $n / $_) eq '123456789'; } grep { $n % $_ == 0 } 2 .. sqrt $n; } 1000 .. 9999;