Consider a set 
of 
positive integer-denomination
postage stamps sorted such that 
. Suppose they are to be used on an
envelope with room for no more than 
stamps. The postage stamp problem then consists of determining
the smallest integer 
which cannot be represented by a linear
combination 
with 
and 
.
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
 |
(1)
|
where 
is called an 
-range.
Exact solutions exist for arbitrary 
for 
and 3. The 
solution is
 |
(2)
|
for 
.
It is also known that
 |
(3)
|
(Stöhr 1955, Guy 1994), where 
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 
,
 |
(4)
|
where 
and 
are functions of 
(mod 9), and Mossige (1981, 1987) showed that
 |
(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 
is fixed.
A related problem asks for the largest integer not representable as some linear combination of 
s
(possibly assumed to have 
) is sometimes known as the coin
problem.
-Range
of the Postage Stamp Problem." Math. Comput. 36, 575-582, 1981.Mossige,
S. "On Extremal 
-Bases 
." Math. Scand. 61, 5-16, 1987.Mossige,
S. "The Postage Stamp Problem: An Algorithm to Determine the 
-Range on the 
-Range Formula on the Extremal Basis Problem for 
." 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 
Wagon, S. "Greedy Coins."