Project Euler で紹介されている問題14を解いてみました。素直なプログラムと、ひと工夫したプログラムを紹介します。なお、コラッツ予想自体は未解決問題です。
Project Euler 問題14（最長のコラッツ数列）
自然数に対して、以下の規則で数列を定義する。
$n \to n/2$（$n$ は偶数の場合）
$n \to 3 \times n+1$（$n$ は奇数の場合）
この定義に従って、13から開始すると、次の数列が生成される。
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
この数列（13から始まって1で終わる）は、10項を含む。まだ証明されていないが、すべての自然数に対して、1 で終わると考えられている（コラッツ予想）。
100万以下で、一番長い数列となる開始の数字を求めよ。
注意）数列は100万以下で始まるが、数列は100万を超えることがある。
解答例
コラッツ予想として知られている有名な未解決問題です。一見すると、奇数のときは3倍で、偶数のときは半分なので発散するのではないかとも思えますが、かなり大きな数まで1に到達することが確かめられています。
コラッツ数列の定義に従い、100万以下までコラッツ数列の長さを計算するプログラムです。C言語で実装しました。
#include <stdio.h>
#include <stdlib.h> /* exit */
#include <limits.h> /* LLONG_MAX */
#define N 1000000
int collatz_length(int start_no)
{
int counter;
long long int number;
counter = 1;
number = (long long int)start_no;
while (number != 1) {
if ((number >= (LLONG_MAX / 3)) && (number % 2 == 1)) {
printf("Collatz_length: Warning! %lld\n", number);
exit(1);
}
++counter;
if (number % 2 == 0) {
number = number / 2;
} else {
number = number * 3 + 1;
}
}
return counter;
}
int main(void)
{
int i, max_index, terms, max_terms;
max_index = 1;
max_terms = 4; /* 1->4->2->1 */
for (i = 2; i <= N; ++i) {
terms = collatz_length(i);
if (terms > max_terms) {
max_index = i;
max_terms = terms;
}
}
printf("Problem014: %d\n", max_index);
return 0;
}問題の注意にも記載がありますが、一度数列の計算が始まると、100万を超えて、数列の途中では、かなり大きくなる可能性があります。今回、コラッツ数列の長さを求める関数 collatz_length では、内部的に long long int で計算しておき、奇数の時に元の数が long long int の3分の1以上であれば、計算を止めて exit します（背景色を変更しました）。このためだけに、stdlib.h（exit）と limits.h（LLONG_MAX）をインクルードしています。動作させたところ、この警告は出力されず、解答を求めることができました。
解答例（改善版）
元のプログラムも十分に速く動作しましたが、コラッツ数列の長さは、一度求めたものは覚えておけば、そもそも計算する必要がなくなります（メモ化）。このアイデアを実装したプログラムが以下となります。コード差分の背景色を変更しています。
#include <stdio.h>
#include <stdlib.h> /* exit */
#include <limits.h> /* LLONG_MAX */
#define N 1000000
int collaz_table[N+1];
int collatz_length(int start_no)
{
int counter;
long long int number;
counter = 1;
number = (long long int)start_no;
while (number != 1) {
if ((number <= N)&&(collaz_table[number] != 0)) {
counter += collaz_table[number];
break;
}
if ((number >= (LLONG_MAX / 3)) && (number % 2 == 1)) {
printf("Collatz_length: Warning! %lld\n", number);
exit(1);
}
++counter;
if (number % 2 == 0) {
number = number / 2;
} else {
number = number * 3 + 1;
}
}
return counter;
}
int main(void)
{
int i, max_index, terms, max_terms;
max_index = 1;
max_terms = 4; /* 1->4->2->1 */
for (i = 2; i <= N; ++i) {
terms = collatz_length(i);
collaz_table[i] = terms;
if (terms > max_terms) {
max_index = i;
max_terms = terms;
}
}
printf("Problem014: %d\n", max_index);
return 0;
}測定結果
以下は、私の個人PC（プロセッサ：Intel Core i7-10700 @2.90GHz、メモリ 32GB）での測定結果です。キャッシュや他のプログラムの影響もあるため、毎回同じとはなりませんが、速度の目安になるかと思います。測定環境は、cygwin コンソールの time コマンドで測定した user time です。
メモ化を活用したプログラムは、かなり速く動作していることが分かります。
| user time | |
| 最初の実装 | 0.171s |
| 計算結果を記憶（メモ化） | 0.015s |
最後に
コラッツ予想に関した問題で、素直なプログラムと、メモ化を活用したプログラムを紹介しました。
余談となりますが、2011年1月実施のセンター試験「数学Ⅱ・数学B」でコラッツ予想に関係する問題が出題されました（本試験、第6問）。このときに問われたのは以下でした。
- 6 から始めたときのコラッツ数列の長さ
- 11 から始めたときのコラッツ数列の長さ
- 100000以下の自然数に対して、コラッツ数列の長さを求める BASIC プログラムの選択式穴埋め問題
1999年に施行された高等学校指導要領の数学Bに「数値計算とコンピュータ」という内容が含まれていて、この内容の理解度を問う問題でした。現在社会にとって重要となったコンピュータをどう数学の教育課程に絡めるかは難しいようで、扱いに変更が多くみられます。実際、「数値計算とコンピュータ」の内容のいくつかは、あとの教育課程では範囲外になりました。
引き続き、Project Euler の問題を紹介していきます。
