4. The number of the non-representable numbers

Both representable and non-representable numbers occur up to the
greatest non-representable number, so it is a natural question, what is the exact number of these. Already SYLVESTER studied and solved this problem for two coins [30]. The Norwegian mathematician, SELMER showed that $N(a_1, a_2, \ldots , a_n)$ can be computed in all cases, when we know the greatest non-representable number in the every residue class mod $a_1$ [28]. Let $H$ be a complete residue system mod $a_1.$ To every $h \in H$ there exists an $r_h \equiv h \pmod {a_1}$, which is representable as $r_h=a_2y_2 + a_3y_3 + \ldots + a_ny_n$ and is the minimal with this property. Then by this notation:

4.1.2. THEOREM

$$N(a_1, a_2, \ldots ,a_n)=\frac {1}{a_1} \sum_{h \in H} {r_h} -\frac {a_1-1}{2}.$$

We present several examples in Chapter 2 for the practical application of this method, and we use the same idea also at the summation of the non-representable numbers in Chapter 5.

We give a short survey about the special results and estimates related to $N(A)$. About the relation of the two functions we have:

$$\frac{G(a_1, a_2, \ldots , a_n)+1}{2} \le N(a_1, a_2, \ldots , a_n) \le G(a_1, a_2, \ldots , a_n),$$

and these inequalities cannot be improved.

As the main result of this chapter we prove that the extremal number $\nu(n, t)$ is obtained when we choose the $n$ largest integers not exceeding $t$ [17]. This was a conjecture by ERDŐS and GRAHAM from 1980 [7, p.86].

THEOREM 4.2.1. Let $n$ and $t$ be positive integers, $1 < n \le t.$ Then

$$\nu(n,t)=N(t-n+1,t-n+2, \dots , t).$$

We also prove that for infinitely many values of $n$ and $t$, the extremal value $\nu(n, t)$ is achieved also for another set $A$ differing from the set of the greatest $n$ numbers up to $t$.

THEOREM 4.2.4. Let $d, n, k$ be integers such that  $2 \le d < n,$ $0 \le k < n-d.$ If $n-k \equiv 0 \pmod {d+1}$ or $n-k\ \equiv -1 \pmod {d+1}$ then for $t=dn+k$ there exist at least two optimal sets $A$, i.e. for which

$$N(A)=\nu(n,dn+k).$$

It is an interesting duality, that for these values of $n$ and $t$, the value $G(a_1, a_2, \ldots , a_n)$ will be smaller in general than $g(n, t)$, when we choose the $a_i$ as adjacent numbers according to the original conjecture, yet we get the most non-representable numbers. The number of the non-representable numbers, however, will be just the same also for the set giving the maximal $G(A)$.

We do not know, whether there exists at least another optimal set for every $t$ besides the construction of the adjacent elements, and whether there exist other types of optimal sets differing from the above-mentioned ones.