## 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%

E-mail : kc2h-msm@asahi-net.or.jpHisanori Mishima