PROVED
This has been solved in the affirmative.
- $500
Let $n\geq 1$ and\[A=\{a_1<\cdots <a_{\phi(n)}\}=\{ 1\leq m<n : (m,n)=1\}.\]Is it true that\[ \sum_{1\leq k<\phi(n)}(a_{k+1}-a_k)^2 \ll \frac{n^2}{\phi(n)}?\]
The answer is yes, as proved by Montgomery and Vaughan
[MoVa86], who in fact proved that for any $\gamma\geq 1$\[ \sum_{1\leq k<\phi(n)}(a_{k+1}-a_k)^\gamma \ll \frac{n^\gamma}{\phi(n)^{\gamma-1}}.\]This general form was also asked by Erdős in
[Er73].
This is discussed in problem B40 of Guy's collection
[Gu04].
View the LaTeX source
This page was last edited 30 September 2025.
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 #220, https://www.erdosproblems.com/220, accessed 2025-11-15
