Problem 709

Let $f(n)$ be minimal such that, for any $A=\{a_1,\ldots,a_n\}\subseteq [2,\infty)\cap\mathbb{N}$ of size $n$ , in any interval $I$ of $f(n)\max(A)$ consecutive integers there exist distinct $x_1,\ldots,x_n\in I$ such that $a_i\mid x_i$ .

Obtain good bounds for $f(n)$ , or even an asymptotic formula.

Source: erdosproblems.com/709

Number theory

Wiki page

Status

Open

No claim settles this problem.

Open. No asymptotic formula, and no bounds beyond those below, were found in the search whose scope the Current assessment records. What is known: $c(\log n)^\alpha<f(n)<c'\sqrt n$ (Erdős and Surányi 1959, Sections 10--12; the site writes $(\log n)^c\ll f(n)\ll n^{1/2}$ ), and the bound $f(n)\gg\log n/\log\log n$ , which the site's commentary derives from van Doorn's 2026 theorem on Problem 711 and the thread's summary of 15 March 2026 obtains by restricting to the set $\{2,\ldots,n+1\}$ . A forum comment of 14 September 2026 reports a further lower bound $f(n)\ge\exp((\tfrac{\log2}2-o(1))\log n/\log\log n)$ from a July 2026 preprint, and an unreviewed claim, attributed by the commenter to GPT Astra, of an upper bound $n^{1/3+o(1)}$ ; both are leads. This is a bounded negative finding, not a certificate of openness.

ErSu59: Erdős, P. and Surányi, J., Megjegyzések egy versenyfeladathoz (Bemerkungen zu einer Aufgabe eines mathematischen Wettbewerbs). Mat. Lapok 10 (1959), 39--48; Sections 10--12, printed pp. 45--47, and the German summary, p. 48. Library home: Erdős and Surányi 1959; result pages Section 10, Section 11 and Section 12.
Er92c: Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. 15 (1992), 34--50, DOI 10.46298/hrj.1992.125; Section 1, display (2), printed p. 35. Library home: Erdős 1992; result page Section 1.
vD26: van Doorn, W., On the length of an interval that contains distinct multiples of the first $n$ positive integers. Integers 26 (2026), #A7 (published 5 January 2026; DOI 10.5281/zenodo.18154085; also arXiv:2601.16972v1); Theorem 1, p. 1. Library home: Doorn 2026; result page Theorem 1.
ErPo80: Erdős, P. and Pomerance, C., Matching the natural numbers up to $n$ with distinct multiples in another interval. Indag. Math. (Proc.) 83 (1980), no. 2, 147--161, DOI 10.1016/1385-7258(80)90018-9; cited by the thread, not by the site's page. Library home: Erdős 1980; result page Theorem 2.
ChKo26: Chen, K. and Korsky, S., Improved bounds for distinct multiples in intervals. arXiv:2607.26450 (v1 29 July 2026, v2 13 August 2026; no journal reference). Not held; known here from its arXiv abstract only; cited from the thread as a lead.

Problem 709

Status

Proof claims

Discussion