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

Korec, Ivan

Math. Slovaca 42, No. 5, 547-563 (1992).

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.

Reviewer: H.Müller (Hamburg)

MSC:

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

Keywords:

Collatz function; \(3x+1\)-conjecture; generalized Pascal triangles; cellular automata

References:

[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