Walking to school, we played a game. One player would pick a number up to 100. The other player would try to get that number down to 1 by following the rules:
Rule 1: If the number is odd, triple it and add one, so 13 becomes 40.
Rule 2: If the number is even, chop it in half, so 40 becomes 20.
Continue: 20, 10, 5, 16, 8, 4, 2, 1. Sometimes numbers would get into three digits, testing the limits of our mental arithmetic. Other times we would land in a familiar chain and quickly work our way down to 1. Neither of us was able to find a starting number that prevented the other player from eventually getting to 1 (or else getting stuck in a loop different from 1, 4, 2, 1, 4, 2...).
No one else has been able to find a starting number that does not reach 1 either.
I was tipped off to this game by some light bathroom reading but could not imagine how deep this rabbit hole goes.
The Collatz Conjecture, that all positive integers eventually reach 1 in this game, seems to have been first considered around 1950 and began distracting people in earnest in the 1960s.
Shizuo Kakutani remarked “For about a month everybody at Yale worked on it, with no result. A similar phenomenon happened when I mentioned it at the University of Chicago. A joke was made that this problem was part of a conspiracy to slow down mathematical research in the U.S.”
Stanisław Ulam carried the infection to Los Alamos. The legendary Paul Erdős said that “mathematics is not yet ready for such problems.”
A distributed computing project tested starting numbers in blocks of twenty trillion and verified that all values up to 2^58 eventually get to 1. But no one has found a proof.
A complex function that encodes the conjecture generates a pretty fractal.
Numberphile covered the strangely organic shape of a Collatz graph.
Another group found more bizarre images.
And, as often happens, just before posting I find that mk has been down this road before.
I've "wasted" happy hours with this. Wrote a post about it when I was writing a blog for the Norwegian national math education center: http://www.matematikksenteret.no/content/2159/Collatz-formodning-The-Collatz-Conjecture I'm re-inspired by those pics! Gonna fire up Processing now and play... maybe find a new way to visualize, maybe just find a new way to lose a few hours...
That second graph is so cool! I decided to make my own real quick: matrix = numpy.zeros(10000) for i in range(1, 10000): counter = 0 pos = i while pos != 1: if pos % 2 == 0: pos = pos / 2 counter = 1 else: pos = pos*3 1 counter += 1 matrix[i] = counter print(i, counter) matplotlib.pyplot.figure(figsize = (20,10)) matplotlib.pyplot.scatter(range(1, 10000), matrix[1:10000], s=1) (Gotta love Python eh!)
import numpy, matplotlib.pyplot