Collatz Conjecture

Define f(n) = n/2 if n is even, and f(n) = 3n + 1, if n is odd. Collatz conjecture claims that regardless of the starting point the iterations settle eventually into a 3-cycle: 4, 2, 1, 4.

As a variant, an even number may be stripped entirely of its even factors (not just divided by 2) which leads to a shorter 2-cycle 4, 1, 4. For small numbers convergence is sufficiently fast to be observed even if calculations are carried by hand. The first number that takes more than 100 iterations is 27. Then such numbers become more frequent: 27, 31, 41, 47, 55, 62, ...

Why is it called a conjecture? For a very simple reason that mathematicians have not yet found a way to prove it. The statement is named after Lothar Collatz who proposed it in 1937. Over the time, the statement and its simplicity drew the interest of various mathematicians and was probably arrived at independly by many of them. It goes under different names: 3n + 1 conjecture, the Ulam conjecture, the Syracuse problem, the hailstone sequence, just to give a few examples. However, as Paul Erdõs once remarked, "Mathematics is not yet ready for such problems."

In the more economical form described by R. Terras, where, for an odd n, f(n) = (3n + 1)/2, the conjecture found its way into modern poetry. The American poetess, JoAnne Growney, even composed a poem celebrating the statement:

A Mathematician's Nightmare

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?

(As you can check with the applet, the first time the price happens to be lower than the original $27 comes on the 59^th day. Short time afterwards, on day 69, the iterations enter the 2, 1 loop.)

Copyright © 1996-2009 Alexander Bogomolny