https://www.johndcook.com/blog/2024/11/10/the-postage-stamp-problem/

John D. Cook
Skip to content

  * MATH
      + PROBABILITY
      + SIGNAL PROCESSING
      + NUMERICAL COMPUTING
      + SEE ALL ...
  * STATS
      + EXPERT TESTIMONY
      + WEB ANALYTICS
      + FORECASTING
      + RNG TESTING
      + SEE ALL ...
  * PRIVACY
      + HIPAA
      + SAFE HARBOR
      + CRYPTOGRAPHY
      + DIFFERENTIAL PRIVACY
      + PRIVACY FAQ
  * WRITING
      + BLOG
      + RSS FEED
      + TWITTER
      + SUBSTACK
      + ARTICLES
      + TECH NOTES
  * ABOUT
      + CLIENTS
      + ENDORSEMENTS
      + TEAM
      + SERVICES

(832) 422-8646
Contact

The Postage Stamp Problem

Posted on 10 November 2024 by John

I recently stumbled upon the Postage Stamp Problem. Given two
relatively prime positive numbers a and b, show that any sufficiently
large number N, there exists positive integers x and y such that

ax + by = N.

I initially missed the constraint that x and y must be positive, in
which result is well known (Bezout's lemma) and there's no
requirement for N to be large. The positivity constraint makes things
more interesting.

5 cent and 21 cent stamps

The problem is called the Postage Stamp Problem because it says that
given any two stamps whose values are relatively prime, say a 5C/
stamp and a 21C/ stamp, you can make any sufficiently large amount of
postage using just those two stamps.

A natural question is how large is "sufficiently large," and the
answer turns out to be all integers larger than

ab - a - b.

So in our example, you cannot make 79C/ postage out of 5C/ and 21C/
stamps, but you can make 80C/ or any higher amount.

If you've been reading this blog for a while, you may recognize this
as a special case of the Chicken McNugget problem, which you can
think of as the Postage Stamp problem with possibly more than two
stamps.

Related posts

  * The Chicken McNugget monad
  * Cicadas and chicken nuggets
  * Possible and actual football scores

Categories : Uncategorized
Bookmark the permalink

Post navigation

Previous PostImpersonating an Edwardian math professor

One thought on "The Postage Stamp Problem"

 1.
    Stefan Schmiedl
    10 November 2024 at 13:44

    In some post-apocalyptic future, an old man is telling an
    attentive horde of youngsters huddled around a camp fire about
    the good old days, when he was working at a drive-through.
    Especially about the fall of 2024, when a bunch of mathematicians
    showed up ordering weird numbers of chicken nuggets and insisting
    to pay with carefully prepared packages of even weirder postage
    stamps.

Leave a Reply

Your email address will not be published. Required fields are marked 
*

          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
          [                                             ]
Comment * [                                             ]

Name * [                              ]

Email * [                              ]

Website [                              ]

[Post Comment] 

 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
 [                                             ] 
D[                                             ] 

Search for: [                    ] [Search]
John D. Cook

John D. Cook, PhD

My colleagues and I have decades of consulting experience helping
companies solve complex problems involving data privacy, applied math
, and statistics.

Let's talk. We look forward to exploring the opportunity to help your
company too.

John D. Cook

(c) All rights reserved.

Search for: [                    ] [Search]
(832) 422-8646

EMAIL