Matt's Solitaire Game Interesting if you haven't seen it before: Matt's got an hour to kill.  He decides to play his own game of solitaire. He picks a random positive integer (say a page # from a book) and does the following with it: 1. If the number is even, he halves it. 2. If the number is odd, he multiplies it by 3 and adds 1. He repeats these steps over and over until he gets the number 1, or the hour is up.  Assuming it takes him 1 minute to go through one iteration of these steps, how big should the initial random number be to keep him occupied throughout the hour?  Does it even matter?  Is the loop infinite in every case? Vin Monday, April 22, 2002 Scientific American did an article on this many years ago.  (Something like 10-15 years maybe.)  The conjecture is that this works for every positive integer.  It's been proven for every number less than maybe 1000 or so, except for one, which is - I can't remember.  192, 196, something like that. Paul Brinkley Monday, April 22, 2002 And before anyone replies, I know what I just said is inconsistent.  If 196 or 192 didn't work, neither would 98 or 96, and I just said it had been proven to work for all other numbers.  :-)  But hey, whaddya want, it's been a decade or so. Paul Brinkley Monday, April 22, 2002 FWIW, 192 collapses to 1 in only 13 steps.  196 takes quite a bit longer - 39 steps. Paul Brinkley Monday, April 22, 2002 This is often called the Collatz problem, Kakutani's problem, Ulam's problem, or even the Syracuse algorithm.  A cursory search on Google! comes up with a page full of links http://www.geometry.net/Theorems_and_Conjectures/Collatz_Problem.htm I've read papers from the mundane (statements that computers have proved the conjecture for up to n (for some large n)) to the out-there (trying to associate the problem with universal Turing machines and equate the conjecture to the Halting problem). Jeremy Horwitz Friday, May 10, 2002   Fog Creek Home