### The Collatz Conjecture

April 14, 2011 Iteration is a large part of our lives. We seem to do the same things, again and again. Any given day of our week is likely a carbon copy of that same day the week before. This repetition was much more regular to our agrarian ancestors; so much so, that they had a different concept of time. The idea of "deep time" was unknown to them, since they had no conception that the Earth, which was their universe, had a beginning and would have an end. Time to them was cyclic. The same things happened over and over, whether by the day or by the season. One of the most important constructs in computer programming is the loop, which uses iteration in a useful fashion. Iteration is built into mathematics in series expansions, which have given us very accurate values for the trigonometric functions, and many digits of pi. The Newton–Raphson method, a method for refining calculation of roots, is another useful iterative technique. There's a "dark side" of iteration; namely, those iterations that don't converge to a simple result. Iteration is at the heart of the Mandelbrot set. John von Neumann proposed the following iteration as a random number generator.[1]xThere's prior art to this in the work of Gauss, who remarked on the complexity of the iteration,[1]_{n+1}= 4x_{n}(1 - x_{n})

xA random number generator that was popular in the early computing days of slow clock rates and small memories is an iteration called the linear congruential generator (LCG),_{n+1}= FractionalPart[1/x_{n}]

xCommon values for the LCG parameters are m = 2_{n+1}= (ax_{n}+ b) mod m

^{32}, a = 1664525 and b = 1013904223. The sequence is seeded by any x

_{0}value between 0 and m. The logistic map is an iteration that produces a variety of responses dependent on its initial parameter. The equation is

xThe logistic map produces a chaotic sequence for r values between 3.57 and 3.83._{n+1}= rx_{n}(1 - x_{n})

*Logistic map for an initial value of 0.33 and r = 3.7. (Plot via Gnumeric)*

The Collatz conjecture is a conjecture involving the progression of values of an iteration. Unlike the iterations above, the Collatz iteration has a condition statement thrown in. This number sequence is constructed as follows:

1) Start with a natural number, nAs you can see, step 2 will always decrease n, and step 3 will always increase n, so you can expect some random up-down action. What you don't expect is that you always terminate in n = 1, no matter the value of n_{0}

2) If n is even, then n_{i+1}= n_{i}/2

3) If n is odd, then n_{i+1}= 3n_{i}+ 1

4) Continue at step (2) until n = 1

_{0}. The conjecture is that this is always the case. The following plot shows the sequence starting at n = 983, as generated by this program.

*Collatz sequence starting with n = 983. (Plot via Gnumeric)*

Lest you think that larger numbers will favor longer sequences, look at the sequences for the numbers 27 and 908:

27 → 41 → 62 → 31 → 47 → 71 → 107 → 161 → 242 → 121 → 182 → 91 → 137 → 206 → 103 → 155 → 233 → 350 → 175 → 263 → 395 → 593 → 890 → 445 → 668 → 334 → 167 → 251 → 377 → 566 → 283 → 425 → 638 → 319 → 479 → 719 → 1079 → 1619 → 2429 → 3644 → 1822 → 911 → 1367 → 2051 → 3077 → 4616 → 2308 → 1154 → 577 → 866 → 433 → 650 → 325 → 488 → 244 → 122 → 61 → 92 → 46 → 23 → 35 → 53 → 80 → 40 → 20 → 10 → 5 → 8 → 4 → 2 → 1

908 → 454 → 227 → 341 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1All this adds to the mystery of this sequence. This interesting recursion was discovered in 1932 by Lothar Collatz, who was at the time a twenty year old mathematics student. As discussed in an entertaining book of number anecdotes by George Szipiro,[2] the Collatz conjecture has had many names over the years before reverting to that of its discoverer. It was popularized in the US by Stanislaw Ulam, who introduced it to the extremely talented corp of people who worked with him on the Manhattan Project. For a time after that it was known as Ulam's problem. Then it became known as the Hailstone sequence because of the similarity of the up-down motion of its numbers to the process of hailstone formation. It was also known as the Kakutani problem, after another mathematician who worked on the conjecture. We shouldn't be too surprised at this, since it happened in the days before computer-assisted search.

### References:

- Stephen Wolfram, "A New Kind of Science," Wolfram Media, May 14, 2002, page 918.
- George G. Szipiro, "The Secret Life of Numbers," Joseph Henry Press (Washington, D.C., 2006), Chapter 6 ("A Puzzle by Any Other Name"). pp. 20-23 (Via Amazon).

*Permanent Link to this article*

Linked Keywords: Iteration; carbon copy; agrarian ancestors; deep time; Earth; universe; computer programming; loop; mathematics; series expansion; trigonometric functions; pi; Newton–Raphson method; nth root; Mandelbrot set; John von Neumann; random number generator; Carl Friedrich Gauss; linear congruential generator; logistic map; chaotic sequence; Gnumeric; Collatz conjecture; condition statement; conjecture; Lothar Collatz; Stanislaw Ulam; Manhattan Project; hailstone; Shizuo Kakutani; web search engine; computer-assisted search; Stephen Wolfram; A New Kind of Science; George G. Szipiro; The Secret Life of Numbers.

### Google Search

Latest Books by Dev Gualtieri

Thanks to Cory Doctorow of BoingBoing for his favorable review of Secret Codes!

Other Books

- The First Angiosperm - September 18, 2017

- Noise Thermometry and the Boltzmann Constant - September 11, 2017

- Walking in the Rain - September 4, 2017

- Agitated Atoms - August 28, 2017

- Partial Solar Eclipse at New Jersey - August 24, 2017

- Magnetocapacitive Tunnel Junctions - August 21, 2017

- Tardigrades - August 14, 2017

- Roman Concrete - August 7, 2017

- Solar Spicules - July 31, 2017

- Schroeder Diffuser - July 24, 2017

- Rough Microparticles - July 17, 2017

- Robot Musicians - July 10, 2017

- Walter Noll (1925-2017) - July 6, 2017

- cosmogony - July 3, 2017

- Crystal Prototypes - June 29, 2017

- Voice Synthesis - June 26, 2017

- Refining Germanium - June 22, 2017

- Granular Capillarity - June 19, 2017

- Kirchhoff–Plateau Problem - June 15, 2017

- Self-Assembly - June 12, 2017

- Physics, Math, and Sociology - June 8, 2017

- Graphene from Ethylene - June 5, 2017

- Crystal Alignment Forces - June 1, 2017

- Martian Brickwork - May 29, 2017

- Carbon Nanotube Textile - May 25, 2017

- The Scent of Books - May 22, 2017

- Patterns from Randomness - May 18, 2017

- Terpene - May 15, 2017

- The Physics of Inequality - May 11, 2017

- Asteroid 2015 BZ509 - May 8, 2017

- Fuzzy Fibers - May 4, 2017

- The Sofa Problem - May 1, 2017

- The Wisdom of Composite Crowds - April 27, 2017

- J. Robert Oppenheimer and Black Holes - April 24, 2017

- Modeling Leaf Mass - April 20, 2017

- Easter, Chicks and Eggs - April 13, 2017

- You, Robot - April 10, 2017

- Collisions - April 6, 2017

- Eugene Garfield (1925-2017) - April 3, 2017

- Old Fossils - March 30, 2017

- Levitation - March 27, 2017

- Soybean Graphene - March 23, 2017

- Income Inequality and Geometrical Frustration - March 20, 2017

- Wireless Power - March 16, 2017

- Trilobite Sex - March 13, 2017

- Freezing, Outside-In - March 9, 2017

- Ammonia Synthesis - March 6, 2017

- High Altitude Radiation - March 2, 2017

### Deep Archive

Deep Archive 2006-2008

**Blog Article Directory on a Single Page**