- #1

- 122

- 26

- TL;DR Summary
- The Collatz Conjecture is that for any integer N (N > 0) the sequence formed by:

- Multiplying by 3 and add 1, if N is odd

- Dividing by 2 if N is even

always converges to the sequence ... 4, 2, 1.

Note as soon as the term 3N+1 become divisible by a power of 2 we can repeatedly divide by 2.

For the proof below we rearrange the sequence so it becomes:

If N is odd, multiply by 3 and add 1.

- Repeatedly divide by 2, as many times as the number k, which is defined as the largest number for which N is divisable by 2

- Muliply by 3 and add 1

What is the chance for a value of k greater then 0?

k chance 3N+1 is divisable by 2

-- ---------

1 1

2 1/2

3 1/4

4 1/8

or for any k, the chance is 1/2

The sequence we can then redefine as (3N+1)/2

If we calculate the average factor for each step defined above, as the sum of the series 1/2+1/4+1/8+... is 1, this factor converges to (3N+1)/2

Hence, the sequence must always converge to 1.

For the proof below we rearrange the sequence so it becomes:

*First step:*If N is odd, multiply by 3 and add 1.

*Each next step:*- Repeatedly divide by 2, as many times as the number k, which is defined as the largest number for which N is divisable by 2

^{k}. Note that k is at least 1, and the resulting number is always odd.- Muliply by 3 and add 1

What is the chance for a value of k greater then 0?

k chance 3N+1 is divisable by 2

^{k}-- ---------

1 1

2 1/2

3 1/4

4 1/8

or for any k, the chance is 1/2

^{k-1}The sequence we can then redefine as (3N+1)/2

^{k}.If we calculate the average factor for each step defined above, as the sum of the series 1/2+1/4+1/8+... is 1, this factor converges to (3N+1)/2

^{1+1}= (3N+1)/4, which is smaller then N. So on average, each step will yield a smaller number.Hence, the sequence must always converge to 1.

Last edited: