Slashdot Mirror
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."
A redditor to be more precise.
Never trust a spiritual leader who cannot dance -- Mr. Miyagi
I propose for some numbers it ends in a repeating loop of 2, 1, 4, 2, 1, 4
The sequence would end in 4.
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.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
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.
I am not a crackpot.
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 called "hailstone" sequences - is the math any use in weather or geology? Or any other?
--
make install -not war
if it reaches 1 then the next would be 4 , so how could it possibly end in 1 ?
Did a six year old write that? Is it really that hard to write a coherent sentence?
Just Sayin'
Rebuttal of the "proof" here: http://mathlesstraveled.com/2011/06/04/the-collatz-conjecture-is-safe-for-now/
Every end has half a stick.
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
"almost all programming can be viewed as an exercise in caching"
Are these the hailstones that are the size of flat cylindrical objects (like coins) rather than the size of spherical objects (peas, golf balls' softballs ?
Obligatory: http://xkcd.com/710/
...by xkcd.
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 long as I can remember, and while it's excusable from a volunteer-run operation, a paying for-profit operation should be willing to invest in someone willing to do basic proofreading and fact-checking while approving reader-submitted links, favoured weblogger glurge, and Slashvertisements.
Then again, I don't think much of the hypothesis that financial profit is an obligatory motivator for competence, so I'm not surprised that garbled sentences go right by the staff; hiring someone to check the spelling and grammar would cut into profits, after all, and as long as people keep paying for crap, what motivation is there to change?
Someday, you're going to die. Get over it.
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 could be wrong.
"For I desired mercy, and not sacrifice" -- God
...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
Well, it seems you will always ultimately land on a number which is a power of 2. At that point, you'll be doing nothing but dividing by 2. You'll only be n steps from 1, with no escape.
The conclusion of the conjecture seems obvious. Showing that the sequence *must* at some point arrive at a power of 2, I'm sure, is quite hard.
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 be even and always end in 1. 2/2 =1, 8/2/2/2=1.
As an infinite sequence, n will always become odd for any even n_0, not a power of 2.
Since odd n always have 1 added, they will eventually become a power of 2.
An odd n + 1 will always be even, but it isn't obvious that this will eventually lead to a power of 2.
Looking at the partial Hailstone tree 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.