コラム 人と星とともにある数学 数学

Pythonで数論!未解決問題「コラッツ・角谷予想」|Pythonで数学を学ぼう! 第8回

コラッツ予想

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分以上かかることを知った後は手計算する気力がなくなります。コンピューターで計算できたらと思うはずです。コラッツ・アルゴリズムはシンプルですからコーディングもシンプルです。

コーディングの違いは、コラッツ・シークエンスの計算結果を出力する方法の違いです。

  1. 与えられたnに対するコラッツ・シークエンス生成
  2. a≦n≦bに対するコラッツ・シークエンス生成
  3. a≦n≦b(数式入力可)に対するステップ数表示+時間計測
  4. コラッツ・アルゴリズムを変えた場合

これら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ならば心配ありません。

計算結果

  1. 与えられたnに対するコラッツ・シークエンス生成
  2. a≦n≦bに対するコラッツ・シークエンス生成
  3. a≦n≦b(数式入力可)に対するステップ数表示+時間計測
    のアウトプットは次のようになります。

このように大きなnに対しても簡単にPythonを使ってコラッツ予想が正しいことを実際に確かめることができます。

次回は、さらにコラッツ・シークエンスを分析していきます。

  • この記事を書いた人
  • 最新記事

桜井進(さくらいすすむ)様

1968年山形県生まれ。 サイエンスナビゲーター®。株式会社sakurAi Science Factory 代表取締役CEO。 (略歴) 東京工業大学理学部数学科卒、同大学大学院院社会理工学研究科博士課程中退。 東京理科大学大学院非常勤講師。 理数教育研究所Rimse「算数・数学の自由研究」中央審査委員。 高校数学教科書「数学活用」(啓林館)著者。 公益財団法人 中央教育研究所 理事。 国土地理院研究評価委員会委員。 2000年にサイエンスナビゲーターを名乗り、数学の驚きと感動を伝える講演活動をスタート。東京工業大学世界文明センターフェローを経て現在に至る。 子どもから大人までを対象とした講演会は年間70回以上。 全国で反響を呼び、テレビ・新聞・雑誌など様々なメディアに出演。 著書に『感動する!数学』『わくわく数の世界の大冒険』『面白くて眠れなくなる数学』など50冊以上。 サイエンスナビゲーターは株式会社sakurAi Science Factoryの登録商標です。

-コラム, 人と星とともにある数学, 数学
-

© 2021 株式会社インフォマティクス