Sunday, March 27, 2011

The Nightmare of an Unsolved Problem

Back in the 1980s when I first met the Collatz conjecture in a number theory textbook it was stated this way:
     Start with any whole number  n :
          If  n  is even, reduce it by half, obtaining  n/2.
          If n is odd, increase it by half and round up to the nearest whole number, obtaining  3n/2 + 1/2 = (3n+1)/2.   Collatz' conjecture asserts that, no matter what the starting number, iteration of this increase-decrease process will each time reach the number 1.   

      For example, we have
          13 → 20 → 10 → 5 → 8 → 4 → 2 → 1  (7 steps)
          23 → 35 → 53 → 80 → 40 → 20 → 10 → 5 → 8 → 4 → 2 → 1  (11 steps)
On the other hand, when we use 27 as a starting number, it requires 70 steps before the sequence reaches 1; after climbing as high as 4616, it drops below 27 for the first time -- to 23 --  on the 59th step. 
     The Collatz conjecture (first proposed by Lothar Collatz in 1937) remains unsolved. During the last 20 years, the conjecture has been known by several names and is often called "the 3n + 1 conjecture."     Because I have spent many many sleepless hours working on the Collatz conjecture, when I describe it in a poem, my title is "A Mathematician's Nightmare."  (Also in the background of my poem is myself as unskilled bargain hunter -- getting a best buy rarely and always by accident. In the poetic case, at least, my mathematical knowledge helps me to know the right amount of time to wait for a good price.)

     A Mathematician's Nightmare     by JoAnne Growney

     Suppose a general store —
     items with unknown values
     and arbitrary prices,
     rounded for ease to
     whole-dollar amounts.

     Each day Madame X,
     keeper of the emporium,
     raises or lowers each price —
     exceptional bargains
     and anti-bargains.

     Even-numbered prices
     divide by two,
     while odd ones climb
     by half themselves —
     then half a dollar more
     to keep the numbers whole.

     Today I pause before
     a handsome beveled mirror
     priced at twenty-seven dollars.
     Shall I buy or wait
     for fifty-nine days
     until the price is lower?

Randall Munroe at his webcomic site, xkcd.com, has a cartoon that also describes the nightmare of the Collatz Conjecture.  Whereas my version of the conjecture calculates (3n+1)/2 when n is odd, Munroe's drawing refers to a version that calculates (3n+1) when n is odd; then, in an additional step, divides that result by 2.  In this "3n+1" version of the conjecture, the sequence that starts with 13 now has 9 steps instead of 7 and looks like this:

          13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1  (9 steps)
 

No comments:

Post a Comment