Gerhard Opfer has posted a paper that claims to resolve the famous Collatz conjecture.
Start with a positive number n and repeatedly apply these simple rules:
- If n = 1, stop.
- If n is even, divide n by 2.
- If n is odd, multiply n by 3 and add 1.
In 1937, Lothar Collatz asked whether this procedure always stops for every positive starting value of n. If Gerhard Opfer is correct, we can finally say that indeed it always stops.
Update: It appears there’s a flaw in the proof. See discussion here. Perhaps the gap can be filled in, or perhaps an idea in the paper can be of use somewhere else.
Related post: Easy to guess, hard to prove
Wow!
Have you tried to read the paper yet? It looks like it’s a little bit above my head. But nowadays I can ask around for help understanding something like this.
I’m sad in a way. It was pretty cool to have a problem kids like playing around with and to know it had no solution.
My home town and my old university
))
Thank you for the info!
Come now, “Collatz 3n + 1 conjecture solved”? A bit sensationalist, don’t you think? =) The paper has not even undergone peer review yet. That said, however, it certainly does look like a serious attempt — by a student of Lothar Collatz, no less! Let’s hope that it’s correct (and that I can understand it)!
First error I caught was “The Collatz conjecture states, that all Collatz sequences terminate after finitely many steps with the cycle 4, 2, 1, . . .”
Tut; n=2.
I haven’t read that kind of math for 5+ years so like Sue I can’t get through the paper… but it seems that it’s reasonable to expect it to stop if, in the long run, the 3n+1 operation mostly gives you numbers that can be divided twice in a row. Since you’re dividing by 4 then, it goes down faster than it goes up. In fact if that happens just over 75% of the time I think it would eventually end.
Any odd number can be expressed at 2x+1, so if you multiply that by 3 and add 1 you end up with 6x + 4. The 4 can be divided by 4, so you need to know if the 6x can be divided by 4 most of the time – in other words if 3x is even. The series of odd numbers alternates between 2*+1 and 2* + 1 so half the x values will be even.
That doesn’t seem sufficient, so I think you would need to either prove that it is or show that doing 3n+1 a few times tends to lead to more even numbers (maybe you do it 10 times and then you can divide by 2 20 times, or you do it 100 times than divide by 2 200 times). If it does work it’s probably by a very small margin.
Alternately you could take the sequence of numbers that go straight to 1 because they’re the product of even numbers only, and then show that multiplying by 3n+1 enough times will eventually get you to one of those numbers. Then the question is how many times you need to do 3n+1 to hit a product of evens.
In another 70 years I think I’ll have this
@Richard “In fact if that happens just over 75% of the time I think it would eventually end.”
I don’t think your reasoning is correct (well, it depends what you mean by “end”). I agree that the sequence tends to decrease, but you can reach a cycle. Actually one can generalize the sequences to rational numbers, and even though you can do the same reasoning, there are an infinite number of cycles.
About 20 years ago, I tried a probabilistic approach: find the probability of getting a cycle of length c (with the operations (3n+1)/2 for n odd and n/2 for n even), and got a relation with the partial quotients and convergents of the continued fraction of log(3)/log(2). The goal was not to be rigorous, but to try to intuitively explain what we can observe. My memory is a bit weak, because I thought I obtained all the cycles (with any integer, i.e. possibly negative) with convergents, but after looking at http://en.wikipedia.org/wiki/Collatz_conjecture I can see a cycle with negative integers that doesn’t correspond to a convergent.
IIRC, I obtained the same formula as the one on Wikipedia (with different notation) about cycles of length c with b odd numbers: (3^{b-1} 2^{k_0} + … + 3^0 2^{k_{b-1}}) / (2^c – 3^b). What I was saying that |2^c – 3^b| should be “small” for some magnitude of b and c to increase the chance of getting an integer, hence the relation with the continued fraction of log(3)/log(2). Something I had noted is that the partial quotients of even position (i.e. the last partial quotient for the cases where 2^c – 3^b > 0) for positions 4 to 10 are larger than those of odd position, which is a bit bad luck…
Actually, I now think this is much more complex and convergents don’t necessarily matter as they are too scarce. A naive probability is binomial(c,b) / (c * |2^c – 3^b|), the sign of the integers of the sequence being the sign of 2^c – 3^b. But I this is not sufficient, because the sum from b = 0 to b=c-1 doesn’t decrease quickly enough.
@Scott: that’s not an error! The sequence starting with 2 is 2, 1, 4, 2, 1, 4, 2, 1, … as you can easily check, so it does fall into that cycle.
I’m not so sure that the conjecture is resolved after all, see http://math.stackexchange.com/questions/43051/collatz-finally-solved/43082#43082
The author of the paper, Prof. Opfer, writes:
“Author’s note:
The reasoning on p. 11, that The set of all vertices (2n; l) in all levels will
contain all even numbers 2n 6 exactly once.” has turned out to be incomplete.
Thus, the statement that the Collatz conjecture is true” has to be withdrawn,
at least temporarily.
June 17, 2011″
source: http://preprint.math.uni-hamburg.de/public/papers/hbam/hbam2011-09.pdf
is this problem solved??
No, there was a flaw in the proof.
You do not have to multiply by 3. N+ 1 gives the same result
So why don’t we just prove it and be done with it? Pick a number, any number. If it’s even and a power of 2, then repeated division by 2 (that pesky n/2 if n is even statement ) will converge to 1. If it’s odd, then 3n+1 will make it even. As my old math instructors would say “It’s intuitively obvious to even the most casual observer” , but you can prove it if you must. So ok, dividing that result by 2 will either end with another odd number eventually, or it will go to 1. When will it go to 1? When it’s a power of 2. That means we should find all of the numbers that make 3n+1 a power or 2. A little fiddling in Excel and you find that a starting set is (1,5,21,341, 1365, …) . You don’t really need 1 since it is, after all the solution to the whole mess, but I included it so you can see the really cool pattern that evolves.
Thus 3*1+1 = 4 =2**2, 3*5+1 = 16, 3*21 +1 = 64 = 2**6, 3*341 + 1 = 1024 = 2**10 just to show a couple of examples. By the way, * means “times ” or multiplied by, ** means “exponent” or “to the power of” .
The really cool pattern (as promised) is this:
1 = 2**0 + 0, 5 = 2**2 + 1, 21 = 2**4 +5, 85 = 2**6+21, 341 = 2**8 + 85, 1365 = 2**10 + 341 and so on. As you can see (by looking at the exponents), for any even number (0, 2, 4, …) we can construct an odd number which, when plugged in to 3n+1, is a power of 2 and thus converges to 1. With the formula 3n+1 we can construct an even number from any odd number (1,3,5,7,9…). Since these 2 sets combined form the natural numbers, I say it’s QED.