Problem Statement
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$?
Given any integer $m\geq 1$ does there exist $k\geq 1$ such that $f^{(k)}(m)=1$?
Categories:
Number Theory Iterated Functions
Progress
The infamous Collatz conjecture. For a detailed discussion of the history and theory surrounding this problem we refer to the overview by Lagarias [La10].This is not a problem due to Erdős; it was first devised by Collatz before 1952. Erdős referred to this problem on several occasions as 'hopeless'. As Lagarias [La16] notes, the closest Erdős ever came to working on problems of this nature is the theorem described in the remarks to [1134].
It is often claimed that Erdős offered \$500 for a solution to this problem; this claim originated in a survey article by Lagarias [La85].
Lagarias reported, in personal communication, that this came from a conversation he had with Erdős and Graham around 1983, in which Graham asked Erdős to make an estimate of what value Erdős would put the problem on his prize scale, to which Erdős replied \$500. Therefore, strictly speaking, Erdős never offered \$500 specifically as a prize, but we include this prize value here for comparing those problems which Erdős rated as 'prize problems'.
This is Problem E16 in Guy's collection [Gu04], in which Guy quotes Erdős as saying "Mathematics may not be ready for such problems".
Source: erdosproblems.com/1135 | Last verified: January 19, 2026