Trying to prove that Collatz conjecture is true using probability
If 3N + 1 results in a random even number we have the formula:
(3N + 1) / 2^K where K is the number of factors of 2 factors that 3N + 1 results.
After applying this formula to N we can have 1 or an odd number and this process will only stop if N reaches 1
If all evens have factors of 2 but the quantity of those factors varies but have a probability which is:
50% of evens have 1 factor of 2
25% of evens have 2 factors of 2
12.5% of evens have 3 factors of 2
6.25 % of evens have 4 factors of 2
...
so we assume the distribution of probabilities are:
100% / 2^K = probability of a even number having K factors
If K = 1 then: (3N + 1) / 2 = 1.5N + 0.5, N will grow
if you apply this formula in almost 50% of cases, N will grow by a factor of 1.5N + 0.5
Since this formula is applied in 1 out of every 2 cases, we will have: 1.5N + 0.5
So what would the worst-case scenario have to be for it to decrease?
If K = 2 then:
(3N + 1) / 2 = 1.5N + 0.5
[(1.5N + 0 .5) * 3 + 1] / 4 = 1.125N + 0.625, N stills grows
If K = 3 then:
[(1.125N + 0.625) * 3 + 1] / 8 = 0.421875N + 0,359375, N will decrease
The chance of K being at least 3 is 25% because:
(12.5% of K = 3 + 12.5% of K > 3) = 25% of K >= 3
The average case to get K >= 3 will be 4 so we will get the following average:
2 cases of K = 1 (50%)
1 case of K = 2 (25%)
1 case of K = 3 (worst case because if K > 3 then will decrease even more)
The result will be:
(3N + 1) / 2 = 1.5N + 0.5
[(1.5N + 0.5) * 3 + 1] / 2 = 2.25N + 1.25
[(2.25N + 1.25) * 3 + 1] / 4 = 1,6875N + 1,1875
[(1,6875N + 1,1875) * 3 + 1] / 8 = 0,6328125N + 0,5703125, N will decrease
This proof for every 4 cases the probability of worst case decreasing is higher than worst case of 2 cases and for an average of 4 cases the worst case decrease is more than the worst case of 2 cases, proofing the more you repeats this formula the higher will be the probability of N decreasing.
Another fact that need to be mentioned is that:
K is limited to the intervals of 2^E to 2^E + 1
So the max number K can be in the interval of 2^E to 2^E + 1 is E
If N is present in 2^E to 2^E + 1 then getting K = 1:
(3N + 1) / 2 = 1.5N + 0.5, still on this interval
Getting K = 1 again:
[(1.5N + 0.5) * 3 + 1] / 2 = 2.25N + 1.25, goes to the next interval
For example:
2^4 to 2^5 = 16 to 32
the max number K can be is limited to 4
If we get K = 1 two times the interval will increase, consulting the probability distribution we have:
50% of evens have 1 factor of 2
25% of evens have 2 factors of 2
12.5% of evens have 3 factors of 2
6.25 % of evens have 4 factors of 2
...
Meaning the chance of decreasing will also become higher if N grows.
Finally, we know that up to 1,000,000,000,000 it is true, and once N reaches a number less than that, it is guaranteed to become 1
And also it's impossible for a number bigger than this get directly turned into 1 because it's N / 2 every time N is even ;
plus the more you repeat this formula the higher the chances of N decreasing, proving this conjecture is true.
