Skip to content

Erdős problem 650

Let f(m)f(m) be such that if A{1,,N}A\subseteq \{1,\ldots,N\} has A=m\lvert A\rvert=m then every interval in [1,)[1,\infty) of length 2N2N contains f(m)\geq f(m) many distinct integers b1,,brb_1,\ldots,b_r where each bib_i is divisible by some aiAa_i\in A, where a1,,ara_1,\ldots,a_r are distinct.

Sources

Browse retained paths and inspect the exact material available for this Problem.

4 retained statements2415f78e850a

Open selected source

FormalConjectures/ErdosProblems/

650.lean

Retained formal statement1 of 4

Let f(m)f(m) be such that if A{1,,N}A\subseteq \{1,\ldots,N\} has A=m\lvert A\rvert=m then every interval in [1,)[1,\infty) of length 2N2N contains f(m)\geq f(m) many distinct integers b1,,brb_1,\ldots,b_r where each bib_i is divisible by some aiAa_i\in A, where a1,,ara_1,\ldots,a_r are distinct.

Estimate f(m)f(m).

GPT 5.4 Pro (prompted by He, Li, and Tang) proved f(m)2mf(m)\leq \lceil 2\sqrt{m}\rceil. A corresponding lower bound was given by GPT 5.4 Pro and Aristotle; it is now known (see the paper of van Doorn, Li, and Tang [VLT26]) that f(m)=min(m,2m)f(m) = \min(m, \lceil 2\sqrt{m}\rceil) for all mm.

FormalConjectures/ErdosProblems/650.leanErdos650.erdos_650.parts.i1 lineExact file
∀ (m : ℕ), Erdos650.f m = min m ⌈2 * √↑m⌉₊
SolvedStatement only, no proof

Search problems.science

Find a Problem, Result, source, or page