SOLVED (LEAN)
This has been resolved in some other way than a proof or disproof, and that resolution verified in Lean.
Let $f(u)$ be the largest $v$ such that no $m\in (u,v)$ is composed entirely of primes dividing $uv$. Estimate $f(u)$.
An equivalent definition is that $v$ is the smallest number $>u$ such that all prime factors of $v$ are factors of $u$. In particular, we trivially have\[u+2\leq f(u)\leq u^2.\]Cambie has noted that when $u=p$ is a prime, $f(p)=p^2$, and if $u$ is even then $f(u)\leq 2^k$, where $2^k$ is the smallest power of $2$ which is $>u$. In particular, $f(u)=u+2$ whenever $u=2^k-2$ for $k\geq 2$.
In particular the function $f(u)$ does not exhibit any regular growth, since there are infinitely many $u$ such that $f(u)=u+2$ and infinitely many $u$ such that $f(u)=u^2$. Cambie can also show that $f(n)=(1+o(1))n$ for almost all $n$. It is not clear what kind of estimates Erdős and Graham had in mind. Since Cambie's observations seem to settle the most obvious questions, I will mark this as solved.
View the LaTeX source
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
BorisAlexeev
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Stijn Cambie
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #459, https://www.erdosproblems.com/459, accessed 2026-04-11
