# Collatz Conjecture

#### Trenly

I was recently thinking back to the collatz conjecture and decided to just think about it for a while. For those who do not know, the conjecture is basically this:

If n is even divide n by 2. If n is odd, multiply n by three then add one. Take that answer and repeat the process such that you have a sequence. For any positive even integer n, does the sequence ever not terminate at 1?

My thoughts:

• Any sequence which reaches 1 terminates as it enters the loop 1>4>2>1
[*]Any sequence which contains a number known to terminate at 1, also terminates at one​
[*]All odd numbers do not need to be checked
[*][*]Take a and b to both be positive odd integers.
[*]a can be written as 2c+1 by the definition of an odd number
[*]b can be written as 2d+1 by the definition of an odd number
[*]a*b = (2c+1)(2d+1) by subsitution
[*](2c+1)(2d+1) = 4cd+2c+2d+1 by distribution
[*]4cd+2c+2d+1 = (4cd+2c+2d)+1 by association
[*](4cd+2c+2d)+1 = 2(2cd+c+d)+1 by distribution
[*]2(2cd+c+d)+1 is an odd number by definition. any integer multiplied by 2 and added to 1 is odd.
[*]Any odd number plus one is even by definition
[*]Therefore, after one iteration any odd number will become even.​
[*]For any integer a where n is equal to 2^a the sequence will terminate at 1
[*]Since 2^a is even, and can be divided by 2 exactly a times, the product of each iteration becomes 2^a-k where k is the current iteration
[*]When a=k then the product of the iteration will be 2^a-a which is 2^0 which is equal to 1​
Based on the proof above, does that mean that a solution to the problem would be to determine if all the series eventually reach a point of 2^n? Thereby making the conjecture:

For any positive integer n; If n is even divide n by 2. If n is odd, multiply n by three then add one. Take that answer and repeat the process such that you have a sequence. For any positive integer n, does the sequence ever not contain a value 2^n?

#### Hedge

That's a lot of words to say something fairly simple. Yes, the 3n+1 step by definition will give you an even number. Yes, when it is 2^a that is the end of the chain as it will go to 1. And yes, you are right, one way to think about attacking the problem is to consider whether all chains starting from b will reach 2^a before they reach b(2^a). But that doesn't actually help very much as this is a horribly difficult thing to prove. Think for instance about the negative loops starting from -5 and -17. Why do those numbers lead to -5( 8 ) and -17(2048 ) rather than to a power of 2? If you could answer that question you might have a start on the problem.

#### isaac

Think for instance about the negative loops starting from -5 and -17. Why do those numbers lead to -5( 8 ) and -17(2048 ) rather than to a power of 2? If you could answer that question you might have a start on the problem.
answering to that question will give you nothing

for any given loop (negative or positive) grater then 3 values the minimum value of that loop will be 12k+7 or 12k+11

12(-1)+7=-5
12(-2)+7=-17

you can even go further

96k+7
96k+31
96k+79
96k+91

96k+47
96k+59
96k+71
96k+95

etc...

#### Hedge

answering to that question will give you nothing

for any given loop (negative or positive) grater then 3 values the minimum value of that loop will be 12k+7 or 12k+11
That might depend on what the answer was although I grant you it is most likely as much of a dead-end as any other path.

What do you mean by minimum value and '3 values' in the sentence above, out of curiosity?

#### isaac

That might depend on what the answer was although I grant you it is most likely as much of a dead-end as any other path.

What do you mean by minimum value and '3 values' in the sentence above, out of curiosity?
Any cycle has a minimum and maximum value to it as well as "size"

4 -> 2 -> 1 is a cycle with 3 values (2 even and 1 odd) "size" of 3

minimum value is 1
maximum value is 4

What I wrote above is for cycles with "size" of 5 or higher,
where the minimum value will be 12k+7 or 12k+11.

Last edited by a moderator:

#### tonykuo1985

What if instead of an odd number uses prime number then applied 3n+1 to the prime number and uses 2^n+1 you might find the answer