Chapter 4: Systems Based on Numbers

Section 2: Elementary Arithmetic

3n+1 problem as cellular automaton

If one writes the digits of n in base 6, then the rule for updating the digit sequence is a cellular automaton with 7 possible colors (color 6 works as an end marker that appears to the left and right of the actual digit sequence):

{a_, b_, c_} -> If[b==6, If[EvenQ[a], 6, 4], 3 Mod[a, 2] + Quotient[b, 2] /. 0 :> 6 /; a == 6]

The 3n+1 problem can then be viewed as a question about the existence of persistent structure in this cellular automaton.

From Stephen Wolfram: A New Kind of Science [citation]