コラッツの問題

コラッツの問題とは，任意の1以上の自然数 n は，以下の手続きを繰り返すと必ず1になるか，という問題である．

• n が偶数なら2で割る
• n が奇数なら3倍して1を足す

この問題は正しいか間違っているかまだわかっていない．正しいことを示すには数学的な証明が必要であり，間違っていることを示すには反例を示せば良い．
今，nより小さい自然数については，主張が成り立っているとする．

• n = 2m₁ の場合，次のステップの値は m₁ であり，n より小さいから，手続きを繰り返すと必ず1になる．
• n = 2m₁+1 の場合，次のステップの値は 6m₁+4，その次は 3m₁+2 となりn より大きい．

n = 2m₁+1 の場合について，さらに場合分けを続けるとどうなるだろうか．

リンク

• wikipedia:コラッツの問題

m₁ = 2m₂ の場合とm₁ = 2m₂+1 の場合に分ける．

• n = 2m₁+1 = 4m₂+1 の場合，以下のように 3m₂+1 となり，n より小さくなる．

 n = 4m2+1
 → 12m2+4
 → 6m2+2
 → 3m2+1

• n = 2m₁+1 = 4m₂+3 の場合，以下のように 9m₂+8 となり，n より大きくなる．

 n = 4m2+3
 → 12m2+10
 → 6m2+5
 → 18m2+16
 → 9m2+8

2⁹の場合

2⁹ までで，調べるべき場合は以下の38通りである．他の場合は，元の値より小さくなる．

n	結果
512*m+27	2187*m+121
512*m+283	6561*m+3644
512*m+155	2187*m+668
512*m+411	729*m+587
512*m+91	2187*m+395
512*m+347	729*m+496
512*m+251	2187*m+1079
512*m+507	729*m+724
512*m+71	729*m+103
512*m+327	2187*m+1403
512*m+167	2187*m+719
512*m+423	729*m+604
512*m+103	2187*m+445
512*m+359	6561*m+4616
512*m+231	2187*m+992
512*m+487	729*m+695
512*m+207	2187*m+890
512*m+463	729*m+661
512*m+47	2187*m+206
512*m+303	729*m+433
512*m+111	2187*m+479
512*m+367	729*m+524
512*m+239	6561*m+3077
512*m+495	2187*m+2119
512*m+31	2187*m+137
512*m+287	729*m+410
512*m+159	6561*m+2051
512*m+415	2187*m+1777
512*m+223	729*m+319
512*m+479	2187*m+2051
512*m+63	729*m+91
512*m+319	2187*m+1367
512*m+191	2187*m+820
512*m+447	6561*m+5741
512*m+127	6561*m+1640
512*m+383	2187*m+1640
512*m+255	6561*m+3280
512*m+511	19683*m+19682

大きくなる場合の数

n = 2^k の時，調べるべき場合の数は以下の通り．

k	場合の数
1	1
2	1
3	2
4	3
5	4
6	8
7	13
8	19
9	38
10	64
11	128
12	226
13	367
14	734
15	1295
16	2114

プログラム

#!/usr/bin/perl
use strict;

my $p = shift;
my $max = 2**9;
if ($p) {
    $max = 2**$p;
}
&collatz(1, 0, 1, 0, 0);
exit 0;

sub collatz {
    my ($a0, $b0, $a, $b, $step) = @_;
    if ($a % 2 == 0 && $b % 2 == 0) {
	&collatz($a0, $b0, $a/2, $b/2, $step+1);
    } elsif ($a % 2 == 0 && $b % 2 == 1) {
	&collatz($a0, $b0, $a*3, $b*3+1, $step+1);
    } elsif ($a < $a0 || ($a == $a0 && $b < $b0)) {
	print "$a0*m+$b0 --> $a*m+$b\n";
    } elsif ($a0 >= $max) {
	print "$a0*m+$b0 --> $a*m+$b --> ?\n";
    } else {
	&collatz(2*$a0, $b0, 2*$a, $b, $step);
	&collatz(2*$a0, $a0+$b0, 2*$a, $a+$b, $step);
    }
}