【２】初等整数論的アプローチ

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

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

４１から始めると

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

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

　　１６→８→４→２→１

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

　　３ｎ＋１＝２^m

を満たす解（ｎ，ｍ）を問うものと考えることができる．

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

　　３ｎ＋１＝２^m

は，ｍｏｄ３として，

　　１＝２^m

を得るが，ｍ＝０，ｎ＝０となり，あまり有効ではない．そこで，ｍｏｄ２として

　　３ｎ＋１＝０

を得る．この場合，ｎは奇数になるから，ｍｏｄ４として

　　ｍ＞１のとき，３ｎ＋１＝０→ｎは４ｋ＋１となることが必要

　　（ｎ，ｍ）＝（５，４）では，５→１６→８→４→２→１

　　ｍ＝１のとき，３ｎ＋１＝２→ＮＧ

　　ｍ＝０のとき，３ｎ＋１＝１→ｎ＝０

　ｍｏｄ８として

　　ｍ＞２のとき，３ｎ＋１＝０→ｎは８ｋ＋５となることが必要

　　ｍ＝２のとき，３ｎ＋１＝４→ｎ＝１

　　ｍ＝１のとき，３ｎ＋１＝２→ＮＧ

　　ｍ＝０のとき，３ｎ＋１＝１→ｎ＝０

　ｍｏｄ１６として

　　ｍ＞３のとき，３ｎ＋１＝０→ｎは１６ｋ＋５となることが必要

　　ｍ＝３のとき，３ｎ＋１＝８→ＮＧ

　　ｍ＝２のとき，３ｎ＋１＝４→ｎ＝１

　　ｍ＝１のとき，３ｎ＋１＝２→ＮＧ

　　ｍ＝０のとき，３ｎ＋１＝１→ｎ＝０

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

これより

　３ｎ＋１＝２^m

を満たすための必要条件は，ｎが４ｋ＋１，８ｋ＋５，１６ｋ＋５・・・型整数であることである．（ｎ，ｍ）＝（５，４）はひとつの解であるが，他の解を探してみよう．

［１］３ｎ＋１＝１２ｋ＋４　（ｋ＝０は除く）

　ｋ＝１，ｎ＝５→１６＝２^4，ｍ＝４

　ｋ＝５，ｎ＝２１→６４＝２^6，ｍ＝６

　ｋ＝２１，ｎ＝８５→２５６＝２^8，ｍ＝８

　ｋ＝８５，ｎ＝３４１→１０２４＝２^10，ｍ＝１０

　ｋ＝３４１，ｎ＝１３６５→４０９６＝２^12，ｍ＝１２

［２］３ｎ＋１＝２４ｋ＋１６　（ｋ＝０は除く）

　ｋ＝２，ｎ＝２１→６４＝２^6，ｍ＝６

　ｋ＝１０，ｎ＝８５→２５６＝２^8，ｍ＝８

　ｋ＝４２，ｎ＝３４１→１０２４＝２^10，ｍ＝１０

　ｋ＝１７０，ｎ＝１３６５→４０９６＝２^12，ｍ＝１２

　ｋ＝６８２，ｎ＝５４６１→１６３８４＝２^14，ｍ＝１４

［３］３ｎ＋１＝４８ｋ＋１６　（ｋ＝０は除く）

　ｋ＝１，ｎ＝２１→６４＝２^6，ｍ＝６

　ｋ＝５，ｎ＝８５→２５６＝２^8，ｍ＝８

　ｋ＝２１，ｎ＝３４１→１０２４＝２^10，ｍ＝１０

　ｋ＝８５，ｎ＝１３６５→４０９６＝２^12，ｍ＝１２

　ｋ＝３４１，ｎ＝５４６１→１６３８４＝２^14，ｍ＝１４

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

以上より，

　　３ｎ＋１＝２^m

の解は，ｍ＝２ｋのとき，

　　３ｎ＋１＝２^m=２^2k

　　３ｎ＝２^2k−１＝（２^2−１）（２^2k-2＋２^2k-4＋・・・＋２^0）

　　ｎ＝２^2k-2＋２^2k-4＋・・・＋２^2＋２^0＝（２^2k−１）／３

（ｎ，ｍ）＝（５，４），（２１，６），（８５，８），（３４１，１０），（１３６５，１２），（５４６１，１４），・・・となり，コラッツ予想は正しいことがわかる．

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