2. Plan for search

Plan for search

There are several approaches to this problem.

• Searching the number which requires many iterations
• Searching the maximum number during its iteration

Former case, we have very simple answer that for any k, n = 2^k converges to 1 after k times iteration.
So we will consider the latter case.

Searching the maximum value of n during its iteration

In case n=27, maximum value was 9232.
We search the number like this which has large value during its iteration.

1. Condition of termination

When we try an exhaustive search from n=1, we can terminate the computation when the current value becomes smaller than original number.

2. Omitting n which need not search

We need not check the case n is even.
(∵ when n is even, n=n/2 at the next generation, and it is smaller than n.)

Considering the odd case.
The case 4n+1,

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

so 4n+1 always becomes smaller than original value, so we need not check 4n+1.

More generally, the case n is

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

there are possibilities that n is omittable.
Let's search the pair a,b which some interim value always smaller the original number.

Program

 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%