問題
-
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. 10010、32=2016、8=10002)。 このような数は反転させると(先頭の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($half)
} (looks_like_number $half) ? ('', ($half > 100) ? () : 0 .. 9) : 0 .. 9;
} grep {
not looks_like_number $_ or /^[13579]/;
} ('', 1 .. 999);
いまさらながら、こんなことやってるんだね。
返信削除面白そうなので部でもやってみるよ。
Cでやると本質と関係ないところで難しいと思います。
返信削除RubyでもGroovyでも何でもいいのでスクリプト言語の学習とセットがおすすめ。