The local postage stamp problem determines, for a fixed set 
of 
positive integer denominations
satisfying 
and a positive integer 
, the smallest integer 
which cannot be represented by a linear
combination 
with 
and 
(Shallit 2002).
Equivalently, the 
-range
of 
is
 |
(1)
|
the largest integer such that every positive integer from 1 through 
can be represented. The global postage stamp problem
asks for the maximum of 
over all such 
-element sets 
; this maximum is denoted 
(Challis and Robinson 2010).
Exact solutions are known for 
and 3. For a fixed two-denomination set,
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 
(modulo 9), and Mossige (1981,
1987) showed that
 |
(5)
|
(Guy 1994, p. 123).
For 
and 
from 1 through 24, the global ranges 
are 2, 4, 8, 12, 16, 20, 26, 32, 40, 46, 54, 64, 72,
80, 92, 104, 116, 128, 140, 152, 164, 180, 196, and 212, respectively (OEIS A001212).
The corresponding numbers of extremal bases are 1, 2, 1, 1, 1, 5, 3, 2, 1, 2, 4,
1, 1, 3, 1, 1, 1, 1, 1, 1, 4, 3, 3, and 3 (Challis and Robinson 2010, Kohonen and
Corander 2014).
A distinct-summand variant allows at most two stamps but requires two used stamps to have different denominations. It asks for the largest 
such that a 
-element set 
of nonnegative integers
contains 0 and every integer from 1 through 
is the sum of two distinct elements
of 
.
For 
from 2 through 20, the maximum values are 1, 3, 6, 9,
13, 17, 22, 27, 33, 40, 47, 56, 65, 74, 83, 94, 105, 117, and 129, respectively (OEIS
A004129). This variant is closely related to
harmonious graphs (Graham and Sloane 1980).
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.
When the number of summands is unrestricted and the denomination set is not required to contain 1, the analogous problem of finding the largest nonrepresentable integer, usually when the denominations have greatest common divisor 1, is the Frobenius problem, also called 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." SIGACT News 33,
90-94, 2002. 
Wagon, S. "Greedy
Coins."