Project Euler - Problem 36

問題

• 原文

  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₁₀、32=20₁₆、8=1000₂)。 このような数は反転させると(先頭の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);