The \(3x+1\) problem, generalized Pascal triangles and cellular automata. (English) Zbl 0773.11016

Let \(T:\mathbb{N}\to\mathbb{N}\) be defined by \(T(n)=(3n+1)/2\), \(n\) odd, and \(T(n)=n/2\), \(n\) even. The sequence \((n,T(n),T(T(n)),\dots)\) is called the \(T\)-trajectory of \(n\). There are several unsolved hypotheses connected with the iterations of \(T\); for example the “\(3x+1\)” (or Collatz or Hasse or Kakutani or Syracuse)-conjecture: For every \(n\in\mathbb{N}\) the \(T\)- trajectory starting with \(n\) contains the value 1.
Generalized Pascal triangles are defined similarly to the classical Pascal triangle, but instead of 0 and the addition of integers operations of a finite algebra is used.
In this note two algebras (consisting of 7 or 8 elements) are constructed in such a way that some structural properties of their generalized Pascal triangles are equivalent to the “\(3x+1\)”-conjecture. In terms of cellular automata, the 8 element automaton is nilpotent if and only if the “\(3x+1\)”-conjecture holds. So one can hope that this translation to cellular automata could help to visualize the underlying number-theoretic problems.


11B83 Special sequences and polynomials
68Q80 Cellular automata (computational aspects)
68R15 Combinatorics on words
Full Text: EuDML


[1] CLONEY T., GOLES C. E., VICHNIAC G. Y.: The 3x + 1 problem: A quasi-cellular automaton. Complex Systems 1 (1987), 349-360. · Zbl 0662.10010
[2] CULIK H. K., GRUSKA J., SALOMAA A.: Systolic trellis automata. Internat. J. Comput. Math. 15 and 16 (1984), 195 -212 and 3-22. · Zbl 0571.68042
[3] CULIK H. K., HURD L. P., YU S.: Computation theoretic aspects of cellular automata. Phys. D 45 (1990), 357-378. · Zbl 0729.68052
[4] KOREC I.: Generalized Pascal triangles. Decidability results, Acta Math. Univ. Comen. XLVI-XLVII (1985), 93-130. · Zbl 0607.05002
[5] KOREC I.: Generalized Pascal triangles. (Slovak), DrSc. Thesis, UK Bratislava. 1984. · Zbl 0734.68072
[6] KOREC I.: Generalized Pascal triangles. Proceedings of the V Universal Algebra Symposium, Turawa, Poland, May 1988 (K. Halkowska and S. Stawski, World Scientific, Singapore, 1989, pp. 198-218. · Zbl 0612.68048
[7] KUIPERS L. NIEDERREITEIR H.: Uniform distribution of sequences. J. Wiley & Sons, New York, 1974.
[8] LAGARIAS J. C.: The 3x + 1 problem and its generalizations. Amer. Math. Monthly 92 (1985), 3-23. · Zbl 0566.10007
[9] WOLFRAM S.: Computation theory of cellular automata. Comm. Math. Phys. 96 (1984), 15-57. · Zbl 0587.68050
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.