It states the following: take any natural number, n. if n is even, divide it by 2 (n/2). if n is odd, multiply it by 3 and add 1 (3n + 1). Repeating this process over and over will eventually get you 1.
(Search it on wikipedia if you don't know it)
So, doing this for, say, n = 9, gives this:
9 -> 28 -> 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1 -> 4 -> 2 -> 1
Now, initially this seems pretty interesting, and indeed it is!
Do it for a few more numbers (larger ones perhaps. although it's worth noting that a small number such as 9 got all the way up to 52!) and you'll see what i mean. It ALWAYS goes to 1, eventually!
This is actually an unsolved problem in pure mathematics, which I was surprised to find out. (Paul Erdos actually offered a $500 prize for the solution).
Like i was saying, it seems really complicated and important at first, but i'm not really sure it is.
----------------------------------------------------------------------------------------------------
Here's my take on it.
(Also, keep in mind that I'm not a degreed mathematician or anything like that. Tthis is just me thinking)
Again, the conjecture states that, for any natural number n, do the following: if n is even, divide it by 2; if n is odd, multiply it by 3 and add 1. Repeating this process over and over will eventually get you 1.
You'll notice pretty quickly (it really only takes two or three runs of this algorithm to do so) that if we reach a power of 2, we're done pretty quickly, because we just keep dividing down by 2 until we hit 1.
So the question really is this (or can be stated as):
how long before we hit a power of 2?
It seems reasonable enough to me to think that given some arbitrary algorithm, you will eventually reach an equally arbitrary goal (assuming they're not contradictory, such as starting with an odd number and adding 2 until you reach an even number).
since 3n + 1 can reach odd numbers and even numbers, there is no reason it shouldn't reach a power of 2 at some point. that is to say, there's no reason that multiplying by 3 and adding 1 shouldn't eventually reach a power of 2 (ie they're not contradictory statements. For example, multiplying instead by 2 and adding 1, and reaching a power of 2 would obviously be contradictory statements). it would seem that the only thing that would need to be proved - if anything - is why that is true.
since 3n + 1 can reach odd numbers and even numbers, there is no reason it shouldn't reach a power of 2 at some point. that is to say, there's no reason that multiplying by 3 and adding 1 shouldn't eventually reach a power of 2 (ie they're not contradictory statements. For example, multiplying instead by 2 and adding 1, and reaching a power of 2 would obviously be contradictory statements). it would seem that the only thing that would need to be proved - if anything - is why that is true.
Consider the following:
Given any natural number:
If the number is not prime, divide it by its smallest prime factor;
If the number is prime, multiply it 2 and add 1, then go eat a cheeseburger.
(If, by chance, you get to 1, consider it prime. I say this just so this process is defined for every natural number.)
(If, by chance, you get to 1, consider it prime. I say this just so this process is defined for every natural number.)
It is my contention that any number chosen will, after repeating this process, eventually converge at some small number (such as the 1 for Collatz); it turns out to be 3 for this problem (and indeed it does reach 3 every time). Also, you will soon become very fat.
(You can also see that it does here; and feel free to copy or rewrite this code and try different numbers for yourself):
You can also see that once it reaches 3, it will cycle back up to 7, and reach 3 again. This is much like the Collatz problem, in which it cycles 4-2-1-4-2-1-4-2-1, but never really stopping.
So does this question deserve as much, if any, attention as the collatz problem? Keep in mind, I just pulled this thing out of my rear-end.
Well, it actually seems harder to analyze than the collatz problem! As far as i know, it's much harder to put into an algorithmic form similar to the one for the collatz problem
(which is:
f(n) = n/2 (if n = 0 [mod 2]), 3n+1 (if n = 1 [mod 2])
)
The answer to me seems to be no, we shouldn't really spend much time analyzing this 'truly mysterious phenomenon'.
While, yes, it is very interesting (and fun to play with!), i don't see what the big deal is!
The Collatz problem says pretty much the same thing as 'if we take a number, and do some arithmetic to it, how long does it take until we get to a power of 2?' Actually, not even that, it only asks if we get to a power of 2, not even how long, or how many iterations. Kind of boring, no?
Actually, the 3n+1 just turns an even number into an odd number, and an odd number into an even number! and the n/2 will turn n odd or even. also note that this way, every odd number becomes even.
so we go... iterating...
odd.. even... even... even... odd... even... odd... even... even... odd... POWER OF 2!! YAY!! done!
All in all, this seems more like a statistics problem to me - seeing how long it takes to get a power of 2. Maybe it is interesting in analyzing some properties of the natural numbers; like the density of powers of 2, or even numbers or something like that. But again, don't we already know that? We know the density of powers of 2 because we have an algorithm to get powers of 2 (hint: start with 2 (or 1), multiply by 2). It's not like the density of primes, which we don't know (although we can approximate the number of primes with the prime-counting-function, which approaches ln(n) minus a small constant for sufficiently large n).
Also, notice that it doesn't matter how large these numbers get. You could iterate a thousand times and get a number in the trillions! but still, once you hit a power of 2, you come tumbling down to 1 very quickly. Granted that the powers of 2 are very sparse in the trillions, there is no way that you are going to stay up in the trillions for long, seeing as you are bound to encounter a number which is divisible by 4 or 16 or 256 soon, and come tumbling way down with the n/2 - try it.
In conclusion, it seems to be an arbitrary problem to me! Given an infinite amount of time and iterations, will this algorithm make power of 2, if you keep giving the algorithm even numbers?
But what do you think?
Is this a trivial problem?
(Also keep in mind that Paul Erdos thought this was a very difficult and complex problem. Ohhhh Paul Erdos! Are you intimidated? Can you feel your opinion changing?)
