Postage stamp problem

Last updated January 31, 2022

The postage stamp problem is a mathematical riddle that asks what is the smallest postage value which cannot be placed on an envelope, if the latter can hold only a limited number of stamps, and these may only have certain specified face values.^[1]

For example, suppose the envelope can hold only three stamps, and the available stamp values are 1 cent, 2 cents, 5 cents, and 20 cents. Then the solution is 13 cents; since any smaller value can be obtained with at most three stamps (e.g. 4 = 2 + 2, 8 = 5 + 2 + 1, etc.), but to get 13 cents one must use at least four stamps.

Mathematical definition

Mathematically, the problem can be formulated as follows:

Given an integer m and a set V of positive integers, find the smallest integer z that cannot be written as the sum v₁ + v₂ + ··· + v_k of some number k ≤ m of (not necessarily distinct) elements of V.

Complexity

This problem can be solved by brute force search or backtracking with maximum time proportional to |V |^m, where |V | is the number of distinct stamp values allowed. Therefore, if the capacity of the envelope m is fixed, it is a polynomial time problem. If the capacity m is arbitrary, the problem is known to be NP-hard.^[1]

Related Research Articles

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states that every even whole number greater than 2 is the sum of two prime numbers.

In mathematics, a Fermat number, named after Pierre de Fermat, who first studied them, is a positive integer of the form

In number theory, Goldbach's weak conjecture, also known as the odd Goldbach conjecture, the ternary Goldbach problem, or the 3-primes problem, states that

In additive number theory, the Schnirelmann density of a sequence of numbers is a way to measure how "dense" the sequence is. It is named after Russian mathematician Lev Schnirelmann, who was the first to study it.

In additive number theory, the Fermat polygonal number theorem states that every positive integer is a sum of at most $n$ $n$ -gonal numbers. That is, every positive integer can be written as the sum of three or fewer triangular numbers, and as the sum of four or fewer square numbers, and as the sum of five or fewer pentagonal numbers, and so on. That is, the $n$ -gonal numbers form an additive basis of order $n$ .

John Lewis Selfridge, was an American mathematician who contributed to the fields of analytic number theory, computational number theory, and combinatorics.

In mathematics, the Gauss–Kuzmin–Wirsing operator is the transfer operator of the Gauss map. It is named after Carl Gauss, Rodion Kuzmin, and Eduard Wirsing. It occurs in the study of continued fractions; it is also related to the Riemann zeta function.

In number theory, Chen's theorem states that every sufficiently large even number can be written as the sum of either two primes, or a prime and a semiprime.

The coin problem is a mathematical problem that asks for the largest monetary amount that cannot be obtained using only coins of specified denominations. For example, the largest amount that cannot be obtained using only coins of 3 and 5 units is 7 units. The solution to this problem for a given set of coin denominations is called the Frobenius number of the set. The Frobenius number exists as long as the set of coin denominations has no common divisor greater than 1.

In number theory, zero-sum problems are certain kinds of combinatorial problems about the structure of a finite abelian group. Concretely, given a finite abelian group G and a positive integer n, one asks for the smallest value of k such that every sequence of elements of G of size k contains n terms that sum to 0.

Erdős' conjecture on arithmetic progressions, often referred to as the Erdős–Turán conjecture, is a conjecture in arithmetic combinatorics. It states that if the sum of the reciprocals of the members of a set A of positive integers diverges, then A contains arbitrarily long arithmetic progressions.

Sylvesters sequence Integer sequence in number theory

In number theory, Sylvester's sequence is an integer sequence in which each term of the sequence is the product of the previous terms, plus one. The first few terms of the sequence are

In mathematics, the Ulam numbers comprise an integer sequence devised by and named after Stanislaw Ulam, who introduced it in 1964. The standard Ulam sequence starts with U₁ = 1 and U₂ = 2. Then for n > 2, U_n is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way and larger than all earlier terms.

In number theory, primes in arithmetic progression are any sequence of at least three prime numbers that are consecutive terms in an arithmetic progression. An example is the sequence of primes, which is given by $for .$

In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.

The Waring–Goldbach problem is a problem in additive number theory, concerning the representation of integers as sums of powers of prime numbers. It is named as a combination of Waring's problem on sums of powers of integers, and the Goldbach conjecture on sums of primes. It was initiated by Hua Luogeng in 1938.

The Erdős–Turán conjecture is an old unsolved problem in additive number theory posed by Paul Erdős and Pál Turán in 1941.

In computer science, the count-distinct problem (also known in applied mathematics as the cardinality estimation problem) is the problem of finding the number of distinct elements in a data stream with repeated elements. This is a well-known problem with numerous applications. The elements might represent IP addresses of packets passing through a router, unique visitors to a web site, elements in a large database, motifs in a DNA sequence, or elements of RFID/sensor networks.

In mathematics, specifically additive number theory, Romanov's theorem is a mathematical theorem proved by Nikolai Pavlovich Romanov. It states that given a fixed base $b$ , the set of numbers that are the sum of a prime and a positive integer power of $b$ has a positive lower asymptotic density.

References

1 2 Jeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30.

External links

Lunnon, W. F. (1969). "A postage stamp problem". Comput. J. 12 (4): 377–380. doi: 10.1093/comjnl/12.4.377 .
Alter, R.; Barnett, J. A. (1980). "A postage stamp problem". Amer. Math. Monthly. 87 (3): 206–210. doi:10.2307/2321610. JSTOR 2321610.
Graham, R. L.; Sloane, N. J. A. (1980). "On additive bases and harmonious graphs". SIAM J. Algebr. Discrete Methods. 1 (4): 382–404. CiteSeerX 10.1.1.70.5521 . doi:10.1137/0601045.
Challis, M. F. (1993). "Two new techniques for computing extremal h-bases A_k". Comput. J. 36 (2): 117–126. doi: 10.1093/comjnl/36.2.117 .
Kohonen, J.; Corander, J. (2013). "Addition chains meet postage stamps: reducing the number of multiplications". arXiv: 1310.7090 [math.NT].
Kohonen, Jukka (2014). "A meet-in-the-middle algorithm for finding extremal restricted additive 2-bases". arXiv: 1403.5945 [math.NT].
Weisstein, Eric W. "Postage Stamp Problem". MathWorld .
OEIS sequenceA001212(Solution to the postage stamp problem with n denominations and 2 stamps)

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[arxiv-1] 1 2 Jeffrey Shallit (2001), The computational complexity of the local postage stamp problem. SIGACT News 33 (1) (March 2002), 90-94. Accessed on 2009-12-30.

[1]