コラッツの問題
以下は擬似コードによるプログラミング例である。与えられた初期値に対するコラッツ数列を計算できる。
このプログラムは 1, 4, 2, 1 の無限サイクルを省くために 1 に到達すると停止するようになっている。もしコラッツ予想が正しければ、いかなる正の整数の初期値を与えても停止する。
この問題を、初期のコンピュータで計算することで研究したのがスタニスワフ・ウラムであった。
これは、すべての整数がパリティシーケンスにより一意に識別されること意味し、さらに複数のコラッツ数列がある場合、対応するパリティシーケンスが異なる必要があることを意味する。
n=a·2 + b に関数 f を k 回適用すると、a·3 + dとなる。ここでdはbに関数fをk回適用した結果で、cはその過程で3倍の演算を行った(増加した)回数である。(例えば、a·2 + 1 では、1が2,1,2,1と変化し最後に2になるので、3回の増加がある。よって結果はa·3+2 である。a·2 + 1 では、1が2に増加しその後1になるので、結果はa·3 + 1 となる。) bが2 - 1の場合には、 k回の増加があり、結果は2·a·3 - 1となる。aに掛かる係数は、aには無関係で、bにのみ依存する。これにより、特定の形式の数値が特定の反復回数の後、常により小さい数値になることを予測できます。例えば、4a + 1 は、2回のf操作により3a + 1となり、16a + 3は4回のf操作により9·a + 2となる。これらの小さくなった数が1へとつながるかどうかは、 aの値に依存する。