1
3n+1 Problem
Definition 1 (3n + 1 process). For an arbitrary positive integer n, define the
following sequence of operations: if the result of the last operation is an odd
number, multiply it by three and add 1. Otherwise divide the result of the last
operation by two.
Conjecture (Collatz Conjecture). For any n N the 3n + 1 process will after
a finite number of steps result in the value 1.
We set out to prove the above conjecture.
Derivation of Congruence Relations
We can combine the two steps of the process as one step:
nj+1 =
3nj + 1
, xj 1, nj 1
2xj
nj =
...
3(
3n0 +1
)+1
2x1
2x2
...
(mod 2)
(1)
+1
(2)
2xj
Remark. Given a n0 1 (mod 2), consecutive iterations of ( 1) clearly give:
n1 n2 nj 1 (mod 2) for any j N.
Definition 2 (Sum of powers). x1:j =
j
X
xd
d=1
Corollary 1 (By Definition 2 and equation 1). x1:j j
We proceed:
nj =
3j n0 + 3j1 + 3j2 2x1:1 + + 3jj 2x1:j1
2x1:j
(3)
We therefore define a congruence function f (n0 , j):
f (n0 , j) = 3j n0 + 3j1 + 3j2 2x1:1 + + 30 2x1:j1 0
(mod 2x1:j )
(4)
We group these terms into a sum (where x1:0 = 0) and divide out the 3j
(giving valid inverses modulo powers of two as the powers of three are a subgroup). Note that this does not change the maximal power of two within which
1
f (n0 , j) 0, as (2, 3) = 1.
f (n0 , j) = n0 +
j1
X
2x1:t 3(t+1) 0
(mod 2x1:j )
(5)
t=0
Now take 2j > n0 , and assume that x1:j+1 = x1:j + 1, that is xj+1 = 1.
Then the next congruence of this form is:
f (n0 , j+1) = n0 +
j1
X
2x1:t 3(t+1) +2x1:j 3(j+1) = 2x1:j wj +2x1:j 3(j+1) +f (n0 , j) 0
t=0
(6)
where wj is odd.
Since n0 < 2j 2x1:j , it does not change between these congruences. Thus
f (n0 , j) only has contributions from the powers of three changing. To clarify
this contribution, we need the following corollary:
Corollary 2 (Difference in a third power modulo consecutive powers of 2).
Powers of 3 generate a cyclic subgroup of the multiplicative group modulo 2k of
order 2k2 . For a given k, a power of 3 is either of the same equivalence class
in 2k and 2k+1 , or differs by a factor of 2k . Proof:
If for some odd h0 < 2k :
3r 2k h0 (mod 2k and 2k+1 )
3r+1 2k+1 + 2k 3h0 (mod 2k and 2k+1 )
3h0 < 2k+1 + 2k , and hence 3h0 can not include both 2k+1 and 2k when
written in binary. The first term is 0 (mod 2k and 2k+1 ), and hence 3h0 can
at most differ by a factor of 2k between the congruences. We then do a change
of variables h1 = 3h0 and repeat the process for all distinct powers of 3.
k+1
This applies to negative powers of three as well, as 31 32
(mod 2k ).
32
Therefore, we can now write (using {0, 1}3(t+1) to denote whether 3(t+1)
changes from one congruence to the next) the change between f (n0 , j) and
f (n0 , j + 1) as:
f (n0 , j) = 2
x1:j
j1
X
x1:t
x1:j
{0, 1}3(t+1) 2
t=0
j1
X
2x1:t {0, 1}3(t+1)
(mod 2x1:j+1 )
t=0
(7)
(mod 2x1:j+1 )
Plugging this back into the main congruence, we have:
f (n0 , j +1) = 2x1:j (wj +3(j+1) +
j1
X
2x1:t {0, 1})3(t+1) 0
(mod 2x1:j+1 ) (8)
t=0
(wj + 3(j+1) +
j1
X
2x1:t {0, 1}3(t+1) ) 0
(mod 2)
(9)
t=0
Since 3(j+1) is odd and thus wj + 3(j+1) is even, and because the terms
for t > 0 have x1:t t, we only have to verify the term corresponding to t = 0,
i.e. the change in 31 :
2x1:0 {0, 1}31 {0, 1}31 0
(mod 2)
(10)
To find when 31 changes, we use the following representation:
Corollary 3 (Representation of 31 modulo powers of two). For a given power
of two, we have:
1+
k2
bX
2 c
22j+1 (mod 2k )
j=0
Thus when x1:j is even, the equivalence class of 31 changes from one congruence to the next. Hence x1:j 0 (mod 2) xj+1 6= 1. Thus, taking c
to index the first division by 2 after nj , the minimal growth rate of x1:j+c to
x1:j+c+h is a sequence of xj+c = 1, xj+c+1 = 3, , as an odd exponent is always
needed to make the overall exponent odd after the previous increment made it
even. That is, even exponents simply make the sum of exponents larger without
allowing for further x1:j+c+b = 1.
3n
+1
Hence for every time we have nj+c+b+1 = j+c+b
we must have nj+c+b+2 =
2
for r 0. Now since if nj+c+b > 1 we have:
3nj+c+b+1 +1
23+r
3nj+c+b +1
2
< 2nj+c+b and hence nj+c+b+2 <
6nj+c+b +1
23
< 78 nj+c+b
Since the 1, 3, pattern makes the current n shrink in relation to nj+c ,
higher exponents can only speed this process up. Hence nj+c+h must tend to 1
as h tends to infinity. This completes the proof.
30/05/2015
dd0df0a39dd1bc4491fb74fe96149dc9454d125b9748362f08d1069bb606bbe4