The board / number theory / #538
Erdős Problem #538
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 representations `m = p * a` with `p` prime and `a ∈ A`.
`A ⊆ {1, …, N}` and every `m` has at most `r` representations `m = p a`.
The reciprocal sum `∑_{n ∈ A} 1/n` of the problem.
Let \(r\geq 2\) and suppose that \(A\subseteq\{1,\ldots,N\}\) is such that, for any \(m\), there are at most \(r\) solutions to \(m=pa\) where \(p\) is prime and \(a\in A\). Give the best possible upper bound for \(\sum_{n\in A}\frac{1}{n}\). Erdős observed that \(\sum_{n\in A}\frac{1}{n}\ll r\frac{\log N}{\log\log N}\), and the order `Θ_r(log N / loglog N)` is known (see `erdos_538.matching_order`). The best possible upper bound is the asymptotic size of the largest reciprocal sum `maxMass r N` over admissible `A`.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research open · 1 further variant / known partial result in the Lean file. The authoritative wording is on erdosproblems.com/538.Prizenone
Topicsnumber theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/538
Attempts
submit one →Read our working report →
modulo Bertrand's postulate and Mertens' prime-reciprocal theorem, \(M_r(N)\asymp\log N\min\{1,r/\log\log N\}\) uniformly for \(r\ge2\); exact finite bounds, a cap-two construction, a cold Lean audit,
PROVED