読者です 読者をやめる 読者になる 読者になる

Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

「任意の数からスタートして、偶数なら2を割る、奇数ならnをかけて1を足す過程で、1に収束するか」をいろいろな数でやってみる

今日の風景

f:id:nisemono_san:20160916152021j:plain

寿司によってベルリンの壁が崩壊したことは、ドイツの歴史において重要な発見の一つとなっています。

はじめに

数学において、未解決問題というのはいろいろあるのだけれども、その一つにコラッツ問題(角谷問題とも言う) がある。大抵の数論の教科書だったりすると、このトピックは取りあげられるので、その方面に詳しい人なら「ああ、あの問題ね」というのはピンとくるはずだ。

そのあたりに明くない人に解説すると、コラッツ問題とは「任意の数からスタートして、偶数なら2を割る、奇数なら3をかけて1を足す過程を繰りかえすと、全ての数は最終的に1になるか」というものである。これが不思議なもので、ステップ数は、始める数によって違うのだけれども、最終的には1に収束する。とりあえずはデータを集めようということで、この計算結果を集めてみようというサイトがあるくらいである。

さて、そんな簡単にして、いざ解こうとなると、難問のように立ち塞がるコラッツ問題なのだが、『数学を生み出す魔法のるつぼ』という本をペラペラと読んでみると、下のような記述にぶちあたった。

3を5に代えて「5n + 1」規則にするとどうなるでしょうか。3n + 1予想がどうしたら間違いとなるか自らに問うでみましょう。予想が間違いとなるには、数列が発散するか無限ループに陥いるかのどちらかになる数が存在しなければなりません。5n + 1規則では多くのものが無限ループになります。

この一文を読んでみたときに、ふと思ったのは、「では最も1に収束しないような規則というのは存在するのだろうか」ということだった。思いたったら吉日なので、さっそくコードを書いてみることにした。

コード

今回は何故かElixirが書きたいなと思ったので、Elixirで実装している:

defmodule Collaz do
  def calc(n, m, count) do
    cond do
      n == 1 -> exit(0)
      count > 1000 -> :ok
      rem(n, 2) == 1 -> calc(m * n + 1, m, count + 1)
      true -> div(n, 2) |> (&(calc(&1, m, count + 1))).()
    end
  end

  def forprint(x, y) do
    for y <- (
          Stream.iterate(3, &(&1 + 2))
          |> Enum.take(y)
          |> Enum.to_list ) do
      IO.puts "\n===="
      for i <- 3..x do
        try do
          calc(i, y, 0)
        catch
          :exit, _ -> :io.format("~B ", [i])
        end
      end
      IO.puts("\n---------")
      :io.format("~B ", [y])
    end
  end
end

Collaz.forprint(1000, 10)

実行すると、次のようなログが吐きだされる筈だ。

3 4 6 8 12 15 16 19 24 30 32 38 48 51 60 64 65 76 96 97 102 120 128 130 137 152 
155 163 175 192 194 204 219 240 243 256 260 274 304 307 310 326 343 350 384 388 
397 408 417 429 438 480 486 491 512 520 548 608 614 620 635 652 655 667 686 700 
768 776 794 816 819 834 858 876 941 960 972 982 993 
---------
5 
====
4 5 8 9 10 16 18 20 32 36 40 41 64 72 73 80 82 128 144 146 160 164 167 256 288 292 320 328 329 334 512 576 584 585 640 656 658 668 
---------
7 
====
3 4 6 7 8 12 14 16 24 28 32 48 56 64 96 101 112 128 192 199 202 224 256 319 359 384 398 404 448 455 512 567 638 718 768 796 808 896 910 
---------
9 
====
4 8 16 32 64 93 128 186 256 372 512 541 744 
---------
11 
====
4 8 16 32 64 128 256 315 512 630 
---------
13 
====
4 8 9 16 17 18 32 34 36 64 68 72 128 136 144 145 256 272 273 288 290 512 544 546 576 580 
---------
15 
====
4 7 8 14 15 16 28 30 32 56 60 64 112 120 128 224 240 256 448 480 512 896 907 960 
---------
17 
====
4 8 16 32 64 128 256 512 
---------
19 
====
3 4 6 8 12 16 24 32 48 64 96 128 192 195 256 384 390 512 768 780 
---------
21

ちなみに、3は自明なので、このログの中では飛ばしてある。また、実装の関係上、無限に発散する、あるいは無限ループに陥いるような判定のコードを書く手間をおしむため、ある一定のステップに達した場合、それは無限ループであるという風に決めうちをしている。

また、掛けあわせる数を奇数に制限している理由としては、考えてみれば当然なのだが、奇数に1を足すと必ず偶数になる。偶数において掛け算するという規則なわけだから、無限ループに陥いって、発散することになる。この問題の妙は、偶数と奇数をいったり来たりしながら、なぜか1に収束するということなわけだから、規則に奇数を使わなければならない。

結果を見ると

さて、ここで気になることが一つある。例えば、この中で特徴的な解決を見せている「17を掛けて1を足す」という規則である。上記では、2の乗算でできる数でしかループが終わらないようになっている。これには理由があって、Twitterで示唆してもらったところによると、2の乗数でできる数は、何度割っても偶数になるため、1になるまで常に偶数となる。そのため、偶数のループによって、必ず終了することが保証されることになる。

このように、2の乗算だけしかループが完了しないものは、17の他に25, 27, 29となるわけだが、では23以上だったらそのような規則になるのか、といえばそうはならず、例えば31の場合、「17」でも、先にループは終了するため、ぱっと見、「この数ならば、2の乗数のみしかループが終了しない」という法則は無いように思える(もしかしたらあるのかもしれない。そのような法則を知っている人がいたら教えて欲しい)。このような規則は無数にあるので、興味がある人は試してみるといいかもしれない。

まとめ

確かにコラッツの問題自体は良く知っていたけれども、その中の規則を変化させると、どのようになるかまでには思い至らなかった。このように、既存の良く知っている問題について、規則を変更すると、どのような結論になるのかということを確認するのは楽しかった。月並みな結論だけれども、何か他の問題でそのような規則について見つけることができたら試してみたい、と思ったりした。

数学を生み出す魔法のるつぼ ―実験数学への招待 (O’Reilly math series)

数学を生み出す魔法のるつぼ ―実験数学への招待 (O’Reilly math series)