Collatzの問題

1937年にドイツの数学者Collatz(コラッツ)が,「ある数が偶数なら2で割り,奇数なら3倍して1を足す。これを繰り返すとすべての数は1になるだろう」と予想しましたが,だれもそれを証明することができていません(ウィキペディアのコラッツの問題参照)。

Pythonのプログラムで調べてみましょう。

def collatz(n):
    print(n, end="")
    while (n > 1):
        if (n % 2 == 0):
            n = n // 2
        else:
            n = 3 * n + 1
        print(" →", n, end="")
    print()

ここで n % 2 はnを2で割った余りです。

例えば collatz(3) と打つと次のように出ます。

3 → 10 → 5 → 16 → 8 → 4 → 2 → 1

いろいろな数から出発して,Collatzの予想が正しいかどうか確かめてください。Pythonの整数はどんな大きな数でも扱えますので,桁あふれする心配はありません。

なお,n = n // 2n //= 2 と書くこともできます。同様に,n = n + 1n += 1 と書けます。

n = n + 1n += 1 では,前者は n を2回評価し,後者は n を1回しか評価しないという違いがあります。評価することによって副作用が生じる場合は,結果が違うことがありますが,上のような単純な例では,まったく違いがないと考えて差し支えありません。n += 1 のほうが必ずしも実行が速いというわけでもありません。

入力を促すためには次のようにします:

n = int(input('正の整数を入力してください: '))
collatz(n)

関数 input() はキーボード入力を文字列として読み込みます。整数にしたいときは int(),浮動小数点数にしたいときは float() で変換します。

Collatz の問題で,最後は 1 になるとしても,途中でどれくらい大きい数になるでしょうか。これを調べるための関数を作ってみましょう:

def collatz_max(n):
    max = n
    while (n > 1):
        if (n % 2 == 0):
            n = n // 2
        else:
            n = 3 * n + 1
            if n > max:
                max = n
    return max

これは n が大きくなるにつれてどれくらい大きくなるでしょうか。

max = 0
for n in range(10000):
    m = collatz(n)
    if m > max:
        print(n, m)
        max = m

range() の数をもっと大きくしてやってみましょう。

Collatzの問題

オレンジの線は n の2乗を表します。


Last modified: