## Chapter 7 : Collatz's Conjecture (E16 The 3x+1 problem)

(First : June 04, 2001; update : April 12, 2008) [Japanese]

### Abstract

Lothar Otto Collatz conjectured that

for any integer n,

• when n is even, then divide by 2 (n ⇒ n/2)
• when n is odd, then multiply by 3 and add 1 (n ⇒ 3n+1)

n always converges to 1.

all n ≤ 2*1015 was checked (For current situation, please check here).

Sometimes n becomes very large during the iteration of computation.
Let max(n) be the maximun value of n during its iterations. Then it seems to be,

max(n) ≤ na,   a=2+ε (conjecture)

If this conjecture is right, then any n has a finite upper bound for its iteration,
so we can prove that any n does not divergent to infinity.
(But there still remains a possibility of a loop.)

In order to understand the difficulty of this problem,
please try to challenge following questions.

• Q1 : Does 27 converge to 1 ?
• Q2 : How about 447 ?
• Q3 : Can you construct the number which converges after n times iterations ?

### Contents

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