Lowest Integer That Can't Be Made

Date: 04/05/2004 at 11:49:41
From: Mary
Subject: algebra

You have an unlimited number of 'a' cent stamps and 'b' cent stamps. 
With them, you will be able to make many different postages.  Both a
and b are relatively prime positive integers.

I am interested in finding a cutoff point, that is, a postage value 
above which any postage amount can be made.  I need to find a formula 
involving a and b, that will give the cutoff point for any such 
pair of numbers a and b.

Date: 04/06/2004 at 09:39:46
From: Doctor Rob
Subject: Re: algebra

Thanks for writing to Ask Dr. Math!

I like to look at this problem like this.

I'll use a = 5, b = 8, as an example.

Assume that b > a.  Arrange the numbers from 0 upwards in an array
with b columns, in order like reading a book.

   0  1  2  3  4  5  6  7
   8  9 10 11 12 13 14 15
  16 17 18 19 20 21 22 23
  24 25 26 27 28 29 30 31
  32 33 34 35 36 37 38 39
  40 41 42 43 44 45 46 47
  48 49 50 51 52 53 54 55
  ....

If you can make an amount of postage in this array, then you can make
all the amounts below it in the same column by adding one or more
b-cent stamps.  For example, if you can make 10 cents with two 5-cent
stamps, you can make 18, 26, 34, 42, and 50 by adding 1, 2, 3, 4, or
5 8-cent stamps.

Now start with the column headed by 0.  You can make 0 cents postage
by taking no stamps of either kind.  Thus every number in that column
can be made.  Now move 'a' columns to the right.  You can make 'a'
cents with 1 a-cent stamp.  Thus every number in that column from 'a'
downwards can be made.  Now move 'a' columns to the right again,
wrapping around if necessary.  You can make 2*a cents with two a-cent
stamps.  Thus every number in that column from 2*a downwards can be
made.  In the example, all of the column headed by 0 can be made, all
of the column headed by 5 can be made, and all of the column headed
by 2 from 10 downwards can be made (but not 2 itself).

Continue dealing with columns in this way.  Since a and b are
relatively prime, you will eventually visit every column.  The last
column to be visited will be the one containing (b - 1)*a, which is
headed by b - a.  In the example, you'll visit the columns in this 
order:  0, 5, 2, 7, 4, 1, 6, and 3.

In that last column, you'll be able to make postage for all money
totals from (b - 1)*a downwards, using (b - 1) a-cent stamps and some
number of b-cent stamps.  The largest amount of postage which cannot
be made is the number just above (b - 1)*a, namely (b - 1)*a - b, or
a*b - a - b or (a - 1)*(b - 1) - 1.  Thus every amount of postage from
(a - 1)*(b - 1) on can be made from a-cent and b-cent stamps.  In the
example, the last column is the one headed by 3.  You can make all
numbers from (8 - 1)*5 = 40 - 5 = 35 downwards, but not 40 - 5 - 8 =
27.  So all numbers from 28 = (8 - 1)*(5 - 1) upwards can be made.

Thus your "cutoff point" is (a - 1)*(b - 1).  In my example, it's 28.

   X  1  2  3  4  X  6  7
   X  9 XX 11 12 XX 14 XX
  XX 17 XX 19 XX XX 22 XX
  XX XX XX 27 XX XX XX XX
  XX XX XX XX XX XX XX XX
  XX XX XX XX XX XX XX XX
  XX XX XX XX XX XX XX XX
  ....

Feel free to reply if I can help further with this question.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/