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

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


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