Collatzの問題
入力した数（正の整数）が偶数であれば2で割る。奇数であれば3倍して1を足す。これをwhileループで延々と繰り返すと，最後には1になる。これを実験的に確かめる： code:collatz.c
int main(void)
{
int n;
printf("n = "); scanf("%d", &n);
while (n > 1) {
printf("%d → ", n);
if (n % 2 == 0) { /* 偶数 */
n /= 2;
} else { /* 奇数 */
n = 3 * n + 1;
}
}
printf("1\n");
return 0;
}
例えば27から始めると，
27 → 82 → 41 → 124 → 62 → 31 → 94 → 47 → 142 → 71 → 214 → 107 → 322 → 161 → 484 → 242 → 121 → 364 → 182 → 91 → 274 → 137 → 412 → 206 → 103 → 310 → 155 → 466 → 233 → 700 → 350 → 175 → 526 → 263 → 790 → 395 → 1186 → 593 → 1780 → 890 → 445 → 1336 → 668 → 334 → 167 → 502 → 251 → 754 → 377 → 1132 → 566 → 283 → 850 → 425 → 1276 → 638 → 319 → 958 → 479 → 1438 → 719 → 2158 → 1079 → 3238 → 1619 → 4858 → 2429 → 7288 → 3644 → 1822 → 911 → 2734 → 1367 → 4102 → 2051 → 6154 → 3077 → 9232 → 4616 → 2308 → 1154 → 577 → 1732 → 866 → 433 → 1300 → 650 → 325 → 976 → 488 → 244 → 122 → 61 → 184 → 92 → 46 → 23 → 70 → 35 → 106 → 53 → 160 → 80 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
となる。
途中で桁あふれする可能性を減らすため，int を long にしたバージョン：
code:collatz2.c
int main(void)
{
long n;
printf("n = "); scanf("%ld", &n);
while (n > 1) {
printf("%ld → ", n);
if (n % 2 == 0) { /* 偶数 */
n /= 2;
} else { /* 奇数 */
n = 3 * n + 1;
}
}
printf("1\n");
return 0;
}
long 型といえども，桁あふれすることがありうるので，チェックが必要である：
code:collatz3.c
int main(void)
{
long n;
printf("n = "); scanf("%ld", &n);
while (n > 1) {
printf("%ld → ", n);
if (n % 2 == 0) { /* 偶数 */
n /= 2;
} else if (n <= LIMIT) {
n = 3 * n + 1;
} else {
printf("大きすぎます。\n");
return 1;
}
}
printf("1\n");
return 0;
}
#include <limits.h> すると long 型の最大値 LONG_MAX が定義されるので，それから1を引いて3で割ったものより大きくなれば，3倍して1を足す操作をせず，「大きすぎます」と表示して終了する。
どれくらい真剣に桁あふれを気にしなければいけないのか。こちらに示したように，だいたい途中で n の2乗くらいになりうるので，int 型の範囲なら途中で long 型を使えば大丈夫であろう。