*** MATHEMATICAL RECREATION DEPARTMENT *** HAILSTONE PATH in HP 48 Machine Language by Joseph K. Horn How would you like to win several thousand dollars (!) and win eternal mathematical fame on a par with that of Pierre de Fermat? All you have to do is prove (or disprove) "Ulam's Conjecture", also known as the 3x+1 Problem, and the Collatz Sequence, and the Hailstone Path, and Wondrous Numbers, and the Syracuse Algorithm, and many more monikers too maudlin to mention. Every significant mathematician for the past 40 years has played with this problem. Several are so frustrated with it that they're offering large cash rewards for its solution. (I've been toying with it for over 20 years!) The analogy is like this. A hailstone is born at some elevation in a storm cloud. Updrafts keep it aloft as it accumulates more and more ice, growing as it rises and falls through the sky. Soon it gets so heavy that only violent updrafts (as are found in storm clouds) can keep it aloft, and still the hailstone's path is unpredictable. But eventually (obviously) it will have grown so large and heavy that it begins an unimpeded plummet towards the ground. End of hailstone path. It is plain to any reasonable person that the actual path will be unpredicatably chaotic, but the end of the path will always be the same. Some wicked soul invented a mathematical equivalent. It is very easy to state and play with, but difficult (!) to prove. It goes like this: Pick any integer > 1. Now DO this: IF it's odd, THEN multiply it by 3 and add 1, ELSE divide it by 2. REPEAT this process over and over, UNTIL you get to 1. Sometimes the number will rise, and sometimes it will fall (like a hailstone caught in updrafts in a storm). But sooner or later, everything seems to get down to 1 (the ground). The conjecture is that ALL integers > 1 will eventually reach 1 by this process. For example, let's start with 3: 3 is ODD, so multiply by 3 and add 1, which gives 10; 10 is EVEN, so divide by 2, which gives 5; 5 is ODD, so multiply by 3 and add 1, which gives 16; 16 is EVEN, so divide by 2, which gives 8; 8 is EVEN, so divide by 2, which gives 4; 4 is EVEN, so divide by 2, which gives 2; 2 is EVEN, so divide by 2, which gives 1; 1 is GROUND LEVEL, so STOP! Thus the "hailstone" (3) eventually reaches "ground" after rising and falling through the numerical sky (getting all the way up to 16!). So Ulam's Conjecture works for 3. Notice that 3 travels through SEVEN different numbers before reaching 1. I define HAILPATH(x) to be the "hailstone path distance" of x, so HAILPATH(3) is 7. I like to think of the hailstone 3 as getting larger and larger with "ice" until it gets so heavy that even the mathematical updrafts cannot keep it from falling to the ground. Try 7. It gets all the way up to 52 before finally starting to come down, and has a HAILPATH of 16. But, wait a second! Isn't it possible for a number to just keep going up and up, and never come down? Or a number might get caught in an infinite loop. Why not? Number, after all, aren't REALLY hailstones... If anybody can find a number which doesn't reach 1, they will win many bucks and instant fame. This is obviously a task that the HP 48 can easily tackle! Here's a simple HP 48 program (written in vanilla RPL, not optimized) for determining the hailpath of x, which I'll name 'ULAM' after the late Stanislaw Ulam, whose love of this conjecture was exceeded only by his bafflement with it: ULAM %%HP:T(3); \<< 0 SWAP @ Put an empty loop counter in level 2. WHILE DUP 1 > @ Exit as soon as it gets to 1. REPEAT IF DUP 2 MOD @ is it odd? THEN 3 * 1 + @ yes? then multiply by 3 and add 1; ELSE 2 / @ no? then divide by 2. END SWAP 1 + SWAP @ Increment the loop counter. END DROP @ Lose the "1" and stop. \>> This program takes any integer > 1 and returns the length of its hailstone path to 1. If X gives an answer, then you've verified Ulam's Conjecture for that X. This program is a lot faster than doing it by hand! Here are some random X's, hailpaths, and ULAM execution times: X: HailPath: ULAM Execution Time: 3 7 .2 sec 7 16 .5 sec 25 23 .7 sec 27 111 3.4 sec 703 170 5.3 sec 2463 208 6.5 sec 26623 307 9.6 sec 63728127 949 31.3 sec 2610744987 1050 34.6 sec 4890328815 -- fails due to roundoff errors! Although that's faster than doing it by hand, wouldn't it be nice to have a HAILPATH function that works as fast as, say, the square root function? Aha, glad you asked. On this disk is a binary file called HAILPATH that is an optimized machine language version of the program above. Here are sample times (compare!): X: HailPath: HAILPATH Execution Time: 3 7 .024 sec 7 16 .024 sec 25 23 .025 sec 27 111 .029 sec 703 170 .032 sec 2463 208 .034 sec 26623 307 .039 sec 63728127 949 .071 sec 2610744987 1050 .076 sec 4890328815 1131 .080 sec As you can see, machine code is so much faster than user code that it boggles the mind. That 1050 entry is almost 500 times faster! Instead of over half a minute, it takes less than a tenth of a second! And it's more accurate; its internal "hailstone" size can be up to 19 digits long. Here's the machine language version in hex form, for those of you who use Bill Wickes' ->ASC program instead of downloading binary files: %%HP:T(1); "D9D20E1632B9691CCD20F6000AF910A1371091371471371791537822AF1AF3B6 7AF69FBF1B7581C832FEA72B76AFAB7582255EAF9155711913711AAF51421648 08CBB69193632B2130DE8E" Have fun. Who knows; you might become rich and famous! Joseph K. Horn -- (714) 858-0920 -- Peripheral Vision, Ltd.