Deterministic Structures in the Stopping Time Dynamics of the 3x+1 Problem

Abstract

The $3x+1$ problem concerns the iteration of the map $T:\mathbb{Z}\to \mathbb{Z}$ defined by $T(x)=x/2$ for even $x$ and $T(x)=(3x+1)/2$ for odd $x$. We study the coefficient stopping time in the sense of Terras. For each order $n$, we characterize the corresponding residue classes modulo $2^{\ddot{I}{ƒ}_n}$ by the admissible positions of the odd iterates. These position vectors form a directed rooted tree under deletion of the final odd position. This description yields a Pascal-type recursion for the number of classes and proves that the recursive generation produces exactly the admissible vectors, each exactly once. The affine iterate formula gives explicit congruence relations for the classes and arithmetic transition rules between related parity vectors. For every fixed $N$, the union of the classes generated up to order $N$ is periodic with period $2^{\ddot{I}{ƒ}_N}$. Its density is given by an exact finite sum, and its largest initial interval of coverage can be computed from one period. These results concern finite coefficient stopping-time structures. They neither prove that every starting value has finite coefficient stopping time nor establish equality between the coefficient stopping time and the classical stopping time.

28 pages, 3 figures, 4 tables, 9 programs in PARI/GP