黄昏より暗きもの、血の流れより赤きもの

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

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

Project Euler 14:計算回数の多いコラッツの問題を考える

Project Euler

序章

今日のProject Eulerコラッツ予想と言うものを背景としたものだ。ここでコラッツ予想とは、自然数nに対する以下の関数


f:id:program_study:20150412002506p:plain

がある。このとき全てのnに対して合成写像*1fを有限回行うと、f(f(f(f....f(n))) = 1が成立するという予想を指す。例えばn=3ならば、

1回目の合成写像: f(3) = 10 (3*3+1)
2回目の合成写像: f(f(3)) = f(10) = 10 -> 5 (10/2)
3回目の合成写像: f(f(f(3))) = f(5) = 16
4回目の合成写像: f(f(f(f(3)))) = f(16) = 8
5回目の合成写像: f(f(f(f(f(3))))) = f(8) = 4
6回目の合成写像: f(f(f(f(f(f(3)))))) = f(4) = 2
7回目の合成写像: f(f(f(f(f(f(f(3))))))) = f(2) = 1

この合成写像の様子を簡単に書くと、n=3のとき「3->10->5->16->8->4->2->1」と7回の合成写像で1へ写像される。簡単に言えば7回操作を行えば1に行き着く。このように全ての自然数nに対し、f(n)を繰り返すと最終的に1となるかどうかが議論されている。

問題とその和訳

Longest Collatz sequence Problem 14
The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)
n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.

問題を2通りに和訳すると、「コラッツ予想において、n<=1,000,000を満たすnにおける合成写像fの回数をTが最大となるようなnを求めよ」「自然数nにおいて、nが偶数のときはn/2、nが奇数のときは3n+1を出力する操作をfとする。n<=1,000,000を満たすnにおいて、操作fの回数が最大となるようなnを求めよ」と言うものだ。

ソースコード

C言語ソースコードは以下の通り。ソースコードの説明の前に、int,long int,long long intを扱う型について確認したい。「プログラミング言語 C の新機能:整数型」の情報を基にまとめると以下のようになる。

最大値
int +32,767
long int +2,147,483,647
long long int +9,223,372,036,854,775,807

例えばここでn=10,925の場合f(10,925) = 3 * 10,925 + 1 =32,776 > 32,767よりintの桁を超えてしまう。このように途中の合成写像の過程でintの桁数を超えてしまう場合がある。このためコラッツ予想における関数を計算するときは、その整数の桁をlong int以上に設定しておくとよい。Project Eulerの場合基本的に扱う数字が大きいので、あらかじめlong intで指定した方が良いのかもしれない。そんな訳でつたないがソースコードを実行してみた。

ソースコード

実行結果

f:id:program_study:20150412002628p:plain

上記を見るとn=837,739のとき、合成写像fの回数が最大となるようだ。macbookで計測した所の実行時間も約1.705[s]であった。

参考資料