Problem Statement
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}?\]
Categories:
Number Theory
Progress
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$.
Source: erdosproblems.com/433 | Last verified: January 15, 2026