×

On the postage stamp problem with three stamp denominations. (English) Zbl 0436.10027

In the “postage stamp problem”, one considers an integral basis \(A_k\) of elements \(1 = a_1 < a_2 < \cdots < a_k\), and studies representations \(\sum x_ia_i\), \(x_i\ge 0\), where the number \(\sum x_i\) of addends does not exceed a certain integer \(h\) (the “size of the envelope”). The \(h\)-range \(n_h(A_k)\) is the largest integer \(M\) for which all natural numbers \(\le M\) have such representations. The “global” stamp problem, for given \(h\) and \(k\), consists in determining the maximal value of \(n_h(A_k)\) over all bases \(A_k\). The “local” problem, for given \(h\) and \(A_k\), consists in determining \(n_h(A_k)\), by an algorithm or preferably by an explicit formula. The solutions to these problems are trivial only for \(k=2\). For \(k=3\), the global problem was solved by G. Hofmeister in 1968 [J. Reine Angew. Math. 232, 77–101 (1968; Zbl 0165.06201)], and an algorithm for the local problem has recently been given by Rödseth, utilizing a connection (discovered by G. Meures [Zusammenhang zwischen Reichweite und Frobeniuszahl, Staatsexamensarbeit, Mainz (1977)] between the postage stamp problem and the “coin exchange problem” of Frobenius. Using Rödseth’s algorithm [Ø. Rødseth, J. Reine Angew. Math. 301, 171–178 (1978; Zbl 0374.10011)], the author gives explicit formulas for \(n_h(A_3)\) under conditions which cover (asymptotically) 99% of all bases \(A_3\).

MSC:

11B13 Additive bases, including sumsets
11D07 The Frobenius problem
PDFBibTeX XMLCite
Full Text: DOI EuDML