Collatz Proof Proposed: Hailstone Sequences End In 1 90
Posted
by
timothy
from the baseball-hailstones-also-a-tough-problem dept.
from the baseball-hailstones-also-a-tough-problem dept.
mikejuk writes "A proof [preprint PDF] has been proposed for the Collatz conjecture about hailstone sequences. A hailstone sequence starts from any positive integer n the next number in the sequence is n/2 if n is even and 3n+1 if n is odd. The conjecture is that this simple sequence always ends in one. Simple to state but very difficult to prove and it has taken more than 60 years to get close to a solution."
... and someone finds a fault in the proof. (Score:3)
Re: (Score:2, Interesting)
Ok, I'm not a mathematician but when I read:
"What's odd is that this assertion looks on the surface extremely simple. In particular, it is true for any 2l which is divisible by 4, and is true for any 2l I can reasonably imagine... but in the cathedral of mathematics experimental evidence is no evidence at all.
Disclaimer: I am a physics graduate student, not an established mathematician by any means. This is the best I can grok the paper."
I wonder... perhaps the paper's author also thought it was simple and
Re: (Score:2)
There's a difference between types of incompleteness in proofs. The first type is when details are left to the reader, which can occur for a variety of reasons: it's too tedious to completely write up; they needed the paper to be shorter; they didn't want to lose sight of their main goal by getting lost in details; etc. This type is pretty innocuous, though it can make papers denser than they otherwise need to be. The second type is when the author doesn't notice the source of incompleteness. A good classic
Re: (Score:2)
Was this supposed to be "the fundamental theorem of algebra"? But I agree with your points.
Re: (Score:2)
In any case, let's stop making stories about preprints proving/falsifying famous conjectures. After they've been reviewed by some experts, great, make a story--just not until then.
This isn't the Washington Post or the New York Times. I don't think Slashdot needs to have the same journalistic standards as publications "of record." I don't think there's any harm in reporting these kinds of stories. Personally, I think it's pretty cool to see these kinds of attempts, even if they turn out to be WAY off base. And it's not like this story had a sensational headline--all it said was that a proof was "proposed." Anyway, that's my two cents.
Re: (Score:2)
I suppose my issue is that pretty much every day someone somewhere comes up with a "proof" of a famous conjecture. Most of these are patently nuts, but some are (on the surface, at least) reasonably serious. It seems a bit strange to single out some of these for special attention. It's also almost always a letdown to read these types of stories. "Oh, cool, it was solved? I wonder how they did--oh wait, the first high rated comment says there's a big hole." In this headline I disliked the subtitle, "Hailston
Re: (Score:2)
I think if this conjecture was proved a decade or so ago, we would know of it's existence, and of its proving and the surprisingly hard road to its proof in classrooms; just like we see the problem of findings median in linear time. But today, as we speak, we are in fact commenting on a blog entry which refers to the proof and are discussing the type of flaw it may have; even though we do in the end yield the matter to ex
Re: (Score:3, Insightful)
That's not a fault in the strict sense, that's an omission. Besides, this IS a preprint - it's not been published, hasn't even been refereed or peer-reviewed yet, so it's not in the least bit surprising it's not perfect.
Remember Wiles' proof of FLT? That one went through quite a few iterations, and it took years until all the flaws were ironed out - big ones, in some cases, that required significant changes to the whole thing. But in the end, the proof stood.
Re: (Score:2)
Re: (Score:2)
Oh, the ignominy!
To have one's proof faulted is unfortunate; to have it faulted on the internet is simply mortifying.
Re: (Score:1)
Re: (Score:2)
One is an odd number, so you multiply it by three and add one for four, which is even, so you divide by two ... and it's turtles all the way down ...
Re: (Score:2)
One is an odd number, so you multiply it by three and add one for four, which is even, so you divide by two ... and it's turtles all the way down ...
The conjecture as stated in the summary, in addition to being poorly punctuated, is not "official". Or complete.
Re: (Score:2)
Except the actual sequence definition declares that the sequence ends at the first instance of one in the sequence.
Re: (Score:2)
You're right. One is the defined end of the sequence.
Re: (Score:2)
The actual hailstone sequence definition says that if a 1 is reached, the sequence ends. The article submitter omitted that, probably to troll slashdot.
Re: (Score:2)
The actual hailstone sequence definition says that if a 1 is reached, the sequence ends. The article submitter omitted that, probably to troll slashdot.
And it worked.
before too many question this (Score:4, Informative)
The sequence ends in 1 rather than 1, 4, 2, 1, 4, 2..... by definition. A hailstone sequence has one additional rule, which is that the first 1 is the last 1, and the sequence ends.
Re: (Score:2)
Those are actually orthogonal. For example, in your version the sequence is infinite, whereas with the additional rule it is probably bounded, and the length might even be amenable to calculation from the input.
So in other words... (Score:1)
...the conjecture could be more simply stated "Every hailstone sequence ends".
Or even more simply stated "Every hailstone sequence eventually contains a power of 2".
------RM
Easy to state, hard to read. (Score:4, Insightful)
A hailstone sequence starts from any positive integer n the next number in the sequence is n/2 if n is even and 3n+1 if n is odd.
It wouldn't have taken any more time to properly punctuate this "sentence" once -- for everyone -- than it takes everyone to punctuate it in their heads in order to make sense of it. I realize they just cut and pasted the bulleted points -- minus the bullets -- but c'mon, they didn't put those there just for decoration.
Re: (Score:2)
Isn't that what "editors" are for? (Score:1)
You shouldn't feel the need to apologize. The people who are presumably being paid to act in an editorial capacity for Slashdot are the individuals who should be taking the time to ensure submissions are readable. They're clearly willing and able to edit submissions, yet have rarely shown any inclination toward putting effort into anything beyond adding subjective comments or making questionable changes that result in submitters having to point out what the editors have done.
This has been a problem for as l
Easy to state, fun to program! (Score:5, Interesting)
I first heard about this conjecture many years ago (25?) and did what most geeks would do; I wrote a program to test all odd integer values and check that they did in fact reach 1.
The obvious approach is to remember the count for each value as you try them, then check any intermediate result against this table:
If found, just add that value to the current count and store the result.
This approach breaks down when you want to test starting values much larger than 2^32, because the space to store the table becomes larger than available memory.
One of the first optimizations is to realize that the result of taking 3n+1 starting from an odd (n) will always be even, so you can simply include the following n/2 (a shift) and increase the count, while getting rid of the multiplication by 3:
Odd(n):
n = 2m+1
3n+1 = 6m + 4
(3n+1)/2 = 3m + 2 = n + (n>>1) + 1
In asm this can be simplified to:
again: ;; Assume even, so divide by two and shift the bottom bit into carry ;; If the result of the shift was zero, we're done!
shr eax,1
jz done
inc edx ;; Increment number of steps ;; No carry means even input, so go back up
jnc again
inc edx ;; One extra increment ;; The starting value was odd, so now we need to multiply by 3 and add 2:
lea eax,[eax+eax*2+2]
jmp again
done:
A much more sophisticated step is to see that the next N operations are determined by the bottom N bits of the current value (as long as there are more than N bits available), basically allowing you to convert those N operations into a multiplication, an add and a shift right.
Next you realize that the intermediate values can very quickly overflow a 32-bit unsigned integer, and even using 64-bit values does not get you very far.
My approach back in those days was to use a variable number of 32-bit counters:
With a single counter I check for getting to 1 or overflowing so I need to use two counters.
With two (or more) counters I test for the top counter becoming zero, allowing me to reduce the number of counters, or for overflow forcing another incease.
All of this is of course much easier in asm than C,since you can use the ADD/ADC combination to perform arbitrary precision
Terje
Re: (Score:2)
ALL odd integer values? Where'd you buy your computer? I gotta get my next one from there!
Re: (Score:2)
Well, doing it for ALL values is what the mathematicians are trying to do, right?
I hope it was clear from my post that I meant "as many odd integers as possible"! :-)
Terje
Re: (Score:2)
It was obvious - and a nice write up. Thanks. That guy's a troll or a pedant.
Re: (Score:2)
And this is where you lose the thread. From the point of mathematic proof, "as many odd integers as possible" has *nothing* to do with "all odd integers" unless you stumble upon one that proves it false. Finding any finite number of odd integers for which it is true accomplishes nothing towards proving it true for all odd integers.
Re: (Score:2)
Re: (Score:2)
Never mind... http://hubrisarts.com/collatz.png [hubrisarts.com]
of the number's you searched
<Sigh>
Re: (Score:2)
Working with starting points less than 1e9 you can try 670617279 which leads to a sequence of 987 steps.
Starting with 319804831 gets you close to 64-bit overflow, with an intermediate value of 1414236446719942480.
Terje
Re: (Score:2)
That depends. Were you referring to the bullets or to the /. editors?
Applications? (Score:2)
I know mathematicians study these mathematics for reasons entirely unrelated to any practical applications of them. And I know that most of the value in proofs and understanding is totally independent of any applications, as the applications' utility are typically of relatively brief lifetime while the math is eternal.
But I'm not a mathematician, nor am I immortal. I'm an engineer. So I'm always interested in whether these proofs (or new insights) have actual immediate or reachable applications. These are c
Re: (Score:3)
No.
Re: (Score:2)
Well, it's a great example of a simple algorithm which may or may not halt. So it's useful for teaching algorithms, compiler design, and the halting problem (which is enormously useful).
But assuming it does always end in 1 ... no, there's no use for the proof. The proof (or it's techniques) might lead to more useful applications though.
Re: (Score:1)
Excuse me but aren't engineers supposed to be taking math and turning it into something useful. You sound more like a user - only using what is already there.
Re: (Score:1)
Well, that is pretty much what engineering is. You would be surprised on how little math is actually used in engineering.
Perhaps you are thinking about physicist that occationally have to do some major advances in math to be able to solve their problems. Notable examples are Newton and his integrals and Green and his theorem.
The math developed by pure mathematicians are seldom of use outside their field but still have an entertainment value for those in the field.
Re: (Score:2)
No, engineers apply known applications to problems they have to solve. Which is why we want newly known applications. And why those of us with problems for which there are no known applications for solutions are interested in the possibility of new applications when the bottleneck at the point of understanding has been passed.
Lots of us "take math" who aren't mathematicians. The vast majority of us, in fact.
Re: (Score:1)
Hey look buddy, I'm an Engineer, that means I solve problems. Not problems like 'What is beauty?', because that would fall within the purview of your conundrums of philosophy.
I solve practical problems.
For instance: How am I going to stop some big mean mother hubbard from tearing me a structurally superfluous new behind?
The answer: Use a gun. And if that don't work? Use more gun.
Re:Applications? (Score:4, Funny)
If that's your solution, you're a terrible engineer.
Re: (Score:2)
Agreed! EVERYONE knows that GOOD engineers use duct tape instead!
(You can solve ANYTHING with well-used duct tape!)
Re: (Score:2)
No immediate or even forseeable applications (and it has nothing to do with hailstones). But the guys who were working on number theory in the early 1900's (Hardy for one, who specifically refused to work on any maths that had real-world applications) didn't forsee the future uses in cryptography ...
Re:Applications? (Score:5, Insightful)
For example, consider the problem of the quintic formula. As everyone with a middle school education should know, there is a formula that gives the solution to any linear equation (ax+b = 0), and there is a formula that gives the solutions to any quadratic equation (ax^2 + bx + c = 0). Some more educated people will also know that there are formulas for cubic equations (ax^3 + bx^2 + cx + d = 0) and quartic equations (ax^4 + bx^3 + cx^2 + dx + e = 0). The obvious question is, "What about quintic equations (ax^5 + bx^4 + cx^3 + dx^2 + ex + f = 0)?"
The answer is a somewhat intellectually interesting, "No, there is no formula that gives the solution to all quintic equations (using only arithmetic and radicals)." There is no real-world application of that answer; we can get good enough approximations of the solutions to quintic equations by various numeric methods, which is perfectly fine for any problem that involves solving a quintic. However, the proof that there is no quintic formula involves fields of mathematics that are very much applicable to real-world problems: group theory and field theory are very important in cryptography and certain branches of physics. Additionally, those fields of study led to the research of more general abstract algebra, with still more real-world application.
So, no, there is no real-world use for the Collatz conjecture, at least none that I am aware of. In all likelihood, the proof of the Collatz conjecture will lead to some practical application, or a better understanding of certain real world problems.
Re: (Score:2)
Thanks for that explanation.
Offtopic: Is there any theory of solving hyperoperation [wikipedia.org] equations generally, or any theoretical work on why some types of hyperoperation equations are solvable by their respective formula but some aren't?
Re: (Score:2)
But I'm not a mathematician, nor am I immortal. I'm an engineer. So I'm always interested in whether these proofs (or new insights) have actual immediate or reachable applications. These are called "hailstone" sequences - is the math any use in weather or geology? Or any other?
I'm sure someone will call you a math philistine or something like that for your question, but I took it seriously. And as I read it, I thought "sure there must be. I bet a quick Google search would turn up some." But the only practical use I turned up was in the creation of graphs, charts and illustrations of the sequences themselves.
Some are pretty.
Re: (Score:2)
Sure. Its main application is an insomnia treatment for mathematicians.
Re: (Score:2)
Re: (Score:1)
Re: (Score:2)
Re: (Score:2)
These simple proofs are like Debian - by itself it's unconfigured so it won't play proprietary stuff. But they can be combined to form other results.
As a superfast dirty guess, there's a computing application here somewhere. The conjecture itself deals with binary division, and the +1 part of the other rule has something to do with a power of 2 result being one more than an odd number next to it.
Fast guesses for apps have to do with lowbyte-highbyte number encoding, etc as well as a bunch of other stuff. (F
Re: (Score:2)
Hi AC.
The reasons why the theorem may matter is that the notion of a "reasonable" number may not hold up to the quantities of throughput that happen at chip speeds. Think of stack carry-through register operations. On a 64 core chip when all that integrates it may not hold at 10^16 or something with a race condition threatened.
Re: (Score:3)
Such sequences are called hailstone sequences because the values typically rise and fall, somewhat analogously to a hailstone inside a cloud. While a hailstone eventually becomes so heavy that it falls to ground, every starting positive integer ever tested has produced a hailstone sequence that eventually drops down to the number 1 and then "bounces" into the small loop 4, 2, 1, ....
It lists as one of its sources this book [amazon.com] on the etymology of math terms in English. It looks interesting. Maybe I'll get a copy myself....
Re: (Score:2)
Thanks for the explanation of the name.
I had a use for a reverse "etymological mathematics dictionary" just this past week. I was trying to collect from people working on projects the "base projects" in the dependency network of all their projects. I was looking for the complementary word to "dependent" in the dependencies. After a while I discovered "pendent [wikipedia.org]", which is the thing on which a dependency depends, from geometry.
But I don't see myself ever again buying a printed dictionary of any subject, except
Re: (Score:2)
If anything the concepts necessary to reason about the problem are probably useful, even if the problem itself is not. Depending on the way the numbers spread in the algorithm, it may have applications for cryptography, or hashes and digests. Algorithms that either generate numbers with greater range from a simpler number, or calculate a simpler number from one of a greater range.
It is undoubtedly also possible to make datastructures and algorithms, that uses the sequence, though there is no guarantee it
Re: (Score:1)
The halting problem is unsolvable, but we have to solve it anyway, as well as we can. And that's just one possible application. The fact is, you have to have a paintbrush before you can paint, and you have to develop the proof before you can say what the proof technique can be used for.
If mathematicians had slowed down every time some "practically minded p
Re: (Score:2)
Nobody asked mathematicians to slow down. And what's "extremely odd" is that you tried ranking what's more important with an obnoxious question after I explained why I'm interested in an application if it exists. What the hell is wrong with wanting an application in addition to humanity taking 1 step forward?
If you can't understand that from what I posted, I expect you have absolutely nothing to offer in helping solve the hailstone sequence. So just shut up. You're holding humanity back with your infinitesi
Re: (Score:2)
By definition, which the article submitter conveniently omitted.
Re: (Score:2)
Lets rephrase: It will always converge to the eternal sequence 4, 2, 1, 4, 2, 1, 4, 2, 1...
Debunked already (Score:4, Interesting)
Re: (Score:2)
Re: (Score:2)
If you (metaphorically) go on the podium with your fly open and your dick hanging out, you deserve to be laughed off the stage.
I am waaay behind in my mathematics (since university), but even to me the paper looked rather fishy. If a problem has not been solved for decades, a prudent researcher would not push a paper like this out. And he surely wouldnt give interviews in the press talking how good he is and how he only recently started working on the problem...
Re: (Score:3)
Mathematics deals in certainties. An integer is odd (or prime, or divisble, or constant, or whatever), or it's not, by a very strict definition.
The problem stems from *proving* that. The mathematician (i.e. someone who studied mathematics at, say, degree level or higher) that can actually write a proof is surprisingly rare. The one that can write a perfect, undeniable, accepted, doubt-free proof in a single hit is would be seen as an absolute genius better than any other mathematician that's ever lived -
Collatz Conjecture Explained... (Score:3)
2^x (Score:1)
Re: (Score:2)
The problem really becomes proving that for any {n: (n mod 4) = 2,3}, the sequence will eventually yield {n: (n mod 4) = 1}.
Can I try? (Score:1)
I'm not a math major, and I have very little experience with any proof. I've never written one. But I would first think this is a 3 part problem. One of n=even, n=odd and n=2^x. Proving all will become 2^x seems to be the goal.
Any even integer n divided by 2 is an integer half the value
Any odd integer n multiplied by 3 is an odd integer.
Any odd integer n plus one is an even integer
Through induction, any power of two in this sequence will end in 1. That is to say if n_0 is 2^x, then the sequence will always
Last step is flawed (Score:1)
An odd n + 1 will always be even, but it isn't obvious that this will eventually lead to a power of 2.
Intriguing Observation (Score:2)
Looking at the partial Hailstone tree [hubrisarts.com] as a network, it's interesting that the tree can fork only at every other node, even for nodes that aren't on the "power of 2" limb. There's no case in which forks occur in neighboring nodes.
That would be a useful property to have in practical situations such as the generation of clock trees in digital integrated circuits. It would be interesting to see if similar rules could be applied to CAD systems.