An Automated Approach to the Collatz Conjecture

Emre Yolcu (Carnegie Mellon University)
Theoretical Foundations of SAT/SMT Solving

[mathrodite]

You can add a third case to the Collatz map that is terminating and does exist, but is "hidden" by the even numbers.
| ((n + 1) 3/2) - 1) if n + 1 ≡ 0 (mod 4)
f(n) | ((n - 1) 2/3) + 1) if n - 1 ≡ 0 (mod 8)
| ((n - 1) 1/4) if n - 1 ≡ 4 (mod 8)

The bijective function (n - 1) 1/4 is not immediately obvious in even-odd sequences since the result is absent from the next sequence. Consider all sequences at intervals of 4n+1. With (((n*4)+1)3)+1, you add two factors of 2 – and remove the original n from the sequence. For example:
31 → 94 → 47
125 → 376 → 188 → 94 → 47
501 → 1504 → 752 → 376 → 188 → 94 → 47
2005 → 6016 → 3008 → 1504 → 752 → 376 → 188 → 94 → 47

[mathrodite]

Termination is just a set of common differences that sums to zero.

[pandabearguy]

Every number I tried (over 10 numbers) had the same result, so ya thats proof enough for me.

[romnickbuenaflor]

COLLATZ PROBLEM
Take any positive number N. If the number is odd, multiply by 3 then add 1. If the number is even, remove all factors of 2, or divide by 2^a, where a is the count of all 2 factors of N. Continue. Do you always end up with the loop 1 2 4 1?

FORMAL PROOF:

if N is odd

then the next term N1 = 3N + 1, which is even, 3N being odd (odd closure)

there exist two numbers, both only divisible by 2 such that

2^b-1 <= N1 <= 2^b, where b is the count of factor 2

then these two numbers have a range R = 2^b - 2^(b-1)=2^(b-1) x (2 -1)

R = 2^(b-1)

the even numbers within this range, which N1 may only take, are divsible by 2^a, where a = {1, 2, …, R}, because of the cyclicity of divisibility of numbers, and with the following distribution

1/2 N1/2 + 1/4 N1/4 + 1/8 N1/8 + … + 1/2^(b-1) N1/2^(b-1)

hence, 50% of the time N1 is reduced to half, N1/2, which is greater than N, the original term. But 50% of the time, it is also at the very least reduced to a fourth - N1/4, N1/8, N1/16, …, N1/2^(b-1) - all less than N!

the expected value of the distibution of numbers converges to N/3 as N approaches infinity (back to its original term). However, 50% of the time when it is reduced below N, its expected value is

(1/3 - 1/4) \ 1/2N, the 1/4 being attributed to N1/2
expected reduction = 1/12 \ 1/2 = 1/6 = .1667

Note that the sequence 1/2 + 1/4 + 1/8 + … converges to 1 and since the 1/2 is attributed to N1/2, the rest will have also 1/2, which in turn is used as the latter’s probability normalizing factor.

Hence while the Collatz conjecture increases the N by 3, it also reduces it by about 1/6 afterwards. Meaning, such new term is half the original term N. Its rate of reduction is 2x its rate of increase! No wonder it drops all the way to 1, and enter the loop, 1-4-2-1 in the end, whatever the initial N.

When N is even, it is the same procedure as N1 on reduction.

The empirical proof was just the starting motivation.