前回のコラッツの問題③の続きです。
下の命題を考えていました。
命題 次の二つは同値
①奇数であれば3倍してから1を加え，偶数であれば2で割る操作を続けると
どんな自然数も[1 → 4 → 2 → 1]のループにたどり着く
②奇数であれば1を加えてから3倍し，偶数であれば2で割る操作を続けると
どんな自然数も[3 → 12 → 6 → 3]のループにたどり着く
今回は①を満たせば②も満たすことを示して証明を終わらせます。
まずは②についての漸化式
を考えましょう。
初項が偶数であれば2で割り続けていつか奇数になります。
また奇数は1を加えてから3倍するので次の項は3の倍数になります。
よってどのような自然数が初項でもその数列は3の倍数のいずれかの項にもつことになります。
（ 例：28 → 14 → 7 → 24 ）
すなわち
3の倍数からスタートしたときにループ[3 → 12 → 6 → 3]に必ずたどりつくか
を調べればよいわけです。
ここである項が3の倍数であれば次項も3の倍数となります。
実際、ある3の倍数の項が偶数であれば、
2と3は互いに素であるからその項を2で割ることで得た次の項は因数3を含み
3の倍数です。
また奇数の場合は漸化式から明らかでしょう。
よって初項が3の倍数であればその数列のすべての項は3の倍数となります。
ここで初項を3の倍数として、次のような数列を考えます。
こうしてできた数列のすべての項は自然数であり
コラッツの問題③の時と同じように計算すると、
を得ます。
よって①を満たせば
この数列は[1 → 4 → 2 → 1]のループに必ず入ることになります。
これらを3倍することで
元の数列も[3 → 12 → 6 → 3]のループに入ることがわかります。
つまり②を満たします。
以上により①と②は同値です。
下の命題を考えていました。
命題 次の二つは同値
①奇数であれば3倍してから1を加え，偶数であれば2で割る操作を続けると
どんな自然数も[1 → 4 → 2 → 1]のループにたどり着く
②奇数であれば1を加えてから3倍し，偶数であれば2で割る操作を続けると
どんな自然数も[3 → 12 → 6 → 3]のループにたどり着く
今回は①を満たせば②も満たすことを示して証明を終わらせます。
まずは②についての漸化式
を考えましょう。
初項が偶数であれば2で割り続けていつか奇数になります。
また奇数は1を加えてから3倍するので次の項は3の倍数になります。
よってどのような自然数が初項でもその数列は3の倍数のいずれかの項にもつことになります。
（ 例：28 → 14 → 7 → 24 ）
すなわち
3の倍数からスタートしたときにループ[3 → 12 → 6 → 3]に必ずたどりつくか
を調べればよいわけです。
ここである項が3の倍数であれば次項も3の倍数となります。
実際、ある3の倍数の項が偶数であれば、
2と3は互いに素であるからその項を2で割ることで得た次の項は因数3を含み
3の倍数です。
また奇数の場合は漸化式から明らかでしょう。
よって初項が3の倍数であればその数列のすべての項は3の倍数となります。
ここで初項を3の倍数として、次のような数列を考えます。
こうしてできた数列のすべての項は自然数であり
コラッツの問題③の時と同じように計算すると、
を得ます。
よって①を満たせば
この数列は[1 → 4 → 2 → 1]のループに必ず入ることになります。
これらを3倍することで
元の数列も[3 → 12 → 6 → 3]のループに入ることがわかります。
つまり②を満たします。
以上により①と②は同値です。