Project Euler で紹介されている問題4を解いてみました。逆さから読んだ数の求め方と6桁の回文数が持つ性質について、解説します。
問題4（積となる最大の回文数）
どちらから読んでも同じになる数を回文数と呼ぶ。2つの2桁の数字の積から作られる最大の回文数は 9009 = 91 × 99 である。
2つの3桁の数字の積から作られる最大の回文数を求めよ。
解答例
まずは、与えられた数字を逆さから読んだ数字を作る必要があります。
- 1234 → 10で割ると4余り、割った数123を得る、0×10+4=4をメモ
- 123 → 10で割ると3余り、割った数12を得る、4×10+3=43をメモ
- 12 → 10で割ると2余り、割った数1を得る、43×10+2=432をメモ
- 1 → 10で割ると1余り、割った数0を得る、432×10+1=4321をメモ
余りを頭から並べると、逆さから読んだ数（4321）を得ることができます。
この関数（reversed_no）が実装できれば、3桁の数（100から999）を2つ掛け合わせて、回文数か確認します（is_palindrome）。以下は、C の実装です。
#include <stdio.h>
int reversed_no(int number)
{
int reverse = 0;
while (number > 0) {
reverse = reverse * 10 + (number % 10);
number = number / 10;
}
return reverse;
}
int is_palindrome(int number)
{
return number == reversed_no(number);
}
int main(void)
{
int i, j, product, max_product, max_index1, max_index2;
max_product = 0;
max_index1 = 0;
max_index2 = 0;
for (i = 100; i <= 999; ++i) {
for (j = i; j <= 999; ++j) {
product = i * j;
if (product > max_product) {
if (is_palindrome(product) == 1) {
max_product = product;
max_index1 = i;
max_index2 = j;
}
}
}
}
printf("Problem004: %d\n", max_product);
printf("Problem004: %d = %d x %d\n", max_product, max_index1, max_index2);
return 0;
}解答としては、最大の回文数だけ求めることができればよいのですが、検算ができるように最大の回文数を得る数字の組み合わせ（max_index1 と max_index2）も出力しています。なお、回文数か調べるのは、掛け算の結果が、いま得ている最大の回文数より大きい場合だけ、計算するようにしています（30行目の if 文）。
解答例（改善版）
ループは100から始めて999まで調べていますが、最大値を求めたいため、大きい数（999）から調べたほうが、（このプログラムの中では）計算量が多い、reversed_no の呼び出しを減らすことができます。
#include <stdio.h>
int reversed_no(int number)
{
int reverse = 0;
while (number > 0) {
reverse = reverse * 10 + (number % 10);
number = number / 10;
}
return reverse;
}
int is_palindrome(int number)
{
return number == reversed_no(number);
}
int main(void)
{
int i, j, product, max_product, max_index1, max_index2;
max_product = 0;
max_index1 = 0;
max_index2 = 0;
for (i = 999; i >= 100; --i) {
for (j = i; j >= 100; --j) {
product = i * j;
if (product > max_product) {
if (is_palindrome(product) == 1) {
max_product = product;
max_index1 = j;
max_index2 = i;
}
}
}
}
printf("Problem004: %d\n", max_product);
printf("Problem004: %d = %d x %d\n", max_product, max_index1, max_index2);
return 0;
}元のプログラムとの差は4行で、背景色を変えました。
考察とさらなる改善
もし、6桁の数が回文数になっていれば、$abccba$ の形になります。この場合は以下が成り立ちます。
$ 100000 \times a + 10000 \times b + 1000 \times c + 100 \times c + 10 \times b + 1 \times a $
$ = 100001 \times a + 10010 \times b + 1100 \times c $
$ = 11 \times (9091 \times a + 910 \times b + 100 \times c) $
つまり6桁の回文数は11の倍数になります。11は素数ですので、
3桁の数（i） × 3桁の数（j） ＝ 6桁の数
になる場合、i または j のどちらかが11の倍数になります。i が 11 の倍数になる場合は、j の値は i 以下の場合をすべて調べますが、i が 11 の倍数にならない場合は、j の値は、i 以下の11 の倍数だけ調べればよいことになります。
また、回文数が5桁になる場合は、11の倍数とはなりませんが、明らかに6桁の回文数が存在するため、3桁の数の積が6桁（100000以上）の場合だけ調べることにしました（25行目）。なお、この実装は、Project Euler が正解者向けに公開している解説を参考にしました。
#include <stdio.h>
int reversed_no(int number)
{
int reverse = 0;
while (number > 0) {
reverse = reverse * 10 + (number % 10);
number = number / 10;
}
return reverse;
}
int is_palindrome(int number)
{
return number == reversed_no(number);
}
int main(void)
{
int i, j, product, max_product, max_index1, max_index2;
int init, diff;
max_product = 100000;
max_index1 = 0;
max_index2 = 0;
for (i = 999; i >= 100; --i) {
if (i % 11 == 0) {
init = i;
diff = 1;
} else {
init = (i/11)* 11;
diff = 11;
}
for (j = init; j >= 100; j -= diff) {
product = i * j;
if (product > max_product) {
if (is_palindrome(product) == 1) {
max_product = product;
max_index1 = j;
max_index2 = i;
}
}
}
}
printf("Problem004: %d\n", max_product);
printf("Problem004: %d = %d x %d\n", max_product, max_index1, max_index2);
return 0;
}測定結果
今回は、3通りのプログラムを紹介しました。どれくらい効果があるのでしょうか？逆さから読んだ数を求める関数（reversed_no）を呼び出す回数を調べてみました。
| reversed_noを呼び出した回数 | |
| 最初の実装 | 51304回 |
| 大きな数から調べる | 6124回 |
| 11の倍数に注目して調べる | 707回 |
最初の実装と比較すると、reversed_no を呼び出す回数がそれぞれの工夫でかなり減っていることが分かりました。
最後に
素朴な実装でも十分な速さで問題を解くことができますが、最大値を求めるため、ループを大きい方から回しました。次に6桁の回文数の性質を使って、特定の関数の呼び出しを減らすことができました。
引き続き、Project Euler の問題を紹介していきます。
