【１】コラッツ予想

任意の自然数ｎに対して

［１］ｎが奇数ならば，３ｎ＋１

［２］ｎが偶数ならば，ｎ／２

にする．この工程（ＨＯＴＰＯ手順，half or triple plus one）を繰り返し行うと常に１に到達するというのがコラッツ予想である（１９３０年代）．

　６→３→１０→５→１６→８→４→２→１

１１→３４→１７→５２→２６→１３→４０→２０→１０→５→１６→８→４→２→１

４１から始めると

４１→１２４→６２→３１→９４→４７→１４２→７１→２１４→１０７→３２２→１６１→４８４→１２１→３６４→９１→２７４→１３７→４１２→１０３→３１０→１５５→４６６→２３３→７００→１７５→５２６→２６３→７９０→３９５→１１８６→５９３→１７８０→４４５→１３３６→１６７→５０２→２５１→７５４→３７７→１１３２→２８３→８５０→４２５→１２７６→３１９→９５８→４７９→１４３８→７１９→２１５８→１０７９→３２３８→１６１９→４８５８→２４２９→７２８８→９１１→１３６７→４１０２→２０５１→６１５４→３０７７→９２３２→５７７→１７３２→４３３→１３００→３２５→９７６→６１→１８４→２３→７０→３５→１０６→５３→１６０→５→１６→１

・・・長くなったが，実行されたｎに対しては必ず１で終結している．常に１に到達するためには，

　　１６→８→４→２→１

　のように，途中で２^nになる必要がある．したがって，

　　３ｎ＋１＝２^m

を満たす解（ｎ，ｍ）をすべて求めよという問題を考えることができる．

コラッツ予想は要するに「自然数は３ｎ＋１と２のベキ乗の範囲内で二分木で一意に表される」という話なので，簡単に解決できてしまいそうな気がしてしまうが，はたして，このアルゴリズムは必ず終結するだろうか？　最後が１にならない数が存在することを証明できれば，自然数を結びつける新たなパターンから予想外の展開に繋がる可能性があるのだそうだ．

　１９６０年代に，角谷静夫がこの問題を知り，母校のエール大学に広めたが誰も解決することはできなかった．最近証明が発表されたが，その証明は不完全であって，いまのところ未解決である．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝