目次
コラッツ予想
1937年、ドイツの数学者ローター・コラッツ（19101-1990）によって次のような問題が提起されました。
コラッツ・アルゴリズム
正の整数nに対して、
偶数なら2で割る
奇数なら3倍して1を足す
コラッツ・アルゴリズムにより、次のように正の整数に対して数列（シークエンス）が生成されます。
コラッツ・シークエンス
2 → 1
3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
4 → 2 → 1
5 → 16 → 8 → 4 → 2 → 1
6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1
「任意の正の整数に対して、コラッツ・アルゴリズムにより生成されるコラッツ・シークエンスは必ず1で終わる」というのがコラッツ予想です。
3n+1問題とも呼ばれます。
小学生でも数論の難問に挑戦！
84年経った現在でも、すべての正の整数に対してこのことが成り立つことは証明されていません。
この数論の難問を実感するのに使うのは四則演算だけです。小学生でも触れることができます。
先日も私が主催するZoomオンラインセミナー、桜井進のPython・UNIX・Math教室、桜井進の魔法の算数教室、桜井進の数学浪漫紀行にて「コラッツ・角谷予想」をテーマにしました。
まず参加者（5歳から60代までの園児・小・中・高・大学生・主婦・教員・会社員）に取り組んでもらったのが、コラッツ・シークエンスを手書きしてもらうことです。
はたして40分かけてn=30までの数表を作成することができました。
なかでも大変なのは27です。
27→ 82→ 41→ 124→ 62→ 31→ 94→ 47→ 142→ 71→ 214→ 107→ 322→ 161→ 484→ 242→ 121→ 364→ 182→ 91→ 274→ 137→ 412→ 206→ 103→ 310→ 155→ 466→ 233→ 700→ 350→ 175→ 526→ 263→ 790→ 395→ 1186→ 593→ 1780→ 890→ 445→ 1336→ 668→ 334→ 167→ 502→ 251→ 754→ 377→ 1132→ 566→ 283→ 850→ 425→ 1276→ 638→ 319→ 958→ 479→ 1438→ 719→ 2158→ 1079→ 3238→ 1619→ 4858→ 2429→ 7288→ 3644→ 1822→ 911→ 2734→ 1367→ 4102→ 2051→ 6154→ 3077→9232→ 4616→ 2308→ 1154→ 577→ 1732→ 866→ 433→ 1300→ 650→ 325→ 976→ 488→ 244→ 122→ 61→ 184→ 92→ 46→ 23→ 70→ 35→ 106→ 53→ 160→ 80→ 40→ 20→ 10→ 5→ 16→ 8→ 4→ 2→ 1
111ステップかかって1にたどり着きます。
Pythonの出番
たった30までですが、手計算することでコラッツ・シークエンスのリズムを実感することができます。
- ステップ数が高々数十であること。nが30までの中でステップ数が100を超えるのは27の場合だけ。
- 数列の値はnの値から大きくなり最大値をとり、減少して1に到る山型のカーブを描くこと。
そして何より、コラッツ・シークエンスが本当に1で終わることが確認できます。
30個のnについて調べるだけで30分以上かかることを知った後は手計算する気力がなくなります。コンピューターで計算できたらと思うはずです。
コラッツ・アルゴリズムはシンプルですからコーディングもシンプルです。
コーディングの違いは、コラッツ・シークエンスの計算結果を出力する方法の違いです。
- 与えられたnに対するコラッツ・シークエンス生成
- a≦n≦bに対するコラッツ・シークエンス生成
- a≦n≦b（数式入力可）に対するステップ数表示＋時間計測
- コラッツ・アルゴリズムを変えた場合
これら4つをまとめたのが次のプログラム「col.py」です。
>>> # col.py
>>>
>>> while(1):
>>> Model = input('1.与えられたnに対するコラッツ・シークエンス生成\r\n'
>>> '2.a≦n≦bに対するコラッツ・シークエンス生成\r\n'
>>> '3.a≦n≦b（数式入力可）に対するステップ数表示＋時間計測\r\n'
>>> '4.コラッツ・アルゴリズムを変えた場合\r\n'
>>> '1、2、3、4のどれかを入力>>> ')
>>> if Model.isdecimal():
>>> Model = int(Model)
>>> if 1 <= Model <= 4:
>>> break
>>>
>>> def col(n):
>>> N = n
>>> s = 0
>>> print('n='+'\t'+str(N))
>>> while True:
>>> if n == 1:
>>> break
>>> if n % 2 == 0:
>>> n = n/2
>>> s = s + 1
>>> else:
>>> n = 3*n + 1
>>> s = s + 1
>>> print(str(s)+'\t'+'{:.0f}'.format(n))
>>>
>>> if Model == 1:
>>> n = int(input('n='))
>>> col(n)
>>>
>>>
>>> elif Model == 2:
>>> a = int(input('nの始まりは '))
>>> b = int(input('nの終わりは '))
>>> for i in range(a, b + 1): # nの範囲
>>> col(i)
>>> print()
>>>
>>>
>>> elif Model == 3:
>>> a = eval(input('nの始まりは 数式OK '))
>>> b = eval(input('nの終わりは 数式OK '))
>>> import time
>>> def col(n):
>>> N = n
>>> s = 0
>>> while True:
>>> if n == 1:
>>> break
>>> if n % 2 == 0:
>>> n = n/2
>>> m = 0
>>> s = s + 1
>>> else:
>>> n = 3*n + 1
>>> m = 1
>>> s = s + 1
>>> print(str(N)+'\t'+str(s))
>>>
>>> start = time.time() # 時間計測開始
>>> print('n'+'\t'+'Step')
>>> for i in range(a, b + 1): # nの範囲
>>> col(i)
>>> t = time.time() - start # 時間計測終了
>>> print('計算時間'+str(t)+'秒')
>>>
>>>
>>> elif Model == 4:
>>> siki = input('コラッツ・アルゴリズム 3*n+1 → ')
>>> S = int(input('Step数の上限は '))
>>> a = int(input('nの始まりは '))
>>> b = int(input('nの終わりは '))
>>> for i in range(a, b + 1): # nの範囲
>>> col(i)
>>> print()
このコードの核は関数col(n)です。変数nがコラッツ・シークエンスの項、変数sがステップ数です。
「if n % 2 == 0:」が「nを2で割った余りが0ならば」を表し、続く「else:」が「nを2で割った余りが0でないならば」すなわちnが奇数である場合を表します。
コラッツ・アルゴリズムは簡単なのでエクセルの関数を用いてコラッツ・シークエンスを表示させることもできます。ただ、エクセルの場合、桁数が大きい場合には計算できません。
その点Pythonなら心配ありません。
計算結果
- 与えられたnに対するコラッツ・シークエンス生成
- a≦n≦bに対するコラッツ・シークエンス生成
- a≦n≦b（数式入力可）に対するステップ数表示＋時間計測
のアウトプットは次のようになります。
このように大きなnに対しても簡単にPythonを使ってコラッツ予想が正しいことを実際に確かめることができます。
次回はさらにコラッツ・シークエンスを分析していきます。
