Problem 1135

Define $f:\mathbb{N}\to \mathbb{N}$ by $f(n)=n/2$ if $n$ is even and $f(n)=\frac{3n+1}{2}$ if $n$ is odd.

Given any integer $m\geq 1$ does there exist $k\geq 1$ such that $f^{(k)}(m)=1$ ?

Number theory
Iterated functions

Wiki page

Status

Open

No claim settles this problem.

The site labels the problem OPEN (page last edited 12 January 2026, label accessed 2026-09-18). No proof, disproof or accepted resolution was found in the search whose scope the Current assessment records; the formal-conjectures file is research open, and the sources cited here prove partial results only: every starting value below $2^{71}$ reaches $1$ (Barina, J. Supercomput. 81 (2025), refereed); no nontrivial cycle of $f$ has at most $91$ local minima (Hercher, J. Integer Seq. 26 (2023), refereed); almost all orbits attain almost bounded values in logarithmic density (Tao, Forum Math. Pi 10 (2022), refereed); and at least $X^{0.84}$ of the integers up to $X$ reach $1$ (Krasikov and Lagarias, Acta Arith. 109 (2003), reported by Lagarias's survey and Tao's introduction). Unrefereed manuscripts claiming proofs exist on the arXiv listing and are recorded below as leads only. This is a bounded negative finding, not a certificate of openness. The site lists a prize with its own caveat: the figure comes from Lagarias's 1985 survey [La85], and Lagarias, in a personal communication the site reports, traced it to a conversation around 1983 in which Graham asked where Erdős would put the problem on the Erdős prize scale, and Erdős named a sum; so, the site says, Erdős never offered the sum as a prize, and the figure is listed only to place the problem on that scale beside the problems Erdős did rate. The 1985 survey's p. 4 lists Erdős's figure among three prizes offered for a solution, beside Coxeter's of 1970 and a later one of Thwaites, with no source, date or occasion for the Erdős figure (the passage).

La85: Lagarias, Jeffrey C., The $3x+1$ problem and its generalizations. Amer. Math. Monthly 92 (1985), no. 1, 3--23, doi:10.2307/2322189. The passages relied on are pp. 3--4 (the Erdős dictum and the prize sentence) and its references [27], [36] and [69] on pp. 21--23. The origin of the Erdős prize figure per the site, and the source of the Erdős dictum Lagarias's 2010 survey quotes from its p. 3. Library home: Lagarias 1985.
Er97e: Erdős, Paul, Some of my favourite unsolved problems. Math. Japon. 46 (1997), 527--537; the site cites p. 537. What p. 537 says about this problem is not checked.
La16: Lagarias, Jeffrey C., Erdős, Klarner, and the $3x+1$ problem. Amer. Math. Monthly 123 (2016), no. 8, 753--776, doi:10.4169/amer.math.monthly.123.08.753 as printed (JSTOR's stable identifier is 10.4169/amer.math.monthly.123.8.753). The closing paragraph, printed p. 775, is the site's source for the remark that the closest Erdős came to such problems is the theorem on Problem 1134: Erdős published no result on the $3x+1$ problem, called it "hopeless" in conversation, and his orbit-size bound (Theorem 3, p. 759) seems to be the closest he came. Section 10 (pp. 772--775) gives the map $T$ , the page's $f$ , and the problem's history; the paper does not mention the Erdős prize figure. Library home: Lagarias 2016; the theorem is paged as Theorem 3.
Gu04: Guy, Richard K., Unsolved problems in number theory. Third edition, Problem Books in Mathematics, Springer (2004), xviii+437 pp. Section E16 "The $3x+1$ problem", printed p. 330: the Collatz sequence and the cycle 4, 2, 1, then "Erdős has said that 'Mathematics may not be ready for such problems.' Do not attempt it without first reading Jeff Lagarias's 1985 article", with no source, date or occasion for the remark. Library home: Guy 2004.
La10: Lagarias, Jeffrey C., The $3x+1$ problem: an overview. In The Ultimate Challenge: The $3x+1$ Problem, AMS (2010), 3--29; cited as arXiv:2111.02635v1 (4 November 2021), whose pagination is used here. Section 6, pp. 14--15; the Klarner passage, p. 4; the "hopeless" quotation, p. 23. Library home: Lagarias 2010.
Ta22: Tao, T., Almost all orbits of the Collatz map attain almost bounded values. Forum Math. Pi 10 (2022), e12, 56 pp., doi:10.1017/fmp.2022.8 (Crossref record accessed); arXiv:1909.03562v7 (16 July 2026). Theorem 1.3 and the map remark, p. 3. Library home: Tao 2019.
Ba21: Barina, D., Convergence verification of the Collatz problem. J. Supercomput. 77 (2021), no. 3, 2681--2688, doi:10.1007/s11227-020-03368-x (Crossref record accessed; online 1 July 2020); the pages cited are the author's postprint's. The verification statement, pp. 6--7. Library home: Barina 2020.
Ba25: Barina, D., Improved verification limit for the convergence of the Collatz conjecture. J. Supercomput. 81 (2025), no. 7, Article 810, doi:10.1007/s11227-025-07337-0 (accepted 21 April 2025; Crossref record accessed). Section 6 and Table 10, p. 12. Library home: Barina 2025.
He23: Hercher, C., There are no Collatz $m$ -cycles with $m\le91$ . J. Integer Seq. 26 (2023), Article 23.3.5; arXiv:2201.00406v3 (4 April 2023). Theorem 23, p. 15. Library home: Hercher 2023.
KrLa03: Krasikov, I. and Lagarias, J. C., Bounds for the $3x+1$ problem using difference inequalities. Acta Arith. 109 (2003), no. 3, 237--258, doi:10.4064/aa109-3-4; arXiv:math/0205002v1. Its abstract states that for each fixed positive integer $a$ not divisible by $3$ and all large enough $x$ , at least $x^{0.84}$ of the integers below $x$ have $a$ in their forward orbit ( $a=1$ gives (W5)); its Theorem 6.1 (arXiv v1 p. 16) states $\pi_a(x)\ge x^{0.84}$ for $x\ge x_0(a)$ and every positive $a\not\equiv0\pmod3$ , by a computer-aided proof (Krasikov and Lagarias 2003, Theorem 6.1 (p. 16)). Library home: Krasikov and Lagarias 2003.
SdW05: Simons, J. and de Weger, B., Theoretical and computational bounds for $m$ -cycles of the $3n+1$ problem. Acta Arith. 117 (2005), no. 1, 51--70, doi:10.4064/aa117-1-3, which excludes nontrivial $m$ -cycles for $m\le68$ (p. 54); the library card describes the authors' updated version 1.44 (31 August 2010) (library home: Simons and de Weger 2010); the exclusion for $m\le75$ and the bounds on $K$ are that version's Theorem 3 (p. 5) (Simons and de Weger 2010, Theorem 3, Main Theorem (p. 5)), which [He23] cites as its [12].
OEIS: Sequences A006370 (the Collatz map) and A008908 (steps to reach $1$ ), The On-Line Encyclopedia of Integer Sequences, JSON records accessed; A006370 cites [Gu04] E16, the Lagarias volume and [KrLa03].

Problem 1135

Status

Proof claims

Discussion