Collatz Conjecture

I was looking into solving the Collatz Conjecture and I came up with a couple of simple tools and programs to help out.

Collatz Conjecture table of solutions/series produced by a PHP script.

n (n base 2) solutions to 3n+1 and n/2 as a series (in base 2)
1 (1) 1
( 1 )
2 (10) 2, 1
( 10, 1 )
3 (11) 3, 10, 5, 16, 8, 4, 2, 1
( 11, 1010, 101, 10000, 1000, 100, 10, 1 )
4 (100) 4, 2, 1
( 100, 10, 1 )
5 (101) 5, 16, 8, 4, 2, 1
( 101, 10000, 1000, 100, 10, 1 )
6 (110) 6, 3, 10, 5, 16, 8, 4, 2, 1
( 110, 11, 1010, 101, 10000, 1000, 100, 10, 1 )
7 (111) 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 111, 10110, 1011, 100010, 10001, 110100, 11010, 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
8 (1000) 8, 4, 2, 1
( 1000, 100, 10, 1 )
9 (1001) 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 1001, 11100, 1110, 111, 10110, 1011, 100010, 10001, 110100, 11010, 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
10 (1010) 10, 5, 16, 8, 4, 2, 1
( 1010, 101, 10000, 1000, 100, 10, 1 )
11 (1011) 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 1011, 100010, 10001, 110100, 11010, 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
12 (1100) 12, 6, 3, 10, 5, 16, 8, 4, 2, 1
( 1100, 110, 11, 1010, 101, 10000, 1000, 100, 10, 1 )
13 (1101) 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
14 (1110) 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 1110, 111, 10110, 1011, 100010, 10001, 110100, 11010, 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
15 (1111) 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 1111, 101110, 10111, 1000110, 100011, 1101010, 110101, 10100000, 1010000, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
16 (10000) 16, 8, 4, 2, 1
( 10000, 1000, 100, 10, 1 )
17 (10001) 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 10001, 110100, 11010, 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
18 (10010) 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 10010, 1001, 11100, 1110, 111, 10110, 1011, 100010, 10001, 110100, 11010, 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
19 (10011) 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 10011, 111010, 11101, 1011000, 101100, 10110, 1011, 100010, 10001, 110100, 11010, 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
20 (10100) 20, 10, 5, 16, 8, 4, 2, 1
( 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
21 (10101) 21, 64, 32, 16, 8, 4, 2, 1
( 10101, 1000000, 100000, 10000, 1000, 100, 10, 1 )
22 (10110) 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 10110, 1011, 100010, 10001, 110100, 11010, 1101, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )
23 (10111) 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1
( 10111, 1000110, 100011, 1101010, 110101, 10100000, 1010000, 101000, 10100, 1010, 101, 10000, 1000, 100, 10, 1 )

2 axis graph of Collatz conjecture.

6 axis graph of Collatz conjecture.

You can see that the number of steps to get to the final value of 1 depends mostly on how many 1 digits there are in binary value.
The more 0 digits there are the more times it can be divided evenly by 2 which leads to the final value of 1.
Look at the series produced by n=3, n=7 or n=15

1. The reason these values take the most steps to solve is because anything with a 0 can be divided by 2.
For example: 10, 100, 1000, 10000, 100000 will become 1 by the collatz conjecture quickly using the function/rule: n/2 for n%2=0

Step by step solution to n=7. In base 2 and base 10.

base 2 base 10
111 7
1110+111+1 3×7+1
10110 22
1011 22/2
10110+1011+1 3×11+1
100010 34/2
10001 17
100010+10001+1 3×17+1
110100 52
11010 52/2
1101 26/2
11010+1101+1 3×13+1
101000 40
10100 40/2
1010 20/2
101 10/2
1010+101+1 5×3+1
10000 16/2
1000 8/2
100 4/2
10 2/2
1 1

After finding the binary approach to the collatz conjecture and making my graphs,
I found out that others have gone there before:

http://www.journalrepository.org/media/journals/BJMCS_6/2014/Aug/Nag4212014BJMCS12538_1.pdf’

Unfortunately the argument of the paper is that no formal proof to the Collatz conjecture exists due to Hasse’s algorithm.

Here’s a really good video explaining more on collatz conjecture.

Leave a Reply

Your email address will not be published. Required fields are marked *