A Postage Stamp Problem

Suppose you have many (as many as you need) postage stamps in the denominations 4, 6 and 7 cents. What exact postages could you make? This is an example of a postage stamp problem. Here, after a little thought, you can see that you can make any amount except 1, 2, 3, 5, 8, or 9 cents. (It’s easy to check you can’t get those amounts, and since 10=4+6, 11=4+7, 12=6+6, and 13=6+7, we can make any amount 10 cents or more; once we have 10, 11, 12, and 13, we can just keep adding 4’s to get anything larger.) Let’s say here that a number k is “achievable” in this problem unless k = 1, 2, 3, 5, 8, or 9.

In such problems, we may as well assume that our given denominations have no common divisor greater than 1. (Otherwise just factor out the greatest common divisor.) It’s then a simple number theory exercise to show that in that case there will be only a finite number of postages that we cannot achieve.

For the topology application in my joint paper with Professor Inga Johnson, we had to deal with an infinite sequence of postage stamp problems, indexed by nonnegative integers n. Here’s a table of the given denominations for various n:

n=0: 2, 3
n=1: 4, 6, 7
n=2: 8, 12, 14, 15
n=3: 16, 24, 28, 30, 31

In general, for a given n, the denominations are
2n+1, 2n+1+2n, 2n+1+2n+2n-1,…,2n+1+2n+2n-1++1
where alternatively the last of these numbers could be written as 2n+2 -1.

It’s an amusing exercise to show that the smallest number k for which all numbers k or more are achievable on line n is n.2n+2+2. So for example, using the denominations 8, 12, 14, 15 above corresponding to n=3 above, we can achieve any amount that is 23+2+2=34 or more (but cannot get 33). But actually, that is not the problem we needed to solve.

It’s another fairly simple exercise to see that if a number k is not achievable for some value of n, then it’s also not achievable for any larger value of n. Also, if n is too large (so that 2n+1>k) k will certainly be not achievable. So given a number k>0, there will be a smallest value of n for which k is unachievable. We needed an easy way to compute that.

And here it is. Let me illustrate with a couple of values of k. Let’s start with k = 132. Write k in binary, with a couple of extra zeros in front:
0010000100
Then insert * somewhere:
001*0000100
To the left of the * decode the string as a number in binary: 001 -> 1, call this number “a”.
To the right of the * count the number of zeros, excluding any at the end:
0000100 -> 4. Call this number “b”.
Compare the results: This time a<b. That will always happen if we place the * far enough to the left (if nothing else, between the initial two 0’s); find the rightmost position for the * with a<b. In our case, that would be 0010*000100, where we have a=2, b=3. Then subtract 2 from the length of the string to the right of the *. Length(000100) – 2 = 4.
That’s the method. We have 132 is not achievable for n=4 (with stamps of denominations 32, 48, 56, 60, 62, 63) but is achievable for n<4.

Here’s another example, k = 29 -> 0011101 and our rightmost placement of * would be 00*11101 where a=0 and b=1. Then length(11101) – 2 = 5 – 2 = 3. So 29 is not achievable for n=3 but is for n<3.

(If you have both k and n given and you simply want to know whether k is achievable at level n, you could directly insert the * so that the length of right hand string is n+2; then k is unachievable at level n if and only if a < b. If n is very large you might need more 0’s at the start of the string, but then the answer will be that k is unachievable – it will be smaller than the smallest stamp value at level n.)

The algorithm could be carried out pretty quickly in general, with a number of steps at worst proportional to the log of k.

It’s not at all obvious that the method works, of course. If you’re interested, you can skip the topology and find the proof embedded in the paper written with Dr. Inga Johnson (reference under the Research tab).