The \(3x+1\) problem: A quasi cellular automaton. (English) Zbl 0662.10010

Cloney, Thomas; Goles, Eric; Vichniac, Gérard Y.

Complex Syst. 1, No. 2, 349-360 (1987).

The “Collatz-Ulam-Syracuse-Kakutani” problem, at its simplest, is the study of the iterates of \(f(x)\) defined equal to \((3x+1)/2\) if x is an odd natural number, and equal to \(x/2\) if \(x\) is an even natural number. Whether \(f\) iterates to 1 is an unresolved issue. The authors show empirical results of the first 717 iterates of \(f\) for a variety of initial values for \(x\), of the order \(10^{300}\). The graphical representations of the iterates expressed in base 2 reveal regular patterns and chaotic behavior, some of which seems partly dependent on the process for generating the random seeds. Their figures also show a resemblance to one-dimensional cellular automata patterns, not unsurprisingly given the effect in base 2 of the definition of the f function. Heuristic arguments, illustrated by the figures, are given for the steady behavior of large iterates, and, for the decay in the size of successive iterates.

Reviewer: G.Lord

MSC:

11B37	Recurrences
11B39	Fibonacci and Lucas numbers and polynomials and generalizations
68Q80	Cellular automata (computational aspects)
68Q45	Formal languages and automata

Keywords:

Collatz-Ulam-Syracuse-Kakutani problem; Collatz problem; cellular automata; large iterates