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

クロビーボ

私的忘備録

コラッツの問題のプログラム

整数論の未解決問題の一つとしてコラッツの問題というものがあるそうです。

これは、問題自体はとても簡単で、小学生でもわかって楽しめるものになってます。

なんでもいいので一つ正の整数を思い浮かべてみましょう。


思い浮かべましたか?

その整数をnとしましょう。

そのとき、nが偶数か奇数かによって次の操作を考えましょう。

(i)  nが偶数のとき、nを2で割る。
(ii) nが奇数のとき、nを3倍して1を足す。

この操作で得られた数にさらに上の操作を施すということを繰り返すと最終的に1になるであろうというのがこのコラッツの予想です。

例えば、nとして13としたとき、

13は奇数なので操作(ii)を施すと 13×3+1=40 が得られ、
40は偶数なので操作(i)を施すと 40÷2=20、
20は偶数なので操作(i)を施すと 20÷2=10、
10は偶数なので操作(i)を施すと 10÷2=5、
5は奇数なので操作(ii)を施すと 15×3+1=16、
16は偶数なので操作(i)を施すと 16÷2=8
8は偶数なので操作(i)を施すと 8÷2=4、
4は偶数なので操作(i)を施すと 4÷2=2、
2は偶数なので操作(i)を施すと 2÷2=1

となって確かに1になりましたね。

簡単に書くと

13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1

という数列が得られました。

(ここで、a->b は操作(i)または操作(ii)を一回施すことによってaからbが得られることを意味しています。)


もう少し続けてみると、

1は奇数なので操作(ii)を施すと 1×3+1=4、
4は偶数なので操作(i)を施すと 4÷2=2
2は偶数なので操作(i)を施すと 2÷2=1

となって

1 -> 4 -> 2 -> 1 -> ・・・

のサイクルとなることがわかります。


ちなみに、Wikipediaによると、このコラッツ予想は、5×2^60まで正しいことが確かめられているそうです (参考: コラッツの問題 - Wikipedia)


今回はこのコラッツ予想を確かめるプログラムをJavaで作成したので、
以下に記載しました。

上で確かめたように操作(i)(ii)を繰り返し施すと1 -> 4 -> 2 -> 1 -> ・・・のサイクルになりますので、与えられた正の整数nから操作(i)(ii)を繰り返して最初に1になるまでに得られる数列を求めるプログラムとしました。



import java.util.*;

public class Collatz_problem {
	
	static Scanner sc = new Scanner(System.in);
	
	public static void main(String[] args) {
		int n;
		do {
			System.out.println("正の整数を入力してください:");
			n = sc.nextInt();
		} while (n <= 0);
		
		int counter = 1;
		System.out.println("以下がn="+n+"に対するCollatz数列です");
		System.out.println("#"+counter+": "+n);

		while(n != 1) {
			if(n % 2 ==0) {
				n = n / 2;
			} else {
				n = 3 * n + 1;
			}
			counter++;
			System.out.println("#"+counter+": "+n);
		}
	}
}

例えば、以下の入力に対して

13
101
70
50

次のような出力が得られます。

以下がn=13に対するCollatz数列です
#1: 13
#2: 40
#3: 20
#4: 10
#5: 5
#6: 16
#7: 8
#8: 4
#9: 2
#10: 1

以下がn=101に対するCollatz数列です
#1: 101
#2: 304
#3: 152
#4: 76
#5: 38
#6: 19
#7: 58
#8: 29
#9: 88
#10: 44
#11: 22
#12: 11
#13: 34
#14: 17
#15: 52
#16: 26
#17: 13
#18: 40
#19: 20
#20: 10
#21: 5
#22: 16
#23: 8
#24: 4
#25: 2
#26: 1

以下がn=70に対するCollatz数列です
#1: 70
#2: 35
#3: 106
#4: 53
#5: 160
#6: 80
#7: 40
#8: 20
#9: 10
#10: 5
#11: 16
#12: 8
#13: 4
#14: 2
#15: 1

以下がn=50に対するCollatz数列です
#1: 50
#2: 25
#3: 76
#4: 38
#5: 19
#6: 58
#7: 29
#8: 88
#9: 44
#10: 22
#11: 11
#12: 34
#13: 17
#14: 52
#15: 26
#16: 13
#17: 40
#18: 20
#19: 10
#20: 5
#21: 16
#22: 8
#23: 4
#24: 2
#25: 1