この問題については、以下のような対応方針が考えられる。
ここでは、後者について考える。
前者については、例えば、任意の k について、n = 2k は k 回で 1 に収束するということが容易にわかるので、特に考えない。
n=27 の時、途中の最大値は 9232 になった。
このように、途中で大きな値をとるものを探してみる。
n=3 からはじめて、n を順に大きくしていく。
最大値 max は、初期値を 1 としておいて、ループの中で毎回比較し、大きかったら更新していく。
とりあえず、107 ぐらいまでやってみたいが、このままでは効率が悪いので、少し考えてみる。
プログラムでは終了条件を n=1 としたが、小さい方からしらみつぶしに探査していくのであれば、
最初の例で見たように、中間結果が 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 を出力するようにしている。
この値が、収束するかどうか自明でない(初期の段階で自分自身より小さくならない)数である。
前 | この章の目次 | 次 |
---|