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 odd, multiply n by three then add one. If n is even, divide n by 2. 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
- Any sequence which enters a loop of any size is considered terminated.
- Any sequence which diverges, or never repeats a number, is considered to grow to infinity
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:
If n is even divide n by 2. If n is odd, multiply n by three and add one, then divide by two. 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?
