The distribution of \(3x+1\) trees. (English) Zbl 0868.11012

The \(3x+1\) function is defined by \(T(n)=n/2\) for \(n\) even, \(T(n)=(3n+1)/2\) for \(n\) odd. Starting from a positive integer \(a\), backward iteration of \(T\) produces a tree of preimages. It is convenient to “prune” this tree by removing the nodes \(n\equiv 0\bmod 3\); denote by \({\mathcal T}^*_k(a)\) the pruned tree extended up to depth \(k\). On the other hand, a sequence \({\mathcal B}[3^j]\) of branched processes designed to model backward iteration of \(T\) had been studied previously [J.-C. Lagarias and A. Weiss, Ann. Appl. Probab. 2, 229-261 (1992; Zbl 0742.60027)].
Here empirical data concerning the minimal and the maximal numbers of leaves of depth \(k\) of \({\mathcal T}^*_k(a)\) are compared to predictions produced by the branched process \({\mathcal B}[9]\). The result is: The range of the leaf counts observed empirically using the trees \({\mathcal T}^*_k(a)\) is significantly narrower than that “predicted” by the stochastic model.
In the final section, fluctuations of the leaf counts of such trees caused by the branching pattern at the base of the tree are studied. Appropriately normalized, the leading terms of these fluctuations are martingale with respect to the \(\sigma\)-fields \(\{{\mathcal F}_j: j\geq 1\}\), with \({\mathcal F}_j=\{\text{residue classes mod }3^j\}\). Then the Martingale Convergence Theorem is applied to show that the normalized variations of leaf counts lead to a function \(W_\infty\) that is defined almost everywhere on the group \(\mathbb{Z}^\times_3\) of invertible 3-adic numbers. It is conjectured that \(W_\infty\) is a continuous function on \(\mathbb{Z}^\times_3\), and it is shown that this is connected to a conjecture called \(C^\#\) concerning the asymptotic behaviour of the extreme leaf counts.


11B83 Special sequences and polynomials
11B37 Recurrences
60G46 Martingales and classical analysis


Zbl 0742.60027


[1] Applegate D., Math. Comp. 64 pp 411– (1995)
[2] Applegate D., Math. Comp. 64 pp 427– (1995)
[3] Athreiya K. B., Branching Processes (1972)
[4] Billingsley P., Probability and Measure (1979)
[5] Borovkov K., ”Estimates for the Syracuse problem via a probabilistic model” (1993) · Zbl 0984.60050
[6] Crandall R. E., Math. Comp. 32 pp 1281– (1978)
[7] Harris T. E., The Theory of Branching Processes (1963) · Zbl 0117.13002
[8] DOI: 10.1214/aoms/1177699266 · Zbl 0203.17401 · doi:10.1214/aoms/1177699266
[9] DOI: 10.2307/2322189 · Zbl 0566.10007 · doi:10.2307/2322189
[10] Lagarias J. C., Ann. Applied Prob. 2 pp 229– (1992) · Zbl 0742.60027 · doi:10.1214/aoap/1177005779
[11] Leavens G., Computers and Mathematics, with Applications 24 (11) pp 79– (1992) · doi:10.1016/0898-1221(92)90034-F
[12] Müller H., Mitteilungen Math. Ges. Hamburg 12 pp 231– (1991)
[13] Rawsthorne D. W., Math. Mag. 58 pp 172– (1985) · Zbl 0587.10030 · doi:10.2307/2689917
[14] Wagon S., Math. Intelligencer 7 pp 72– (1985) · Zbl 0566.10008 · doi:10.1007/BF03023011
[15] Wirsching G. J., Rev. Roum. Math. Pure Appl. 39 pp 915– (1994)
[16] Wirsching G. J., Habilitationsschrift (1995)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.