Collatz問題 #3

main関数を変更して操作回数をかなり狭い範囲だが探索してみた。

#include <stdio.h>
#include <gmp.h>
...snip
int main(void)
{
	unsigned long i, max_i = 0;
	mpz_t x, iter, max_iter;
	mpz_inits(x, iter, max_iter, NULL);
	mpz_set_ui(max_iter, 0UL);
	for (i = 4294967295UL; i >= 4294700000UL; --i) {
		mpz_set_ui(x, i);
		collatz(iter, x);
		if (mpz_cmp(iter, max_iter) > 0) {
			mpz_set(max_iter, iter);
			max_i = i;
		}
	}
	gmp_printf("%lu: %Zu\n", max_i, max_iter);
	mpz_clears(x, iter, max_iter, NULL);
	return 0;
}

4294967295は手元のC処理系でのunsigned longが表せる最大値である。
結果は、

  4294793947: 756

であり、操作回数に関しては通常の整数型の範囲で収まっている。
もちろん4294700000より小さい初期値で操作回数がこれより多い可能性は十分ある。
実際、4294967295UL >= i >= 4294800000UL の探索では、

  4294832447: 694

4294967295UL >= i >= 4294900000UL の探索では、

  4294956271: 588

であった。
ただ、探索範囲を広げるとか理論的に推測するとかの深い追求はしないが、
「操作回数については多分unsigned intの範囲の初期値に対してunsigned intの範囲を超えないような気もする」
という感覚もあまり間違ってはないと思う（疑問符は付く）。

もし強引に探索範囲を広げるのであれば以下の方針も検討の余地があるかもしれない。
上のコードでは単純に初期値ごとに1に至るまでの操作回数を数え上げている。
これを、一回の操作ごとに出てくる値を記録してマップを作っていくようにすれば、
別の初期値で同じ値が出現した際にはそこから先を操作することなく1までの回数が分かる。
ただし、「マッピングのための記憶領域＋マッピング操作の時間」と「単純探索の時間」とのトレードオフになる。