The Collatz Conjecture

The Collatz Conjecture is a simple statement that is hard to prove. Given the funtion

f(x) = 3x+1 if x is odd, otherwise x/2

and the sequence generator

S(m) : a₀ = m, a_n = f(a_n-1)

For any positive integer m, does there exist a positive integer n such that a_n = 1?

Here are some generated sequences as examples.

1 -> 4 -> 2 -> 1. This demonstrates that 1 is a loop.
2 -> 1. Powers of 2 simplify easy
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1. Longest string so far is 1 below a power of 2
4 -> 2 -> 1. Powers of 2 simplify easy
5 -> 16 -> 8 -> 4 -> 2 -> 1. This sequence is a subsequence of 3s expansion

graphing the length of each generated sequence gives a chaotic graph.

If you continue these expansions you may notice a few things.

All the numbers have given 1 eventually (If you found a number that doesnt, you just solved the collatz conjecture)
There is alot of repetition. for example, 5s sequence is a subsequence of 3s sequence

To solve the repetition problem let -> be defined as follows. a -> b iff b is an element in S(a). So if b shows up after a then a -> b. -> is transitive so it lets us skip known subsequences. -> helps abstract away the number of iterations and focuses on if a number reaches a known 1 terminating sequence. The following example shows strips away even numbers using ->. This reasoning behind this will be explained in the next section

1 -> 4 -> 2 -> 1.
2 -> 1.
3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 1. notice that 2 is ommited since we already know 4 -> 2 -> 1
4 -> 1. Powers of 2 simplify easy
5 -> 1. 5s expansion is simplified alot since it is a subsequence of a previous sequence

Graphing the length of each sequence excluding even numbers gives a familiar graph

When compared to the earlier graph that includes even numbers the shapes are nearly identical

graphing the ratio between the graphs shows an average ratio around 3 with spikes around powers of 2

Prime Factors, and Simple 2s

When first tackling the problem, abstracting away the 2s is usually the first step. Since even numbers are divided by 2 until they are odd, they strip away all the 2s from a numbers prime factorization. For example, look at the collatz sequences of numbers broken into their prime factors

3 = 3 -> 1.
6 = 2*3 -> 3 -> 1
12 = 2*2*3 -> 2*3 -> 3 -> 1
24 = 2*2*2*3 -> 2*2*3 -> 2*3 -> 3 -> 1

Notice all the powers of two vanish and leave 3. In general x*2ⁿ -> x. This means x*2ⁿ forms an equivilance class that all collapse to n. In effect this means we ignore powers of 2, and we can now focus only on odd numbers. Lets look at the collatz sequences focusing on prime factorizations ignoring powers of 2.

3 -> 5 -> 1
5 -> 1
7 -> 11 -> 17 -> 13 -> 5 -> 1
9 -> 7 -> 1
11 -> 1
13 -> 1

The pattern in prime factorizations is hard to follow, so we need a change in perspective.

Binary Representation

Binary represents the problem well in a couple of ways. We will use the term binary string to mean the binary representation of a number. s will be used to a group of digits of variable length and values. exponentiation of a binary string will be interpeted as repetition of those digits.

Binary limit the number of digits. This can help in finding patterns and approaching the problem in different ways
Dividing by 2 until even is super easy in binary. s0ⁿ -> s
3x+1 can be interpeted as 2x+x+1 which in binary is equivilant to s1+s

Lets look at some examples.

1: 1 -> 100 -> 1.
3: 11 -> 1010 -> 101 -> 10000 -> 1.
5: 101 -> 1
7: 111 -> 1011 -> 10001 -> 1101 -> 101 -> 1

Here are som general rules for simplifying binary strings

s0ⁿ -> n.
s1(01)ⁿ -> s1
s01ⁿ -> (3s+1)01^n-1
s10ⁿ1 -> (3s+1)10^n-21

This may look unorganized, but the inverses have patterns. The following is an example. note that multiples of 3 are skipped because they have no inverses.

101 -> 1
undefined -> 3
11 -> 5
1001-> 7
undefined -> 9
111 -> 11
10001 -> 13
undefined -> 15
1011-> 17
11001-> 19
undefined -> 21
1111-> 23
100001 -> 25

It may be hard to see but the inverses are ordered in a binary fractal.

Binary Fractal, and the Binary Lookup

To explain the idea of the binary fractal, look at the pattern in the number of factors of 2 in the natural numbers.