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).
So again by the method of contradiction we can safely say that the number X will not be of the form 4n + 1.
So finally we are left with odd numbers of the form 4n + 3.
So we know that any number that violate the 3n + 1 conjecture will be of the form 4n + 3.
Proving this last part is left to the reader as an exercise. (I mean, I did try this part for a few days, but it didn’t go anywhere.)
Very nicely thought out. But when we say that all odd numbers can be represented as 4n+1 or 4n+3, aren’t we assuming that in some cases n=0? And if so, we’re using whole numbers to prove a conjecture based on natural numbers…
I don’t know if this introduces hidden subtleties (as you said, real analysis is a complicated subject), but I wouldn’t be surprised. After all, mathematicians are a fussy lot
You can start from n=1 if you want. For n=0, it is trivial to solve the problem anyway.
Good try. Started with 4n+3…
what all were ur approches for this which failed?
Here is one approach:
First, find the values in the series by applying the operations: X0, X1, X2……
Now, convert all these numbers to the form 4n + c (where c = 1 or 3).
Now take the values of all the “n”s and make the series: n0, n1, n2,…
You can see that these values of n “kinda” follow an original 3n+1 series. Now, If you can show that the “n”s follow the same series, the problem is solved. If the “n”s follow the same series, it means that the n0, n1, n2… series will eventually reach 1, because n0 is less than X0, and x0 is the smallest number that violates the conjuncture. This is turn means that X0 will also reach 1.
The flaw with this logic is that I could not factor in the constants (+1 and +3) in each series. You can see some patterns on *when* the +1 changes to +3 though.
In the same way for 4n+3, I suppose it would reach some stage where we will have to prove that number X will not be of the form 9n+8. but now , there emerges two case within, where the number can be odd or even . So may be, for 4n+3 an all together different approch could be taken.
Good try..
We all know that 1+2+4+…+2n-1 = 2n – 1. I conjecture that 1+3+9+…+3n-1 = 3n
– 1 but soon realise that my first few results are twice as big as I want them to
be. On this basis I guess that the correct answer is (3n – 1) / (3 – 1). Show that
this is indeed the case.
try this!!
Kash, your conjecture is correct for the following reason:
Let f(x) = x^n – 1, where n is any natural number.
Clearly 1 is a root of f since f(1) = 1^n – 1 = 0. This implies that (x-1) is a factor of f. It is easy to verify by multiplying out that f can be factored as follows:
f(x) = x^n – 1 = (x – 1)(x^(n-1) + x^(n-2) + … + x + 1)
Divide both sides by (x-1) and reorder to get the following equality:
1 + x + x^2 + … + x^(n-1) = (x^n – 1) / (x – 1)
Substitute x=3 into this general case and we get your conjecture. But how does that help prove the Collatz conjecture?
….good..i am think so..
Clumsy birds have to start flying early.