Collatz（コラッツ）の予想は，角谷（かくたに）予想ともいいます。次のプログラムが必ず停止するという予想です。
class Collatz {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
while (n > 1) {
if (n % 2 == 0) n = n / 2;
else n = 3 * n + 1;
System.out.println(n);
}
}
}
これを Collatz.java として保存し，
javac Collatz.java
でコンパイルします。
java Collatz 30
などのように適当な数を与えて実験してみましょう。
java Collatz 30 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
どんな数から始めても，必ず1になりそうです。
遊んでいるうちに，変な現象に出会うかもしれません。
java Collatz 113383 340150 170075 510226 255113 765340 382670 191335 574006 287003 861010 430505 1291516 645758 322879 968638 484319 1452958 726479 2179438 1089719 3269158 1634579 4903738 2451869 7355608 3677804 1838902 919451 2758354 1379177 4137532 2068766 1034383 3103150 1551575 4654726 2327363 6982090 3491045 10473136 5236568 2618284 1309142 654571 1963714 981857 2945572 1472786 736393 2209180 1104590 552295 1656886 828443 2485330 1242665 3727996 1863998 931999 2795998 1397999 4193998 2096999 6290998 3145499 9436498 4718249 14154748 7077374 3538687 10616062 5308031 15924094 7962047 23886142 11943071 35829214 17914607 53743822 26871911 80615734 40307867 120923602 60461801 181385404 90692702 45346351 136039054 68019527 204058582 102029291 306087874 153043937 459131812 229565906 114782953 344348860 172174430 86087215 258261646 129130823 387392470 193696235 581088706 290544353 871633060 435816530 217908265 653724796 326862398 163431199 490293598 245146799 735440398 367720199 1103160598 551580299 1654740898 827370449 -1812855948
あれあれ，マイナスになってしまいました。どうしてでしょう？
テストのために次のようなプログラムを作ってみました。
class Test {
public static void main(String[] args) {
int n = Integer.parseInt(args[0]);
for (int i = 0; i < 10; i++)
System.out.println(n + i);
}
}
これは入力した数から始まる10個の数を出力するものです。2147483643あたりから始めてみましょう。
java Test 2147483643 2147483643 2147483644 2147483645 2147483646 2147483647 -2147483648 -2147483647 -2147483646 -2147483645 -2147483644
2147483647の次が負の数になることがわかります。つまり，Javaの int 型の数は
1
2
3
……
2147483645
2147483646
2147483647 (= 231-1)
-2147483648 (= -231)
-2147483647
-2147483646
……
-3
-2
-1
0
のように環状になっているのです。全部で 232 通りあり，int 型の数はコンピュータの中では32ビットで表されていることがわかります。
int 型は 231-1 = 2147483647
まで表せます。この数のことを Integer.MAX_VALUE と表します。
232 通りでは足りない場合は，264 通りの数が表せる long 型を使います。この場合，最初のプログラムは次のようになります。
class Collatz {
public static void main(String[] args) {
long n = Long.parseLong(args[0]);
while (n > 1) {
if (n % 2 == 0) n = n / 2;
else n = 3 * n + 1;
System.out.println(n);
}
}
}
long 型なら 263-1 = 9223372036854775807
まで表せます。この数のことを Long.MAX_VALUE と表します。
いくら long 型でも溢れることはあります。そこで，次のようにするとよいでしょう。
class Collatz {
static final long LIMIT = (Long.MAX_VALUE - 1) / 3;
public static void main(String[] args) {
long n = Long.parseLong(args[0]);
while (n > 1) {
if (n % 2 == 0) n = n / 2;
else if (n <= LIMIT) n = 3 * n + 1;
else break;
System.out.println(n);
}
}
}
long 型でも足りない場合は，多倍長計算を使います。以下のものはあまり効率の良いものではありません：
import java.math.BigDecimal;
class Collatz2 {
public static void main(String[] args) {
BigDecimal n = new BigDecimal(args[0]);
BigDecimal zero = new BigDecimal("0");
BigDecimal one = new BigDecimal("1");
BigDecimal two = new BigDecimal("2");
BigDecimal three = new BigDecimal("3");
while (! n.equals(one)) {
if (n.remainder(two).equals(zero)) n = n.divide(two);
else n = n.multiply(three).add(one);
System.out.println(n);
}
}
}
Last modified: 2005-12-26 11:11:49