TOPICS
Search

Postage Stamp Problem


Consider a set A_n={a_1,a_2,...,a_n} of n positive integer-denomination postage stamps sorted such that 1=a_1<a_2<...<a_n. Suppose they are to be used on an envelope with room for no more than h stamps. The postage stamp problem then consists of determining the smallest integer N_h(A_n) which cannot be represented by a linear combination sum_(i=1)^(n)x_ia_i with x_i>=0 and sum_(i=1)^(n)x_i<h.

Without the latter restriction, this problem is known as the Frobenius problem or Frobenius postage stamp problem.

The number of consecutive possible postage amounts is given by

 n_h(A_n)=N_h(A_n)-1,
(1)

where n_h(A_n) is called an h-range.

Exact solutions exist for arbitrary A_n for n=2 and 3. The n=2 solution is

 n_h(A_2)=(h+3-a_2)a_2-2
(2)

for h>=a_2-2. It is also known that

 n_h(2)=|_1/4(h^2+6h+1)_|,
(3)

(Stöhr 1955, Guy 1994), where |_x_| is the floor function, the first few values of which are 2, 4, 7, 10, 14, 18, 23, 28, 34, 40, ... (OEIS A014616; Guy 1994, p. 123).

Hofmeister (1968, 1983) showed that for h>=20,

 n_h(3)=4/3(1/3h)^3+6(1/3h)^2+Ah+B,
(4)

where A and B are functions of h (mod 9), and Mossige (1981, 1987) showed that

 n_h(4)>=2.008(1/4h)^4+O(h^3)
(5)

(Guy 1994, p. 123).

Shallit (2002) proved that the (local) postage stamp problem is NP-hard under Turing reductions, but can be solved in polynomial time if k is fixed.

A related problem asks for the largest integer not representable as some linear combination of a_is (possibly assumed to have GCD(a_1,...,a_n)=1) is sometimes known as the coin problem.


See also

Coin Problem, Greedy Algorithm, Harmonious Graph, Integer Relation, Knapsack Problem, Stamp Folding, Stöhr Sequence, Subset Sum Problem

Explore with Wolfram|Alpha

References

Guy, R. K. "The Postage Stamp Problem." §C12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 123-127, 1994.Hofmeister, G. "Asymptotische Aschätzungen für dreielementige extremalbasen in natürlichen Zahlen." J. reine angew. Math. 232, 77-101, 1968.Hofmeister, G. "Die dreielementige Extremalbasen." J. reine angew. Math. 339, 207-214, 1983.Hujter, M. and Vizvari, B. "The Exact Solutions to the Frobenius Problem with Three Variables." J. Ramanujan Math. Soc. 2, 117-143, 1987.Mossige, S. "Algorithms for Computing the h-Range of the Postage Stamp Problem." Math. Comput. 36, 575-582, 1981.Mossige, S. "On Extremal h-Bases A_4." Math. Scand. 61, 5-16, 1987.Mossige, S. "The Postage Stamp Problem: An Algorithm to Determine the h-Range on the h-Range Formula on the Extremal Basis Problem for k=4." Math. Comput. 69, 325-337, 2000.Nijenhuis, A. "A Minimal-Path Algorithm for the 'Money Changing Problem.' " Amer. Math. Monthly 86, 832-835, 1979.Shallit, J. "The Computational Complexity of the Local Postage Stamp Problem." ACM SIGACT 33, 90-94, 2002.Sloane, N. J. A. Sequence A014616 in "The On-Line Encyclopedia of Integer Sequences."Stöhr, A. "Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I, II." J. reine angew. Math. 194, 111-140, 1955. Wagon, S. "Greedy Coins." http://library.wolfram.com/infocenter/MathSource/5187/.

Referenced on Wolfram|Alpha

Postage Stamp Problem

Cite this as:

Weisstein, Eric W. "Postage Stamp Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PostageStampProblem.html

Subject classifications