2021年7月11日日曜日

コラッツ予想

 コラッツ予想1億2千万円の懸賞金がかかった。胴元は音圧爆上げくんという音楽系ウェブサービス(料金が無料!)の会社だとのこと。クレイ数学研究所の7つのミレニアム懸賞問題(1件100万ドル)より懸賞金が高い。

それはいいとして,コラッツ予想とは次のようなものだ。ある自然数 n (n≧2) から出発してその次の自然数を,n が偶数のときは n/2 ,n が奇数のときは 3n+1 で定義する。こうして得られた自然数の列が最終的には1に到達するという予想である。

まだ証明はできていないが(だから懸賞金問題になるわけで),2^68 ≒ 3x10^20 まではコンピュータで確かめられている。奥が深そうなので,詳細には立ち入らずに,Juliaでコーディングしてみた。まったく工夫のないプログラムによって,1〜10^8までの奇数に対して1分以内で計算することができた。

なお,プログラミング教育と称して小中学校でモソモソする内容よりは,エクセルを使えるようにするほうが圧倒的に価値があるという説にはほとんど賛同したくなる今日このごろである。

using Plots

function collatz(m,n,p)
# m : number of call
# n : argument of function
# p : print switch
#
  if p==1
    print(n,"->")
  end
  m=m+1
  if mod(n,2)==0
    return m,div(n,2)
  else
    return m,3*n+1
  end
end

function sequence(m,n,p)
# n0: starting argument
# m : iteration number
#
  n0=n
  while n!=1
    m,n=collatz(m,n,p)
  end
  if p==1
    println(1,":",m)
  else
    return n0,m
  end
end

function counter(N,M)
  for i in 1:2:N
    n,m=sequence(0,i,0)
    if m > M
      println(n,":",m)
    end
  end
end

function plotter(N)
  x,y = zeros(N),zeros(N)
  for i in 1:2:N
    x[i],y[i]=sequence(0,i,0)
  end
  scatter(x,y,legend=:topleft)
end

@time counter(100000000,800)
plotter(1000)

図 コラッツ予想 奇数 n=3〜999までのシーケンス数の散布図

0 件のコメント:

コメントを投稿