9桁の計算問題

2乗した結果、1から9までの数字を1つずつ含む9桁の数字になるような数字にはどんなものがあるか、という問題を考える。Rubyで次のように書いてみた。

def has9digits? (num)
  exit if num.to_s.size >= 10
  digits = num.to_s.split(//).sort.join
  digits == "123456789"
end

1.upto(10000000) do |i|
  print i," * ",i," = ",i**2,"\n" if has9digits?(i**2)
end

結果は次のとおり。

$ ruby 9digits.rb
11826 * 11826 = 139854276
12363 * 12363 = 152843769
12543 * 12543 = 157326849
14676 * 14676 = 215384976
15681 * 15681 = 245893761
15963 * 15963 = 254817369
18072 * 18072 = 326597184
19023 * 19023 = 361874529
19377 * 19377 = 375468129
19569 * 19569 = 382945761
19629 * 19629 = 385297641
20316 * 20316 = 412739856
22887 * 22887 = 523814769
23019 * 23019 = 529874361
23178 * 23178 = 537219684
23439 * 23439 = 549386721
24237 * 24237 = 587432169
24276 * 24276 = 589324176
24441 * 24441 = 597362481
24807 * 24807 = 615387249
25059 * 25059 = 627953481
25572 * 25572 = 653927184
25941 * 25941 = 672935481
26409 * 26409 = 697435281
26733 * 26733 = 714653289
27129 * 27129 = 735982641
27273 * 27273 = 743816529
29034 * 29034 = 842973156
29106 * 29106 = 847159236
30384 * 30384 = 923187456

計算問題とはいえ、各桁を単独の数字として扱うとなると単純じゃないので、文字列にしてソートしている。効率は悪いけど簡単。同じことを、Cでやってみるために次のように書いた。

#include <stdio.h>

int digits(int num)
{
  int i, amari;
  int flag = 1;
  int d[10] = {0};

  for (i = 1; i < 10; i++)
    {
      amari = num % 10;
      d[amari]++;
      num = num / 10;
    }

  for (i = 1; i < 10; i++)
    flag *= d[i];

  return flag;
}

int main(void)
{
  int i, num;
  for (i = 10000; i < 33333; i++){
    num = i * i;
    if(digits(num) == 1)
      printf("%d * %d = %d\n",i,i,num);
  }
}

結果は同じだけど、処理速度はRuby 1.8.6の70倍、Ruby 1.9.1の50倍程度となった。さらに、gcc -O3でコンパイルしたら、50％速くなった。片や文字列に変換したりソートしたりと大げさな処理をしていて、Cのほうは四則演算程度という違いはあるけど。

スピードは100倍ぐらい違うけど、Cのほうはかなり面倒くさい。記述が多いだけではなくて、判定のロジックを考える必要があった。そもそもintで済んだからマシだけど、大きな桁数を扱うとなると、えーと、どうするんだっけな。Rubyだと何も考えずに「これぐらいデカければ充分だろう」と思えるだけ0をつけておいて、結果を見てからよしなに書き換えるということができる。