PROVED
This has been solved in the affirmative.
If $A\subset \mathbb{N}$ is a finite set then let $G(A)$ denote the greatest integer which is not expressible as a finite sum of elements from $A$ (with repetitions allowed). Let\[g(k,n)=\max G(A)\]where the maximum is taken over all $A\subseteq \{1,\ldots,n\}$ of size $\lvert A\rvert=k$ which has no common divisor. Is it true that\[g(k,n)\sim \frac{n^2}{k-1}?\]
This type of problem is associated with Frobenius (see also
[434]). Erdős and Graham
[ErGr72] proved $g(k,n)<2n^2/k$, and there are examples which show that\[g(k,n) \geq \frac{n^2}{k-1}-5n\]for $k\geq 2$.
The problem is written as Erdős and Graham describe it, but presumably they had in mind the regime where $k$ is fixed and $n\to \infty$.
This is true, and was proved by Dixmier
[Di90], who proved that in fact, for all $2\leq k<n$,\[\left\lfloor\frac{n-2}{k-1}\right\rfloor(n-k+1)-1\leq g(k,n) \leq \left(\left\lfloor\frac{n-1}{k-1}\right\rfloor-1\right)n-1,\]and determined $g(k,n)$ exactly when $k-1$ divides any of $n,n-1,n-2$.
View the LaTeX source
This page was last edited 31 October 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 #433, https://www.erdosproblems.com/433, accessed 2026-01-16
