Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated

Problem 1135

../


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

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

Formulation. The site's wording on 2026-09-18 (page last edited 12 January 2026). The map ff is the shortcut form of the Collatz iteration, the "3x+13x+1 function" TT of Lagarias, in which the division by 22 that must follow every odd step is built in; the sources define it the same way (Hercher's Definition 1; Barina's 2025 display (1); Tao's Col2\mathrm{Col}_2). For the standard Collatz map C(n)=3n+1C(n)=3n+1 (nn odd), n/2n/2 (nn even), one has C(n)=f(n)C(n)=f(n) for even nn and C2(n)=f(n)C^2(n)=f(n) for odd nn, so the ff-orbit of mm is the CC-orbit with the even values 3n+13n+1 that follow odd terms omitted; since 11 is odd, the CC-orbit reaches 11 exactly when the ff-orbit does, and the two orbits have the same minimum (one authored line; Tao's paper states the equality of the minima on its p. 3). The question, whether every m≥1m\ge1 reaches 11 under iteration of ff (for m=1m=1, f(1)=2f(1)=2, f(2)=1f(2)=1, the trivial cycle {1,2}\{1,2\}), is the Collatz conjecture. It is not Erdős's problem: the site includes it to record the history of the link between Erdős and the problem, and asks that comments stay at that intersection; this page does the same.

Status. 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 2712^{71} reaches 11 (Barina, J. Supercomput. 81 (2025), refereed); no nontrivial cycle of ff has at most 9191 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 X0.84X^{0.84} of the integers up to XX reach 11 (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).

Source. erdosproblems.com/1135, accessed 2026-09-18: the problem page (OPEN, with the site's note that no finite computation can settle it; a prize; last edited 12 January 2026; source keys [La85], [Er97e, p. 537], [La16]; commentary citing [La10], [La16], [La85], [Gu04] and Problem 1134; OEIS A006370 and A008908 linked; a formalized statement; the page thanks Lagarias and one other contributor), its four-comment discussion thread (11 January to 16 July 2026) and its empty proof-claims tab. Cite as: T. F. Bloom, Erdős Problem #1135, https://www.erdosproblems.com/1135, accessed 2026-09-18.

References.

  • [La85] Lagarias, Jeffrey C., The 3x+13x+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_3x1_problem_generalizations.
  • [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+13x+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+13x+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 TT, the page's ff, and the problem's history; the paper does not mention the Erdős prize figure. Library home: lagarias_2016_erdos_klarner_3x1_problem; 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+13x+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_unsolved_problems_number_theory.
  • [La10] Lagarias, Jeffrey C., The 3x+13x+1 problem: an overview. In The Ultimate Challenge: The 3x+13x+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_problem_overview.
  • [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_almost_all_orbits.
  • [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_convergence_verification.
  • [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_improved_verification_limit_convergence_collatz.
  • [He23] Hercher, C., There are no Collatz mm-cycles with m≤91m\le91. J. Integer Seq. 26 (2023), Article 23.3.5; arXiv:2201.00406v3 (4 April 2023). Theorem 23, p. 15. Library home: hercher_2023_no_mcycles_91.
  • [KrLa03] Krasikov, I. and Lagarias, J. C., Bounds for the 3x+13x+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 aa not divisible by 33 and all large enough xx, at least x0.84x^{0.84} of the integers below xx have aa in their forward orbit (a=1a=1 gives (W5)); its Theorem 6.1 (arXiv v1 p. 16) states πa(x)≥x0.84\pi_a(x)\ge x^{0.84} for x≥x0(a)x\ge x_0(a) and every positive a≢0(mod3)a\not\equiv0\pmod3, by a computer-aided proof (theorem_6_1). Library home: krasikov_lagarias_2003_bounds_difference_inequalities.
  • [SdW05] Simons, J. and de Weger, B., Theoretical and computational bounds for mm-cycles of the 3n+13n+1 problem. Acta Arith. 117 (2005), no. 1, 51--70, doi:10.4064/aa117-1-3, which excludes nontrivial mm-cycles for m≤68m\le68 (p. 54); the library card describes the authors' updated version 1.44 (31 August 2010) (library home: simons_de_weger_2010_mcycles_bounds); the exclusion for m≤75m\le75 and the bounds on KK are that version's Theorem 3 (p. 5) (theorem_3), which [He23] cites as its [12].
  • [OEIS] Sequences A006370 (the Collatz map) and A008908 (steps to reach 11), The On-Line Encyclopedia of Integer Sequences, JSON records accessed; A006370 cites [Gu04] E16, the Lagarias volume and [KrLa03].

Formalization. Statement only. The file ErdosProblems/1135.lean of formal-conjectures at the commit linked (main) declares theorem erdos_1135 : type_of% CollatzConjecture.collatz_conjecture under category research open, AMS 11 37, with proof sorry, pointing to the collection's FormalConjectures/Wikipedia/CollatzConjecture.lean (at the same commit), which defines collatzStep n = if Even n then n / 2 else 3 * n + 1 and states collatz_conjecture (n : ℕ) (hn : n > 0) : ∃ m, collatzStep^[m] n = 1 (research open, sorry): the standard map, whose question is equivalent to the page's by the map remark above. The community database (teorth/erdosproblems) lists the problem as open as of its last update on 11 January 2026, the statement as formalized as of that field's last update on 13 January 2026, no formal proof, a prize and the comment "Collatz conjecture". The corpus has not built the files.

Current assessment

The question (site formulation of 2026-09-18). The statement above; OPEN; a prize; last edited 12 January 2026. The commentary, in summary: the problem is the Collatz conjecture, for whose history and theory the site refers to Lagarias's overview [La10]; it is not Erdős's problem but was devised by Collatz before 1952; Erdős called it hopeless on several occasions; as Lagarias [La16] notes, the nearest Erdős came to such problems is the theorem in the remarks to Problem 1134; the often-repeated claim that Erdős offered a prize for a solution goes back to Lagarias's 1985 survey [La85], with the prize story summarized in the Status; and the problem is E16 of Guy's collection [Gu04], where Guy quotes Erdős as saying that mathematics may not be ready for such problems. The thread: two moderation notices of 11 January 2026 (the site's comment policy on AI-written and long formal-proof comments, and the request that comments stay at the intersection of Erdős and Collatz, since the problem needs no further publicity from the site), a historical comment of 12 January 2026 (Erdős and Collatz both attended the 1950 International Congress at Harvard; a group photograph), and a third-party notice of 16 July 2026 (a company's prize for a proof, with a 2031 deadline); none is a mathematical source. The proof-claims tab is empty. The community database record, lists the problem as open as of its last update on 11 January 2026.

The Erdős connection (the account this page keeps). Lagarias's 2010 survey prints: "We also note that Paul Erdős said, in conversation, about its difficulty ([25]): 'Hopeless. Absolutely hopeless.' In Erdős-speak, this means that there are no known methods of approach which gave any promise of solving the problem" (p. 23; [25] is "P. Erdős, Private communication with J. C. Lagarias"), and "To quote a still valid dictum of Paul Erdős ([58, p. 3]) on the problem: 'Mathematics is not yet ready for such problems'" (p. 14; [58] is [La85]), which the site quotes from Guy's E16 as "Mathematics may not be ready for such problems". The 1985 survey's p. 3 prints the 2010 wording: "Paul Erdős commented concerning the intractability of the 3x+13x+1 problem: 'Mathematics is not yet ready for such problems.'", with no occasion, date or source given (the passage). Guy's E16 [Gu04], printed p. 330, prints the site's wording, "Erdős has said that 'Mathematics may not be ready for such problems'", with no source, date or occasion, and sends the reader to the 1985 survey; so the two wordings are Guy's and Lagarias's, and neither book nor survey says where Erdős said it. The prize figure is the site's account of Lagarias's communication; the 1985 survey's p. 4 prints it as one of three prizes "offered", "$50 by H. S. M. Coxeter in 1970, then $500 by Paul Erdős, and more recently £1000 by B. Thwaites [69]", sourcing Coxeter's figure to Trigg (its reference [27]) and Thwaites's to [69] and giving none for Erdős's, so the 1983 conversation the site reports is not in the paper and rests on the site alone. [La16], p. 775, prints a third account of the remark: Erdős "did not publish any result on the 3x+13x+1 problem, which he characterized in conversation as 'hopeless'", again with no date or occasion, and the paper says nothing of the Erdős prize figure or of a 1983 conversation with Graham (Graham is named on p. 775 only as coauthor of two cited works). What the site's third key, [Er97e, p. 537], says about the problem is not checked. The Klarner connection (survey, p. 4): Klarner's 1971 interaction with Erdős at Reading led to "a (solved) Erdős prize problem" on the density of the smallest set containing 11 and closed under x↦2x+1x\mapsto2x+1, 3x+13x+1, 6x+16x+1, proved of density zero by Crampin and Hilton ("The solvers collected £10 from Erdős"), with Klarner's revised problem still open; [La16] tells the story at length (pp. 755--768): Erdős's 1972 bound on orbit sizes (its Theorem 3), the prize problem it led him to pose, and Crampin and Hilton's unpublished negative answer, reconstructed as its Theorem 6. That circle of questions is the site's Problem 1134, and the theorem [La16] means, "the closest he ever came to working on problems like the 3x+13x+1 problem" (p. 775), is the orbit bound.

The frontier (six statements; the map is the page's ff in every source). Verification: Barina's 2020 statement (postprint pp. 6--7): "From September 2019 to May 2020, the project managed to verify this conjecture for all numbers below 2682^{68}", superseded by the 2025 result (p. 12): "we have managed to verify the convergence of the Collatz conjecture for all numbers up to the limit of 2712^{71} (which is equal to 2 048×2602\,048\times2^{60})", the 2712^{71} milestone dated 15 January 2025 in the paper's Table 10; both are computations the corpus has not rerun, and the site's label says that no finite computation can settle the problem. Cycles: Hercher's Theorem 23 (p. 15): "There is no mm-cycle with m≤91m\le91", an mm-cycle being a nontrivial cycle of ff with mm local minima, proved by iterating continued-fraction lower bounds on the number of odd members against the Simons--de Weger upper bound, using the verification bound 704⋅260704\cdot2^{60}; Simons and de Weger's m≤75m\le75 is their Theorem 3 (p. 5) in their 2010 version 1.44 (the 2005 Acta Arith. version has m≤68m\le68), and Eliahou's 2010-era period bound 10,439,860,59110{,}439{,}860{,}591 is reported in Lagarias's (W2). Almost all orbits: Tao's Theorem 1.3 (p. 3): for any F:N+1→RF:\mathbb N+1\to\mathbb R with F(N)→∞F(N)\to\infty, Colmin⁡(N)<F(N)\mathrm{Col}_{\min}(N)<F(N) for almost all NN in logarithmic density ("Thus for instance one has Colmin⁡(N)<log⁡log⁡log⁡log⁡N\mathrm{Col}_{\min}(N)<\log\log\log\log N for almost all NN"), stated for the standard map and carried to ff by the paper's own remark that the orbit minima coincide; Remark 1.4 there says that a bounded constant in place of F(N)F(N) "is likely to be almost as hard to settle as the full Collatz conjecture". Density: the count of n≤Xn\le X that reach 11 is at least X0.84X^{0.84} for all large XX (Krasikov and Lagarias, reported as (W5) of Lagarias's Section 6 and in Tao's introduction; the paper's abstract agrees, and its Theorem 6.1 (arXiv v1 p. 16; theorem_6_1) states πa(x)≥x0.84\pi_a(x)\ge x^{0.84} for x≥x0(a)x\ge x_0(a) and every positive a≢0(mod3)a\not\equiv0\pmod3, by a computer-aided proof). Lagarias's Section 6 (pp. 14--15) is the 2010 baseline for all of these: (W1) verification below 20×25820\times2^{58}, (W2) Eliahou's cycle bounds, (W3) infinitely many nn needing at least 6.143log⁡n6.143\log n steps (Applegate and Lagarias), (W4) Roosendaal's record, (W5) the density bound. Hercher's Remark 3 names the two ways the conjecture could fail, an unbounded trajectory or a nontrivial cycle; the results above bound the second for cycles of a given shape and say nothing about the first. The six statements are checked against their theorems, not their proofs (Tao's 58 pages included); no computation is rerun, and none of them is independently reviewed.

Proof claims (leads with provenance, not status). The site's tab is empty and its commentary reports no claim. The arXiv listing (the search below) carries unrefereed manuscripts whose titles claim a proof of the conjecture (among the newest: arXiv:2309.09991, arXiv:2402.00001, arXiv:2502.20642, the last applying a fixed-point theorem), recorded from their titles or abstracts only, with no acceptance evidence found; an algorithm preprint (arXiv:2602.10466, February 2026) proposes a faster check for the next verification exponent and reports no new bound. Following the site's request, none of these is pursued on this page.

Search scope. None of the routes below found a proof, disproof or accepted resolution, or a verification or cycle bound beyond those above.

  • The site: problem page, discussion thread and proof-claims tab; the formal-conjectures file and the Collatz module it points to at the pinned commit; the community database as fetched 2026-09-18.
  • The primary sources, at these pages: [La10] pp. 1, 4, 14--15 and 23; [Ta22] pp. 1--3; [Ba21] pp. 1 and 6--7; [Ba25] pp. 1--3 and 12--13; [He23] pp. 1--3 and 15--16; [KrLa03] and [SdW05] p. 1; [La85] and [La16] whole, with pp. 3--4 and 21--23 of the first and pp. 753, 756, 759, 761, 766--767, 771--772 and 775 of the second relied on.
  • arXiv: the API records of 2111.02635, 1909.03562, 2201.00406 and math/0205002 (versions and journal references); the searches abs:Collatz AND (abs:proof OR abs:conjecture) (157 records) and ti:Collatz (198 records), each sorted by submission date with the 40 newest scanned by title.
  • Crossref: the records of [Ta22], [Ba21] and [Ba25]; a bibliographic query for [He23] (no record; the journal issues no DOIs).
  • OEIS A006370 and A008908 (the JSON records).

Not searched: MathSciNet, zbMATH, Google Scholar, X, and the verification project's live web page (a dynamic page, not a citable record). Not checked against the source: [Er97e], Eliahou 1993, Oliveira e Silva 2010, Applegate and Lagarias 2003.

Remaining gaps. (1) The Erdős connection is second-hand beyond [La85] and [La16]: the 1985 survey prints the Erdős prize figure and the dictum, and Guy's E16 the dictum, without a source; [La16] prints the "hopeless" remark as said in conversation, again without a date or occasion, and does not mention that figure; and [Er97e] is not checked, so the 1983 conversation behind the figure, the "hopeless" remark's occasions and Erdős's own 1997 words rest on the site and on Lagarias's 2010 survey. Reopening condition: a check of [Er97e]. (2) The conjecture is open; finite verification and cycle exclusion cannot settle it, and the almost-all theorem decides no single value. (3) Proof coverage: the six statements are checked against their theorems, not their proofs; no computation is rerun. (4) The arXiv proof claims are unchecked and unreviewed. (5) The Lean statement is the standard map's; the bridge to the page's ff is the one-line map remark. (6) The sixteen other library cards the page links (surveys, bibliographies, stochastic models, cycle and density papers) have no result pages.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.