【Python】コラッツ予想
こちらの記事で紹介されていたコラッツ予想を判定するプログラムを Python で書いてみました。
まずはコードです。
def is_collatz(N, calc_max = 700) :
N_calc = N
N_list = []
for calc in range(0, calc_max) :
N_list.append(N_calc)
if (N_calc <= 1) :
return True, calc, N_list
elif ((N_calc % 2) == 0) :
N_calc /= 2
else :
N_calc = (N_calc * 3) + 1
return False, calc, N_list
# 開始時間記憶
import time
start_time = time.time()
# 統計情報
calc_total = 0
calc_max = 0
calc_max_N = 0
N_list_all = []
is_collatz_N = True
# コラッツ予想チェック
max_N = 500000 # 50万
for number in range(1, max_N) :
is_collatz_N, calc, N_list = is_collatz(number)
N_list_all.append(N_list)
if (is_collatz_N == False) :
break
calc_total += calc
if (calc_max < calc) :
calc_max = calc
calc_max_N = number
# 結果表示
if (is_collatz_N == True) :
print('1 -', max_N, 'is Collatz Number')
else :
print(number, 'is not Collatz Number')
# 統計表示
print('calc_total = ' , calc_total)
print('calc_max = ' , calc_max)
print('calc_max_N = ' , calc_max_N)
print('N_list of %d = ' % calc_max_N, N_list_all[calc_max_N - 1])
# 処理時間表示
end_time = time.time()
print('processing time is %d sec' % (end_time - start_time))実行結果
1 - 500000 is Collatz Number
calc_total = 62134644
calc_max = 448
calc_max_N = 410011
N_list of 410011 = [410011, 1230034, 615017.0, 1845052.0, 922526.0, 461263.0, ・・・ 46.0, 23.0, 70.0, 35.0, 106.0, 53.0, 160.0, 80.0, 40.0, 20.0, 10.0, 5.0, 16.0, 8.0, 4.0, 2.0, 1.0]
processing time is 22 sec除算をなくしてみましょう。
関数「is_collatz」だけのせます。
def is_collatz(N, calc_max = 700) :
N_calc = N
N_list = []
for calc in range(0, calc_max) :
N_list.append(N_calc)
if (N_calc <= 1) :
return True, calc, N_list
elif ((N_calc & 1) == 0) :
N_calc >>= 1
else :
N_calc = (N_calc * 3) + 1
return False, calc, N_list実行結果
1 - 500000 is Collatz Number
calc_total = 62134644
calc_max = 448
calc_max_N = 410011
N_list of 410011 = [410011, 1230034, 615017, 1845052, 922526, 461263, 1383790, 691895, ・・・ 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1]
processing time is 18 sec22sec が 18sec に短縮されました。
約18% 減少です。
除算を避けると、やっぱり違うんですね。
ついでに。
この方法だと「is_collatz(N)」では、すでに「N-1」まで検証済みであるわけで、「N-1」以下になったら検証不要です。
というロジックにしてみました。
「is_collatz」の引数に「judged_max_N」を追加します。
def is_collatz(N, judged_max_N, calc_max = 700) :
N_calc = N
N_list = []
for calc in range(0, calc_max) :
N_list.append(N_calc)
if (N_calc <= 1) :
return True, calc, N_list
elif (N_calc <= judged_max_N) :
return True, calc, N_list
elif ((N_calc & 1) == 0) :
N_calc >>= 1
else :
N_calc = (N_calc * 3) + 1
return False, calc, N_list呼び出す側はこれで。
is_collatz(number, number-1)実行しました。
1 - 500000 is Collatz Number
calc_total = 2615292
calc_max = 282
calc_max_N = 381727
N_list of 381727 = [381727, 1145182, 572591, 1717774, 858887, 2576662, 1288331, 3864994, ・・・ 1149986, 574993, 1724980, 862490, 431245, 1293736, 646868, 323434]
processing time is 1 secえ？
と思うくらい速くなった(笑)。
１秒です。
さっきの「410011」「448回」だけど、リストをチェックしてみると、
123回目で「288569」になってるんですね。
「288569」は既にコラッツ予想にあてはまることはわかっていますから、ここで終了ということになります。
処理時間を高速化する場合は、やはりループ回数を減らすのが最も効果が高いようです。
となるともっと数字を大きくしたくなるわけで。
「1～50000000（5000万）」でやってみた。
したらメモリエラーになった(笑)。
こんなことしちゃったからね。
N_list_all.append(N_list)メモリエラーは仕方がないとして、PCを電源ボタン長押しの強制終了するはめになった。
例外を拾ってたら大丈夫だったかな。
Windows アプリでは、ブルースクリーンとか、ハングアップとか、突然リセットとかを、最近は見なくなったので少し焦りましたわね。
とりあえずこんなことはやめて、
N_list_all.append(N_list)こんな風にしたらメモリエラーはなくなりました。
if (calc_max < calc) :
N_list_max = N_list１億。4分17秒。
1 - 100000000 is Collatz Number
calc_total = 523898495
calc_max = 613
calc_max_N = 63728127
N_list_max = [63728127, 191184382, 95592191, 286776574, 143388287, 430164862, ・・・ 264112474, 132056237, 396168712, 198084356, 99042178, 49521089]
processing time is 257 sec１0億。44分30秒。
うーん。
リストを作っている影響もあるかもしれないけど。
インタプリタのせいかな。
1 - 1000000000 is Collatz Number
calc_total = 5239038036
calc_max = 644
calc_max_N = 217740015
N_list_max = [217740015, 653220046, 326610023, 979830070, 489915035, ・・・ 228676289, 686028868, 343014434, 171507217]
processing time is 2670 secC++で書く？(笑)
この記事が気に入ったらサポートをしてみませんか？