Thursday, June 25, 2009

101 Interesting Things, part eighteen: Hailstone Sequences

The field of mathematics is chock-full of interesting things, but most of these are only of interest to physicists and mathematicians as they involve concepts or methods well beyond the education of most. Some examples of these include the Riemann hypothesis, which involves the distribution of prime numbers in a way that almost requires higher education to even understand, and is really only interesting to cryptographers; or Goldbach's conjecture, unsolved since the 1700s and seemingly demanding of a simple solution, which states merely that every even number may be expressed as the sum of two prime numbers. Sure, it's simple - but you try proving it! Any aspiring mathematicians who want to have their dreams crushed are welcome to peruse the CMI Millennium Prize problems - open problems in mathematics which have collectively stymied the experts for probably a million man-years.

At the other end of the spectrum are problems within every layman's grasp, such as the Monty Hall problem (which shall get its own post in short order, now that I've thought of it). The one I want to talk about today is the problem of hailstone sequences. As the linked page explains, these are called "hailstone sequences" because the sequences generated by the following algorithm go up and down like a hailstone in a cloud. Take any number - for the sake of the cited article, we'll call it n - and follow these steps:
1a. If n is even, divide it by two. n/2=n'
1b. If n is odd, multiply it by three and add one. 3n+1=n'
2. Repeat step 1 with n'. Lather, rinse, repeat ad infinitum.
OK, now eventually, your sequence is going to end up repeating at 4, 2, 1, 4, 2, 1... Go ahead, try it. I've got time. There's even a little applet on the page linked above.

All right, satisfied? Now I've got two propositions that I'm just going to lay out there:
1. Every number put through these steps will end up repeating at 4, 2, 1, 4, 2, 1...
2. There is at least one number that does not end up at 4, 2, 1, 4, 2, 1...
Nobody - not one single person - has been able to prove either of these contradictory propositions. But one of them must be true! The common-sense approach is that any time you end up at a power of two (2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, etc.), it's Game Over, and you're eventually going to hit on a power of two, so there. This is also true of powers of two multiplied by any power of ten, since it will end up at a power of ten which all fall into the same old trap (though for slightly more subtle reasons). In fact, you could conceivably show that all non-prime numbers end up at 4, 2, 1, etc., though I'm a bit fuzzy on the how of the matter. You'd probably want to start by showing that all multiples of three will do it, then all multiples of five, then six, seven, eight, nine, etc. (1, 2, and 4 are skipped for what should be obvious reasons), until you identified a general solution. But that still leaves the problem of primes, and prime numbers are ipso facto numbers that don't fit any pattern - the sieve of Eratosthenes (which eliminates all non-prime or "composite" numbers until the square of the next prime) demonstrates this by eliminating all numbers generated by regular patterns, leaving you what's left: the primes. Because of this, a general solution to prove proposition 1 (above) may well be impossible.

Frustratingly, it may be an insoluble problem - proposition 1 may be true but unprovable, meaning that proposition 2 can never be proven and the question shall always remain open. This possibility could itself be proven by showing that proposition 1 can never be verified in a way that neither confirms nor refutes proposition 2. Whether this can even be done is also an open question, though.

So scratch your head in wonder at this interesting emergent property of numbers, and then have a beer. I'm sure going to!


Zach L said...

look, if they can "solve" the map coloring problem with big honking computers just trying out every dang old permutation, why can't they do it with hailstone sequences?

D said...

Because there are infinite prime numbers and every single one of them must be evaluated, unless a general solution is found. A productive approach may be to see if there's a way to predict how many "steps" a particular number will take before collapsing to 4, 2, 1, 4, 2, 1... If such a formula were discovered, that could actually solve the problem handily by proving premise 1, so long as no integer has an undefined (read: infinite) number of steps before collapsing.

Dammit, now I want to try that. I need even more time. Zach, quick: make every day 36 hours long, but in a way that prevents people from demanding more work out of each day!

Zach L said...

I wish I could.

unfortunately, people are assholes. If we had 36 hour days, the daily workload would increase to compensate.

stupid jerky people.