Problem 413

Let $\omega(n)$ count the number of distinct primes dividing $n$ . Are there infinitely many $n$ such that, for all $m<n$ , we have $m+\omega(m) \leq n$ ?

Can one show that there exists an $\epsilon>0$ such that there are infinitely many $n$ where $m+\epsilon \omega(m)\leq n$ for all $m<n$ ?

Source: erdosproblems.com/413

Number theory
Iterated functions

Wiki page

Status

Open

No claim settles this problem.

Open: the site's label (page last edited 17 April 2026). Its commentary credits Lau [La26] with a positive answer to the second question and with a weaker version of the first. The partial claim page Lau 2026 records the result for the second question; the first question has no claim, so the derived standing stays open.

Er79: Erdős, Paul, Some unconventional problems in number theory. Math. Mag. (1979), 67-70.
Er79d: Erdős, P., Some unconventional problems in number theory. Acta Math. Acad. Sci. Hungar. (1979), 71-80.
ErGr80: Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
Gu04: Guy, Richard K., Unsolved problems in number theory, third edition, Problem Books in Mathematics, Springer (2004), xviii+437 pp.; B8 "Unitary aliquot sequences", p. 98: the Erdős--Selfridge barriers, $n$ with $m+f(m)\le n$ for all $m<n$ , the question whether $\omega(m)$ has infinitely many barriers, the list 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 17, 18, 20, 24, 26, 28, 30, ..., and the same question for $\Omega(m)$ with Selfridge's 99840 as the largest barrier below $10^5$ . Library home: Guy 2004.
La26: C. F. Lau, On the number of prime factors of consecutive integers. arXiv:2604.15042 (v1 16 April 2026, v2 24 June 2026); Theorem 1.3 and Corollary 1.4. Library home: Lau 2026.

Problem 413

Status

Proof claims

Discussion