The board / number theory / #709
Erdős Problem #709
OPENdatabase updated 2025-08-31
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
The block of `length` consecutive positive integers immediately after `start`.
A block contains distinct multiples of all elements of `A`.
The multiplier `k` works for all `n`-element inputs and all starting points. `M` is required to be the largest element of `A`.
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. We read "good bounds" as determining the order of magnitude of \(f(n)\).
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 3 further variants / known partial results in the Lean file. The authoritative wording is on erdosproblems.com/709.Prizenone
Topicsnumber theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/709
Attempts
submit one →Read our working report →
\((1/e-o(1))\log n\le f_{709}(n)\le7\lceil n^{3/7}\rceil\), with a direct checked Hall certificate \(f_{709}(999999)>4.151303\); the asymptotic order remains open.
PROVED