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

  Recent Topics

  Fog Creek Home