My Log: 3n+1 Conjecture

The 3n+1 conjecture or the Collatz conjecture is an unsolved conjecture in mathematics. So what is 3n+1 conjecture? From wikipedia:

Take any natural number n. If n is even, divide it by 2 to get n/2, if n is odd multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1.

Even though the idea of the conjecture is very easy to understand, it is suppose to be a very hard problem to solve/prove.

I was doing some learning of the 3n+1 conjecture. As naive as I am, I went right ahead trying to prove the conjecture. Now the problem with me trying to solve this hard problem is that I am not even qualified to be called an amateur mathematician. I am just a programmer with a lot of free time. Furthermore, mathematics is an advanced field and I cannot even comprehend the basic literature on the subject. Anyway, working on this was fun and so I thought I would document it here.

First let us start by the assumption that the 3n+1 conjecture is true, i.e, no matter what number you start with, you will reach the number 1 in the end. To prove this, we will use the method of contradiction. This means that we will say that certain conditions should be met if the conjecture is false. By proving that the conditions supplied or intermediate results break down or contradict with the assumptions before it, we can say that the assumption that the conjecture is false, is false.

So now assuming that the conjecture is false, there should be some number(s) that does not reach 1 when the operations are applied to it infinitely. Let us call the smallest of these numbers X.

So X is the smallest number that violates the 3n+1 conjecture.

(1) Assume that X is an even number.

If X is even, the first operation to do would be X/2.

Since X cannot reach 1, X/2 (which is in the same series) cannot reach 1. This means that X is not the smallest number violating the conjecture (X/2 is smaller).

This contradicts our initial assumption and so X cannot be an even number.

(2) Now, assuming X is an odd number.

Odd numbers can be divided into two types (for our convenience).

The numbers that can be represented as 4n+1.

The number that can be represented as 4n+3.

where n = 0,1,2….

(2.a) If X is an odd number of the type 4n+1:

X = 4n + 1

Since X is odd, the first operation to be done on X would be to find 3X + 1.

3X + 1 = 3 (4n +1) + 1
3X + 1 = 12n + 4

Now the resultant number is an even number and so the next operation will be to divide by 2.

(12n + 4 ) / 2 = 6n + 2

This is still an even number and so we divide by 2 again:

(6n + 2) / 2 = 3n + 1

This means that 3n + 1 is also a number that violates 3n+1 conjecture. Now as you can see, 3n + 1 is a smaller number than X (which is equal to 4n + 1).