Catch up on stories from the past week (and beyond) at the Slashdot story archive

typodupeerror

## Collatz Proof Proposed: Hailstone Sequences End In 190

Posted by timothy
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."
This discussion has been archived. No new comments can be posted.

## Collatz Proof Proposed: Hailstone Sequences End In 1

• #### ... and someone finds a fault in the proof. (Score:3)

<musically DOT ut AT gmail DOT com> on Sunday June 05, 2011 @10:15AM (#36342680) Homepage Journal
A redditor [reddit.com] to be more precise.
• #### Re: (Score:2, Interesting)

by Anonymous Coward

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)

Gauss' first proof of the fundamental theorem of arithmetic

• #### 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)

Here, I think, one can comment on how this business of science is changing markedly.

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)

by Anonymous Coward

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)

I don't think it's remotely fair to compare this paper to the FLT proof. For one thing, the content of this one is around 11 pages (the PDF includes many pages of tables at the end) while Wiles' final proof is over 100 pages. This is much more "elementary", as well. I don't remember the source, but I remember hearing that at the time it was made the number of people qualified to comment on Wiles' proof could fit in a small room, which is certainly not true of this proof. Wiles invented a graduate course whe
• #### Re: (Score:2)

Oh, the ignominy!

To have one's proof faulted is unfortunate; to have it faulted on the internet is simply mortifying.

• #### before too many question this (Score:4, Informative)

on Sunday June 05, 2011 @10:56AM (#36342904) Homepage Journal

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.

• #### 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)

on Sunday June 05, 2011 @10:57AM (#36342910)

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.

Sorry :-(
• #### 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)

on Sunday June 05, 2011 @12:50PM (#36343688)

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:
shr eax,1 ;; Assume even, so divide by two and shift the bottom bit into carry
jz done ;; If the result of the shift was zero, we're done!

inc edx ;; Increment number of steps
jnc again ;; No carry means even input, so go back up

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)

I wrote a program to test all odd integer values

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)

Out of curiosity, of the number's you searched, what number had the longest sequence?
• #### 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)

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

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

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)

by Anonymous Coward

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

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)

by Anonymous Coward

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)

on Sunday June 05, 2011 @01:52PM (#36344094) Homepage Journal

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)

on Sunday June 05, 2011 @11:17AM (#36343026)
The reason mathematicians are interested in the 3n+1 problem is that we do not have a very good understanding of the process -- it is a fairly simple process to describe, but it is not so easy to explain why it would always fall into the same cycle (1,4,2,1,4,2,1,4,2). A lot of problems in number theory are like this; Fermat's last theorem was similarly easy to state but very difficult to understand and prove. The real-life application of these problems is often more related to the various methods required to solve them than the problem itself.

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)

I get kept up by interesting problems. Maybe you meant "insomnia causer for mathematicians".
• #### Re: (Score:1)

The proof is treatment though, because it allows you to finally rest.
• #### Re: (Score:2)

Oh, I think I misconstrued the person I was replying to. They were probably referring to applications of this purported proof (which I don't believe is correct) while I was referring to mathematicians' work on the Collatz conjecture, or the conjecture itself and numerous related topics and generalizations.
• #### 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:3)

"Hailstone" doesn't seem to have anything whatsoever to do with actual weather or geology. MathWorld's [wolfram.com] take on it:

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)

Understanding if a sequence ends is very important. You don't like it when your word processor crashes (ends) when you try to save a file do you?

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

• #### Debunked already (Score:4, Interesting)

on Sunday June 05, 2011 @12:14PM (#36343416) Journal
Rebuttal of the "proof" here: http://mathlesstraveled.com/2011/06/04/the-collatz-conjecture-is-safe-for-now/ [mathlesstraveled.com]
• #### Re: (Score:2)

It seems that the field of mathematics is cut throat. Just the tone alone from that blog post would make me reconsider even trying to break into mathematics as a researcher. I thought only computer geeks are like that on USENET.
• #### 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)

on Sunday June 05, 2011 @02:37PM (#36344350)
...by xkcd [xkcd.com].
• #### 2^x (Score:1)

This sequence will always collapse to 1 when we reach any number that is represented by 2^x. That is to say that when we reach a number whose prime factors are only twos. The entire purpose of 3n+1 is to manipulate the previous number to try to get a number that can be represented by 2^x. Dividing all even numbers by two is just a simple way to test for 2^x. Given enough iterations we will eventually reach a number that can be represented by 2^x. Of course this is only what I concluded years ago and I
• #### Re: (Score:2)

...which is itself inevitable once (n mod 4) = 1. (Stupid slashdot filters out &cong; symbol)

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.

#### Related LinksTop of the: day, week, month.

"Free markets select for winning solutions." -- Eric S. Raymond

Working...