×

The postage stamp problem and arithmetic in base \(r\). (English) Zbl 1174.11013

Summary: Let \(h,k\) be fixed positive integers, and let \(A\) be any set of positive integers. Let \(hA:=\{a_1+a_2+\cdots +a_r\: a_i \in A, r \leq h\}\) denote the set of all integers representable as a sum of no more than \(h\) elements of \(A\), and let \(n(h,A)\) denote the largest integer \(n\) such that \(\{1,2,\ldots ,n\} \subseteq hA\). Let \(n(h,k):=\max _A\:n(h,A)\), where the maximum is taken over all sets \(A\) with \(k\) elements. We determine \(n(h,A)\) when the elements of \(A\) are in geometric progression. In particular, this results in the evaluation of \(n(h,2)\) and yields surprisingly sharp lower bounds for \(n(h,k)\), particularly for \(k=3\).

MSC:

11B13 Additive bases, including sumsets
11D04 Linear Diophantine equations
PDF BibTeX XML Cite
Full Text: DOI EuDML

References:

[1] R. Alter and J. A. Barnett: A postage stamp problem. Amer. Math. Monthly 87 (1980), 206–210. · Zbl 0432.10032
[2] G. Hofmeister: Asymptotische Abschätzungen für dreielementige Extremalbasen in natürlichen Zahlen. J. reine angew. Math. 232 (1968), 77–101. · Zbl 0165.06201
[3] H. Rohrbach: Ein Beitrag zur additiven Zahlentheorie. Math. Z. 42 (1937), 1–30. · Zbl 0015.20002
[4] R. G. Stanton, J. A. Bate and R. C. Mullin: Some tables for the postage stamp problem. Congr. Numer., Proceedings of the Fourth Manitoba Conference on Numerical Mathematics, Winnipeg 12 (1974), 351–356. · Zbl 0361.05014
[5] A. Stöhr: Gelöste and ungelöste Fragen über Basen der natürlichen Zahlenreihe, I. J. reine Angew. Math. 194 (1955), 40–65. · Zbl 0066.03101
[6] A. Stöhr: Gelöste and ungelöste Fragen über Basen der natürlichen Zahlenreihe, II. J. reine Angew. Math. 194 (1955), 111–140. · Zbl 0066.03101
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.