A Note on the Postage Stamp Problem

Amitabha Tripathi Department of Mathematics Indian Institute of Technology Hauz Khas New Delhi - 110016 India

                   atripath@maths.iitd.ac.in

Abstract Let h, k be fixed positive integers, and let A be any set of positive integers. Let hA := {a_{1} + a_{2} + ⋯ + a_{r} : a_{i} ∈ A, r ≤ 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, …, n} ⊆ hA. Let n(h, k) = max_{A} n(h, A), where the maximum is taken over all sets A with k elements. The purpose of this note is to determine n(h, A) when the elements of A are in arithmetic progression. In particular, we determine the value of n(h, 2).

1 Introduction

A set A = {a_{1} < a_{2} < ⋯ < a_{k}} is called an h-basis for a positive integer n if each of 1, 2, …, n is expressible as a sum of at most h (not necessarily distinct) elements of A. In order that A be an h-basis for n, it is necessary that a_{1} = 1. For fixed positive integers h and k, let n(h, k) denote the largest integer for which an h-basis of k elements exists. The problem of determining n(h, k) is apparently due to Rohrbach [1], and has been studied often. A large and extensive bibliography can be found in a paper of Alter and Barnett [2]. The Postage Stamp Problem derives its name from the situation where we require the largest integer n = n(h, k) such that all stamp values from 1 to n may be made up from a collection of k integer-valued stamp denominations with the restriction that an envelope that can have no more than h stamps, repetitions being allowed. An additional related problem is to determine all sets with k elements that form an h-basis for n(h, k). We call such a set an extremal h-basis.

It is easy to see that n(1, k) = k with unique extremal basis {1, 2, …, k} and that n(h, 1) = h with unique extremal basis {1}. The result n(h, 2) = ⌊(h^{2} + 6h + 1)/4⌋ with unique extremal basis {1, (h + 3)/2} for odd h and {1, (h + 2)/2} and {1, (h + 4)/2} for even h has been rediscovered several times, for instance by Stöhr [3, 4] and by Stanton, Bate and Mullin [5]. No other closed-form formula is known for any other pair (h, k) where one of h, k is fixed. In addition, n(h, k) is known for several pairs (h, k); see [2]. Asymptotic bounds for n(h, k) are due to Rohrbach [1], while bounds for n(h, 3) and n(2, k) are due to Hofmeister [6], and due to Rohrbach [1], Klotz [7], Moser [8] and others, respectively.

Let h, k be fixed positive integers, and let A be any set of positive integers. Let

hA := {a_{1} + a_{2} + ⋯ + a_{r} : a_{i} ∈ A, r ≤ 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, …, n} ⊆ hA. Thus n(h, k) = max_{A} n(h, A), where the maximum is taken over all sets A with k elements. The purpose of this note is to determine n(h, A) when the elements of A are in arithmetic progression. In particular, this easily gives the value of n(h, 2).

2 Main Result

Throughout this section, h, k, d are fixed positive integers. Let

A = {1, 1 + d, 1 + 2d, …, 1 + (k − 1)d}

be a k-term arithmetic progression. In order that n ∈ hA, it is necessary and sufficient that the equation

x_{0} + (1 + d)x_{1} + (1 + 2d)x_{2} + ⋯ + (1 + (k − 1)d)x_{k−1} = ∑_{i=0}^{k−1} x_{i} + (∑_{i=0}^{k−1} ix_{i}) d = n (1)

has a solution, with x_{i} ∈ ℕ ∪ 0 for all i and ∑_{i=0}^{k−1} x_{i} ≤ h.

Suppose x_{0}, x_{1}, …, x_{k−1} are nonnegative integers whose sum is at most a. Then x_{1} + 2x_{2} + ⋯ + (k − 1)x_{k−1} assumes all values 0, 1, …, (k − 1)a as the x_{i}’s range over nonnegative integers whose sum does not exceed a. Indeed, to achieve the sum q(k − 1) + r for 0 ≤ q < a and 0 ≤ r < k − 1 or for q = a, we may choose x_{k−1} = q, x_{r} = 0 or 1 according as r = 0 or r > 0, and all other x_{i} zero. We are now in a position to state our main result.

Theorem 1 Let h, k, d be positive integers. Then

n(h, \{1, 1 + d, 1 + 2d, …, 1 + (k − 1)d\}) = \{ \begin{matrix}h, & if h ≤ d − 1; \\ h + (k − 1)(h + 1 − d)d, & if h ≥ d. \end{matrix}

Proof. We write A = {1, 1 + d, 1 + 2d, …, 1 + (k − 1)d}. The case h ≤ d − 1 is easy to see. Henceforth, we assume h ≥ d. Suppose x_{0}, x_{1}, …, x_{k−1} are chosen such that the sum in (1) equals n = n(h, A). If ∑_{i=0}^{k−1} x_{i} < h, x_{0} may be incremented by 1 without violating the restriction on the sum of the x_{i}’s, thereby achieving the sum n(h, A)+1. Thus ∑_{i=0}^{k−1} x_{i} = h, so that n(h, A) ≡ h (mod d) by (1) and m := ∑_{i=0}^{k−1} ix_{i} ≤ (k − 1)h.

Now h + 1 + md ∈ hA if and only if (1) has a solution with ∑_{i=0}^{k−1} x_{i} = h + 1 − λd and ∑_{i=0}^{k−1} ix_{i} = m + λ for some λ ∈ ℕ. Such a simultaneous solution exists precisely when m+λ ≤ (h+1−λd)(k −1), that is, when m ≤ (h+1−λd)(k −1)−λ ≤ (h+1−d)(k −1)−1. Thus h + 1 + md ∉ hA for m ≥ (h + 1 − d)(k − 1), and n(h, A) ≤ h + (k − 1)(h + 1 − d)d.

It remains to show that every positive integer less than or equal to h+(k −1)(h+1−d)d is an element of hA. Any such integer N can be expressed as r + qd, where r, q satisfy the inequalities 1 ≤ r ≤ h and q ≤ (k − 1)r, as follows. We choose the largest r ≡ N (mod d) which is also less than or equal to h. Such an r is greater than or equal to h + 1 − d, so that qd = N − r ≤ N − (h + 1 − d) ≤ h + (h + 1 − d)((k − 1)d − 1) < ((k − 1)(h + 1 − d) + 1)d, and q ≤ (k − 1)(h + 1 − d) ≤ (k − 1)r. Thus ∑_{i=0}^{k−1} x_{i} = r and ∑_{i=0}^{k−1} ix_{i} = q is simultaneously solvable by the argument immediately preceding the Theorem. This completes the proof. □

Corollary 2 For h ≥ 1,

n(h, 2) = ⌊\frac{h^{2} + 6h + 1}{4}⌋ .

Moreover, the only extremal basis is {1, (h + 3)/2} if h is odd, and {1, (h + 2)/2} and {1, (h + 4)/2} if h is even.

Proof. From Theorem 1,

n(h, 2) = h + max_{d≥1} (h + 1 − d)d = h + ⌊\frac{(h + 1)^{2}}{4} ⌋ = ⌊\frac{h^{2} + 6h + 1}{4}⌋ .

It is easy to see that the maximum is achieved at d = (h + 1)/2, so that there is only one extremal basis if h is odd and two such bases if h is even. □

Remark. The function n(h, 2) is sequence A014616 in Sloane’s table [9].

3 Acknowledgments

The author is grateful to the referee for a careful reading and for numerous suggestions all of which have helped improve the presentation of this article.

References

[1] H. Rohrbach, Ein Beitrag zur additiven Zahlentheorie, Math. Z., 42, 1–30, 1937.

[2] R. Alter and J. A. Barnett, A postage stamp problem, Amer. Math. Monthly, 87, 206– 210, 1980.

[3] A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe, I, J. reine Angew. Math., 194, 40–65, 1955.

[4] A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe, II, J. reine Angew. Math., 194, 111–140, 1955.

[5] 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, 351–356, 1974.

[6] G. R. Hofmeister, Asymptotische Abschätzungen für dreielementige Extremalbasis in natürlichen Zahlen, J. reine Angew. Math., 232, 77–101, 1968.

[7] W. Klotz, Eine obere Schranke für die Reichweite einer Extremalbasis zweiter Ordnung, J. reine Angew. Math., 238, 161–168, 1969.

[8] L. Moser, On the representation of 1, 2, …, n by sums, Acta Arith., 6, 11–13, 1960.

[9] N. J. A. Sloane, The On-Line Encylopedia of Integer Sequences, 2005.

2000 Mathematics Subject Classification: Primary 11B13. Keywords: h-basis, extremal h-basis, arithmetic progression.

(Concerned with sequence \underline{A014616}.)

Received July 1 2005; revised version received December 15 2005. Published in Journal of Integer Sequences, December 15 2005.

Return to Journal of Integer Sequences home page.