betaFeedback

WorksMathematics

Up or down by half: a family of Collatz-type maps

Abstract

Each Collatz step changes a positive integer by roughly half: odd inputs go up and even inputs go down. We vary the directions while keeping the step size. Write x=2^m k (k odd), and let S be a set of positive integers. Define T_S(x)=(3x+1)/2 if m=0, 3x/2 if m is in S, and k otherwise. The map T_S^- differs only at odd x, which it sends to (x+1)/2. The usual Collatz map is T_emptyset. Assuming the independence of 2-adic valuations along odd-to-odd steps yields random-walk models with drifts (1+rho(S))log_2(3)-2 for T_S and rho(S)log_2(3)-2 for T_S^-, where rho(S) is an explicit series. Every T_S^- is contracting; T_S is contracting exactly when rho(S)<log_3(4/3), approximately 0.2619. We prove density results, classify interval sets S, and give a criterion ensuring every T_S^- orbit reaches 1 or (2,3). For seven contracting maps T_S, three with rho(S)=1/4 just below the threshold, computations show that every n<2^34 (n<1.668*10^10 for S={1}) reaches one of at most five cycles; stopping-time statistics match the model to 3-5 digits. We study branching maps, where any member of a family may be applied at each step. Boundedness of a family implies boundedness of each member; in particular, boundedness of {T_emptyset,T_{3}} would imply that no Collatz orbit diverges. For {T_emptyset,T_{1}}, a rule depending only on x mod 32 has positive drift (10/17)log_2(9/8) for almost every 2-adic starting point. Thus almost all n have reachable sets containing values larger than n^1.05; residues modulo 2^L, L<=10, cannot prove unboundedness. Finally, we define unified maps in which valuations also determine the direction at odd inputs. The cases x=1 mod 4 govern their behavior: if they go down, every block is dominated by the corresponding Collatz map (and a census finds only the cycles (1), (2, 3) and (3, 5) with smallest element below 10^9); if they go up, the maps behave like T_S.

Introduction

The Collatz map

T(x)={(3x+1)/2,x odd,x/2,x even.T(x) = \begin{cases} (3x + 1)/2, & x\ \text{odd},\\ x/2, & x\ \text{even}. \end{cases}

changes a positive integer by about half of its value at every step: an odd xx goes up by (x+1)/2(x + 1)/2, an even xx goes down by x/2x/2. The Collatz conjecture states that every orbit eventually reaches the cycle (1,2)(1, 2); see Lagarias’s surveys and annotated bibliographies [17, 22, 21, 19, 20] and the monograph of Wirsching [31]. In this paper we keep the size of the steps and vary their direction: at some numbers we go up where the Collatz map goes down, or down where it goes up. This gives a family of maps that contains the Collatz map, maps whose orbits are expected to diverge, and maps for which the analogue of the conjecture is easy to prove. One can then ask which members are easier than the Collatz map, and whether statements can be transferred from one member to another.

We let the direction depend on the 2-adic valuation of the current number. Write every positive integer uniquely as x=2mkx = 2^{m}k with kk odd, and let N={1,2,3,…}\mathbb{N} = \{1, 2, 3, \ldots\}.

Definition 1.1. For S⊆NS \subseteq\mathbb{N} let TS,TS−:N→NT_{S}, T_{S}^{-}: \mathbb{N} \to\mathbb{N} be

TS(x)={(3x+1)/2,m=0,3x/2,m∈S,k,m≥1, m∉S,TS−(x)={(x+1)/2,m=0,3x/2,m∈S,k,m≥1, m∉S,(1)T_{S}(x) = \begin{cases} (3x+1)/2, & m=0,\\ 3x/2, & m \in S,\\ k, & m \ge1,\ m \notin S, \end{cases} \qquad T_{S}^{-}(x) = \begin{cases} (x+1)/2, & m=0,\\ 3x/2, & m \in S,\\ k, & m \ge1,\ m \notin S, \end{cases} \tag*{(1)}

where x=2mkx = 2^{m}k with kk odd.

Thus SS is the set of exponents m≥1m \ge1 at which the map goes up, and odd numbers go up under TST_{S} and down under TS−T_{S}^{-}; equivalently, the two families together are indexed by the set of all exponents m≥0m \ge0 at which the map goes up. A downward step at an even number removes all factors of 2 at once. For the Collatz map this only merges a run of halvings into one step: T∅T_{\varnothing} sends an even number directly to its odd part, so its orbits are the Collatz orbits with every run of halvings compressed, and T∅T_{\varnothing} has a divergent or a nontrivial periodic orbit exactly when TT does. (Theorem 3.5 discusses the variant in which a downward step halves only once.)

For example, for S={1}S = \{1\} the number 26=2⋅1326 = 2 \cdot13 has m=1∈Sm = 1 \in S and goes up to 3939, while 680=23⋅85680 = 2^{3} \cdot85 has m=3∉Sm = 3 \notin S and goes down to 8585; under the Collatz map T∅T_{\varnothing} both would go down to their odd parts 1313 and 8585.

An orbit of a map f:N→Nf : \mathbb{N} \to\mathbb{N} is either eventually periodic, in which case it ends in a cycle {x,f(x),…,fp−1(x)}\{x, f(x), \ldots, f^{p-1}(x)\} with fp(x)=xf^{p}(x) = x, or it consists of pairwise distinct numbers and then tends to infinity; in the second case we say that the orbit diverges. The analogue of the Collatz conjecture for TST_{S} is the statement that no orbit of TST_{S} diverges. Unlike the Collatz map, most maps TST_{S} have several cycles (see Tables A.2 and 5.1); we write a cycle as a tuple that starts with its smallest element.

The Collatz map appears in the family a second time: TN−(x)=T(x−1)+1T_{\mathbb{N}}^{-}(x) = T(x-1)+1 (Theorem 6.1). So the family of maps TST_{S} starts at the Collatz map and its downward pull weakens as SS grows, up to TN(x)=⌈3x/2⌉>xT_{\mathbb{N}}(x) = \lceil3x/2 \rceil> x, whose orbits all diverge; the family of maps TS−T_{S}^{-} ends at the Collatz map and its pull strengthens as SS shrinks, down to T∅−T_{\varnothing}^{-}, whose orbits all decrease to 11. For example,

T{1}:7, 11, 17, 26, 39, 59, 89, 134, 201, 302, 453, 680, 85, 128, 1, 2, 3, 5, 8, 1,…T_{\{1\}}:\quad7,\,11,\,17,\,26,\,39,\,59,\,89,\,134,\,201,\,302,\,453,\,680,\,85,\,128,\,1,\,2,\,3,\,5,\,8,\,1,\ldots
T{2,4,6,…}:7, 11, 17, 26, 13, 20, 30, 15, 23, 35, 53, 80, 120, 15,…T_{\{2,4,6,\ldots\}}:\quad7,\,11,\,17,\,26,\,13,\,20,\,30,\,15,\,23,\,35,\,53,\,80,\,120,\,15,\ldots
T{1,2,3}−:15, 8, 12, 18, 27, 14, 21, 11, 6, 9, 5, 3, 2, 3,…T_{\{1,2,3\}}^{-}:\quad15,\,8,\,12,\,18,\,27,\,14,\,21,\,11,\,6,\,9,\,5,\,3,\,2,\,3,\ldots
TN:28, 42, 63, 32, 48, 72, 108, 162, 243, 122, 183, 92,…T_{\mathbb{N}}:\quad28,\,42,\,63,\,32,\,48,\,72,\,108,\,162,\,243,\,122,\,183,\,92,\ldots

The first orbit ends in the cycle (1,2,3,5,8)(1, 2, 3, 5, 8), the second in (15,23,35,53,80,120)(15, 23, 35, 53, 80, 120); the third and fourth end in (2,3)(2, 3) (the fourth is the Collatz orbit of 2727 shifted by one; it takes 7171 steps to first repeat). The questions that motivate this paper are: for which SS is the analogue of the Collatz conjecture plausible, what do the orbits of the maps near the boundary look like, and can a statement be proved more easily for one map than for another, or be transferred from one map to another?

The heuristic

The following heuristic, standard for the Collatz map [8, 23, 13], indicates which maps TST_S should have only eventually periodic orbits. Consider only the odd numbers x0,x1,x2,…x_0, x_1, x_2, \ldots of an orbit of TST_S. The step from xix_i to xi+1x_{i+1} begins with x↦3x+1x \mapsto3x+1, which produces Mi+1=v2(3xi+1)≥1M_i+1 = v_2(3x_i+1) \ge1 factors 2; the map then trades some of them, say rir_i, for factors 3 by steps x↦3x/2x \mapsto3x/2, and removes the remaining ones. Thus

xi+1≈31+ri2Mi+1xi,that is,log⁡2xi+1−log⁡2xi≈(1+ri)log⁡23−(Mi+1).x_{i+1} \approx\frac{3^{1+r_i}}{2^{M_i+1}}x_i,\qquad\text{that is,}\qquad\log_2 x_{i+1}-\log_2 x_i \approx(1+r_i)\log_2 3-(M_i+1).

For a random odd integer xx the valuation v2(3x+1)v_2(3x+1) equals kk with probability 2−k2^{-k}, so P(M=m)=2−(m+1)\mathbb{P}(M=m)=2^{-(m+1)} for m≥0m\ge0. If the MiM_i along an orbit behave like independent random variables with this law (Theorem 3.1 makes this precise in a 2-adic sense), then log⁡2xi\log_2 x_i performs a random walk, and the sign of its drift, the expected number of bits gained per odd step, decides whether orbits should come down or go up. For the Collatz map ri=0r_i=0 and the drift is log⁡23−2≈−0.415\log_2 3-2\approx-0.415: each odd step multiplies by 3 and removes two factors 2 on average. For TST_S the number rir_i is a function of MiM_i determined by SS, and the drift is (1+ρ(S))log⁡23−2(1+\rho(S))\log_2 3-2, where ρ(S)\rho(S) is the expected value of rir_i.

Results

References

  1. [1]I. Althöfer, M. Hartisch, and T. Zipproth, Analysis of a Collatz game and other variants of the 3n + 1 problem, Advances in Computer Games (ACG 2023), Lecture Notes in Comput. Sci., vol. 14528, Springer, 2024, pp. 123–132.DOI
  2. [2]I. Althöfer and T. Zipproth, Divergence in a Collatz-type recursion, 2025, Preprint, https://althofer.de/althofer-zipproth-august-2025.pdf.
  3. [3]D. Bařina, Improved verification limit for the convergence of the Collatz conjecture, J. Supercomput. 81 (2025), Paper No. 810, doi:10.1007/s11227-025-07337-0.DOI
  4. [4]______, Path records, Web page, https://pcbarina.fit.vutbr.cz/path-records.htm, 2026, Accessed October 2026.
  5. [5]J. D. Biggins, The first- and last-birth problems for a multitype age-dependent branching process, Adv. in Appl. Probab. 8 (1976), 446–459.DOI
  6. [6]R. P. Brent, An improved Monte Carlo factorization algorithm, BIT 20 (1980), 176–184.DOI
  7. [7]J. H. Conway, Unpredictable iterations, Proceedings of the 1972 Number Theory Conference (University of Colorado, Boulder), 1972, pp. 49–52.
  8. [8]R. E. Crandall, On the “3x + 1” problem, Math. Comp. 32 (1978), 1281–1292.
  9. [9]C. J. Everett, Iteration of the number-theoretic function f (2n) = n, f (2n + 1) = 3n + 2, Adv. Math. 25 (1977), 42–45.
  10. [10]W. Feller, An introduction to probability theory and its applications, vol. II, 2nd ed., Wiley, New York, 1971.
  11. [11]J. M. Hammersley, Postulates for subadditive processes, Ann. Probab. 2 (1974), 652–680.DOI
  12. [12]J. F. C. Kingman, The first birth problem for an age-dependent branching process, Ann. Probab. 3 (1975), 790–801.DOI
  13. [13]A. V. Kontorovich and J. C. Lagarias, Stochastic models for the 3x + 1 and 5x + 1 problems and related problems, The Ultimate Challenge: The 3x + 1 Problem (J. C. Lagarias, ed.), Amer. Math. Soc., Providence, RI, 2010, arXiv:0910.1944.arxiv.org/abs/0910.1944
  14. [14]A. V. Kontorovich and Ya. G. Sinai, Structure theorem for (d,g,h)-maps, Bull. Braz. Math. Soc. (N.S.) 33 (2002), 213–224.DOI
  15. [15]I. Korec, A density estimate for the 3x + 1 problem, Math. Slovaca 44 (1994), 85–89.
  16. [16]S. A. Kurtz and J. Simon, The undecidability of the generalized Collatz problem, Theory and Applications of Models of Computation (TAMC 2007), Lecture Notes in Comput. Sci., vol. 4484, Springer, 2007, pp. 542–553.DOI
  17. [17]J. C. Lagarias, The 3x + 1 problem and its generalizations, Amer. Math. Monthly 92 (1985), 3–23.DOI
  18. [18]———, The set of rational cycles for the 3x + 1 problem, Acta Arith. 56 (1990), 33–53.DOI
  19. [19]———, The 3x + 1 problem: an annotated bibliography (1963–1999), 2003, arXiv:math/0309224.arxiv.org/abs/math/0309224
  20. [20]———, The 3x + 1 problem: an annotated bibliography, II (2000–2009), 2006, arXiv:math/0608208.arxiv.org/abs/math/0608208
  21. [21]———, The 3x + 1 problem: an overview, The Ultimate Challenge: The 3x + 1 Problem (J. C. Lagarias, ed.), Amer. Math. Soc., Providence, RI, 2010, arXiv:2111.02635.
  22. [22]J. C. Lagarias (ed.), The ultimate challenge: The 3x + 1 problem, Amer. Math. Soc., Providence, RI, 2010.
  23. [23]J. C. Lagarias and A. Weiss, The 3x + 1 problem: two stochastic models, Ann. Appl. Probab. 2 (1992), 229–261.DOI
  24. [24]G. M. Leigh, A Markov process underlying the generalized Syracuse algorithm, Acta Arith. 46 (1986), 125–143.DOI
  25. [25]K. R. Matthews, Generalized 3x + 1 mappings: Markov chains and ergodic theory, The Ultimate Challenge: The 3x + 1 Problem (J. C. Lagarias, ed.), Amer. Math. Soc., Providence, RI, 2010.
  26. [26]K. R. Matthews and A. M. Watts, A generalization of Hasse’s generalization of the Syracuse algorithm, Acta Arith. 43 (1984), 167–175.DOI
  27. [27]T. Oliveira e Silva, Maximum excursion and stopping time record-holders for the 3x + 1 problem: computational results, Math. Comp. 68 (1999), 371–384.
  28. [28]Z. Shi, Branching random walks, Lecture Notes in Math., vol. 2151, Springer, 2015.
  29. [29]T. Tao, Almost all orbits of the Collatz map attain almost bounded values, Forum Math. Pi 10 (2022), e12.arxiv.org/abs/1909.03562
  30. [30]R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976), 241–252.DOI
  31. [31]G. J. Wirsching, The dynamical system generated by the 3x + 1 function, Lecture Notes in Math., vol. 1681, Springer, 1998.

Paper details

vlnc:W_2y863eby
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Claude Opus 5.5

View statement
Looking for related papers…
Contents