2.探査方針

探査方針

この問題については、以下のような対応方針が考えられる。

ここでは、後者について考える。
前者については、例えば、任意の k について、n = 2k は k 回で 1 に収束するということが容易にわかるので、特に考えない。

途中で大きな値をとるものを探す

n=27 の時、途中の最大値は 9232 になった。 このように、途中で大きな値をとるものを探してみる。
n=3 からはじめて、n を順に大きくしていく。
最大値 max は、初期値を 1 としておいて、ループの中で毎回比較し、大きかったら更新していく。
とりあえず、107 ぐらいまでやってみたいが、このままでは効率が悪いので、少し考えてみる。

1. 終了条件の変更

プログラムでは終了条件を n=1 としたが、小さい方からしらみつぶしに探査していくのであれば、
最初の例で見たように、中間結果が n より小さくなった時点で終了してよい。これで多少は速くなる。

2. 探査不用な n のふるい落し

まず n が偶数の時は調べなくてよい。
(∵ n が偶数の場合、次に n=n/2 となるが、これは n より小さい)
これだけでも、調べる対象が半分になる。

残った奇数について少し考えてみる。
例えば、4n+1 の形の奇数について考えてみよう。
これは奇数だから、次に 3 をかけて 1 を足すことになる。

3*(4n+1)+1 = 12n+4

これは偶数であり、2 で 2 回割ることができる。

12n+4 = 4(3n+1) ⇒ 3n+1

ここで、

3n+1 < 4n+1

だから、4n+1 の形の奇数も探査対象からはずしてよい。
これでさらに探査対象が半分になる。
さて、このような数は他にないか。

4n+1 がうまくいった理由は、2 で 2 回割れた点にある。
これは n の係数が 2 のべき乗だったから生じた結果である。
そこで、

an+b   (a=2k, b=1, 3, ... , a-1)

の形の式について、中間結果が最初よりも小さくなるような a, b の組を探してみる。

プログラム

 10   ' collatz2
 20   ' an+b , b=1,3,... a-1 , a=2^k
 30   input K:A=2^K:dim T%(A\2):for I%=1 to A\2:T%(I%)=0:next I%
 40   for B=1 to A-1 step 2:C=A:D=B
 50     C=C*3:D=D*3+1
 60     if and{even(C),even(D)} then C=C\2:D=D\2:goto 60
 70     if C<A then 90
 80     if even(C) then 50
 90     if C>A then T%((B+1)\2)=1
100   next B
110   for I%=1 to A\2
120     if T%(I%)=1 then print I%*2-1
130   next I%
140   N=A
150   for I%=1 to A\2
160     if T%(I%)=0 then 180
170     M=N+I%*2-1
180   next I%

最後の150〜180で、ふるい落とせなかった n を出力するようにしている。
この値が、収束するかどうか自明でない(初期の段階で自分自身より小さくならない)数である。


この章の目次

E-mail : kc2h-msm@asahi-net.or.jp
三島 久典