Collatz Proof Proposed: Hailstone Sequences End In 1

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."

Comments

... and someone finds a fault in the proof.

[Musically_ut]

A redditor to be more precise.

Re:... and someone finds a fault in the proof.

[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 obvious and possibly even proved elsewhere?

Anyway. Isn't refuting the proof, just claiming it is incomplete.
And from what I recall, mathematicians often submit proofs others consider "incomplete" since they kinda assume those things are obvious.

Re:... and someone finds a fault in the proof.

[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:... and someone finds a fault in the proof.

[barlevg]

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.

before too many question this

[Surt]

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.

Easy to state, hard to read.

[Rob the Bold]

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:Applications?

[nedlohs]

No.

Re:Applications?

[betterunixthanunix]

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.

Debunked already

[CSMoran]

Rebuttal of the "proof" here: http://mathlesstraveled.com/2011/06/04/the-collatz-conjecture-is-safe-for-now/

Re:Debunked already

[ledow]

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 - more "clever" than Einstein, Hawking, etc. Because we're human and we always miss *something* in any proof ever offered for even the simplest of things.

Most proofs are like security programs on computers - they'll have holes with virtually certainty, and it's only accepted as "proof" when the holes have been found, poked at for 20+ years and every holes patched, countered and fixed. That's the process called "peer review". Look at any mathematical-based security process in computer science and you see the same pattern - cryptography, clever exploits, chroot-breaking etc. It takes decades to find MOST of the holes and an infinite amount of time to find all of them.

Any "proof" that comes from someone who hasn't been poking holes in others papers, or endlessly patching their proof for years based on the input of humongously talented third-parties is, history shows, 100% bullshit. Just read the story behind the solution to Fermat's Last Theorem, for example.

The problem is that the mathematical equivalent of "free energy" fanatics, etc., are people who claim to have proven something and yet have zero experience of providing actual proofs that are accepted by the mathematical community. It's elitest, sure, but it helps to filter out the nutters if you just ignore EVERYTHING posted on arxiv.org until it appears in a reputable, third-party-reviewed journal and has had ten rebuttals, all of which have been neatly countered using fabulously complex arguments.

You can now "prove" the four-colour theorem in an afternoon with a home computer and some mathematical knowledge. But it took *decades* to convince the mathematical community that a proof which relies almost entirely on the output of a computer to perform the grunt work was acceptable. And it was still in doubt from 1976 up until around 2005 as to whether it was actually a "proof" or not.

If someone claims to have solved a long-standing mathematical problem, with zero previous experience, treat them how you'd treat someone who claims that they can double the output of your car engine without using any extra energy source if you let them take the car apart. Yes, technically and historically, such things have been possible by certain marvellous innovations in the field. But would you really let him tinker with your car on the basis of that without knowledge of that person himself?

P=NP is a field that attracts people just like the "free/perpetual energy/motion" nutters, for instance. There's been at least three or four slashdot stories of "proofs" of that since the beginning of the year. None of them came to anything, all of them were firmly rebutted, and none of the authors were heard of again. It's not a general hostility in mathematics - just towards the time-wasters and nutters that think A-level maths qualifies them to provide a definitive proof of something new in an afternoon.

Re:Applications?

[FrootLoops]

"Hailstone" doesn't seem to have anything whatsoever to do with actual weather or geology. MathWorld's 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 on the etymology of math terms in English. It looks interesting. Maybe I'll get a copy myself....

Easy to state, fun to program!

[Terje Mathisen]

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:Applications?

[Doc Ruby]

If that's your solution, you're a terrible engineer.

Collatz Conjecture Explained...

[dlgeek]

...by xkcd.