コラッツ予想｜【コード付き】Pythonでプログラミング作成してみた!!

【対象年次:中学一年～】

みなさんこんにちは！
中高生にも分かる数学のお時間です。

今回は数学上の未解決問題である「コラッツ予想」に関するお話をしたいと思います。
まず、コラッツ予想とはどんなものであるかご覧ください。

$＜コラッツ予想＞$
$nを2以上の自然数とする。このとき、$
$nが奇数ならば\frac{3n+1}{2},nが偶数ならば\frac{n}{2}という計算で新たな自然数を生成する際、$
$その操作を有限回繰り返すと最終的に1になる$

というものです。
これだけ言われてもわかりにくいと思うので、例題を考えてみましょう。

$＜例題＞$ $n=17として何回か操作を行ったとき、それは1になるか？$

まず、17は奇数なので次の自然数は
$\frac{3\times17+1}{2}=26$ となります。
この生成された自然数である26は偶数なので次の自然数は、
$\frac{26}{2}=13$ となりますね。
これを繰り返していくと、
$17→26→13→20→10→5→8→4→2→1$
という感じになります。
おおー！最終的には1になりましたね！
ちなみに矢印の個数が操作の回数なので17は9回の操作で1になるんですね。
(計算は自分でやってみてくださいね)

さて、これを見てもらうとわかるのですが
ある自然数が奇数だったときの次の自然数は増加しており、
ある自然数が偶数だったときの次の自然数は減少していますよね。
どういうことかというと、
$17→26,13→20,5→8$
のように左の自然数(計算前の自然数)が奇数なら、右の自然数(計算後の自然数)は左の自然数より大きく、
$26→13,20→10,10→5,8→4,4→2,2→1$
のように左の自然数が偶数なら、右の自然数は左の自然数より小さくなることが分かります。
これは奇数のときの操作、偶数のときの操作を見れば一目瞭然です。
$nが奇数ならば\frac{3n+1}{2}$ という計算を行うので、自然数 $n$ は大体 $\frac{3}{2}$ 倍され、
$nが偶数ならば\frac{n}{2}$ という計算を行うので、自然数 $n$ は $\frac{1}{2}$ 倍されるわけです。

このことから確率論的にはこの「コラッツ予想」は正しいと予測できます。
その理由を説明しましょう。

まず、自然数 $n$ に対して何回か操作を繰り返したとします。
このとき
$「ある自然数を選ぶとき、それが『奇数である確率』と『偶数である確率』は同じである」$
という事実を利用すると、奇数である際に行われる操作 $\frac{3}{2}$ 倍と偶数である際に行われる操作 $\frac{1}{2}$ 倍が大体同じ回数行われるはずなので、その回数を $m$ とすると、操作後には $n$ は
$((\frac{3}{2})^{m}\times (\frac{1}{2})^{m})n=(\frac{3}{4})^{m}n=\frac{3^{m}}{4^{m}}n$
という大きさになっているはずですね。

ここで操作の回数を増やしていくと $m$ はどんどん大きくなっていき、
それに従って $\frac{3^{m}}{4^{m}}n$ はどんどん減少していくことが分かります。
(これは、 $\frac{3^{m}}{4^{m}}$ が $m$ の増加に従って減少するからです！)

よって何回も操作を行えば、 $\frac{3^{m}}{4^{m}}n$ = $(操作後のnの大きさ)$ はどんどん小さくなっていくので、
最後には1になるだろうと期待できるのです。

ですが、これはあくまでも確率的にそうなるだろうと予想できるだけであって、
実際にこの予想の正しさとは全く無関係であることには注意しなくてはいけません。
最初に選ぶ自然数 $n$ によっては、操作後の数が奇数になることが多く $\frac{3}{2}$ 倍される回数の方が優位になり、最終的にはどんどん大きくなって1にならない可能性も残されているのです。
また、操作を行っているうちにループが起こって1になることは永遠にないかもしれません。
このようにこの「コラッツ予想」は確率的なアプローチ以外で解決しなくてはならないのです！

というわけで、その第一歩として「Python」を使って、このコラッツ予想を研究するためのプログラムを作成しました。
以下の画像は $100$ 以下の自然数に対して何回の操作で1になったかを示したものです。

f:id:exponential0805:20190327025909j:plain

各括弧の中に記載された情報は
[ $(1に到達するまでに要した操作の回数k)$ , $(最初に選ぶ自然数n)$ ]となっています。
先ほど例として示した $n=17$ は、確かに[ $9$ , $17$ ]となっているのが分かりますね。
さて、この表を見ていて気付くこととしては、

$隣り合った自然数同士は1に到達するまでに要する操作の回数が等しいことが多い$

ということだと思います。
例としてはいくつもありますが、
[ $10$ , $34$ ],[ $10$ , $35$ ]や3つ並んだ[ $12$ , $44$ ],[ $12$ , $45$ ],[ $12$ , $46$ ]、
さらには交互に5つ連続で並んだ[ $14$ , $56$ ],[ $22$ , $57$ ],[ $14$ , $58$ ],[ $22$ , $59$ ],[ $14$ , $60$ ]などもあります。

これらの数の並びは偶然というにはあまりに出来すぎていると思います。
きっとこの裏には何か興味深い真実が隠されているのでしょう…！

また、 $100$ 以下の自然数に対して
横軸に $(最初に選ぶ自然数=n)$ ,縦軸に $(1に到達するまでに要した操作の回数k)$ をとったグラフを描くと以下のようになります。

f:id:exponential0805:20190327032900p:plain

比較的 $k$ の値が $5～20$ の間に落ち着いている中、たまに突出して $k$ の値が大きな場合が現れていますね。

また、 $1000$ 以下の自然数に対しても同様のグラフを描くと、

f:id:exponential0805:20190327033239p:plain

のようになります。
さっきより突出した $k$ の値は多くなっていますが、 $k$ の大きさ自体はそこまで跳ね上がっているようには見えませんね。

そしてさらに飛んで $100万$ 以下の自然数に対しても同様のグラフを描きました。

f:id:exponential0805:20190327033531p:plain

激しく振動して塗りつぶされた青い領域はゆがんだ長方形のように見えます。
$k$ の振れ幅がそれほど大きくなっているようには見えず、上限があるようにも見えます。
$n$ を大きくしていくと、いつか $k$ の平均は頭打ちになるのでしょうか？
ううむ、興味深い…。

というわけでプログラミングを使うと膨大な量の計算ができるので、手計算では分からないようなことに気づくことができました！
今回の結果から予想できることを今度は数式を用いて証明していけたらいいなと考えております！

では最後に「Python」に使用したコードを貼っておきます。
私的利用の範囲でしたら、お使いいただいて構いませんのでよろしくお願いいたします！

import math
import matplotlib.pyplot as plt

import sys

sys.setrecursionlimit(2000)

def collatz(n):
    if n == 1:
        return True
    elif n % 2 == 1:
        return (3*n+1)/2
    elif n % 2 == 0:
        return n/2

def c_process(n,RANGE=1000):
    lst = []
    for i in range(1,RANGE+1):
        if n == 1:
            lst.append(i-1)
            return lst
            break
        elif n % 2 == 1:
            lst.append(1)
        elif n % 2 == 0:
            lst.append(2)
        n = collatz(n)


def c_count(n,RANGE=1000):
    for i in range(1,RANGE+1):
        if n == 1:
            return i-1
            break
        n = collatz(n)


def c_staired(n):
    lst = []
    for k in range(2,n+1):
        lst.append([c_count(k),k])
    return lst


def p_staired(n):
    lst = []
    for k in range(2,n+1):
        lst.append(c_count(k))
    return lst


def c_plot(n):
    k = [ k for k in range(2,n+1) ]
    m = []
    for c in p_staired(n):
        if c == None:
            m.append(0)
        else:
            m.append(c)

    plt.plot(k,m)
    plt.grid(color='grey')
    plt.show()
    print(m)

「中高生にも分かる数学」では数学が苦手な人にも非常に分かりやすい記事を心がけています。
他にもいくつか記事があるので、ご覧いただけると嬉しいです！
では、また他の記事でお会いしましょう！