Homer Simpson's bakery sells donuts in 5 packs, 9 packs and 13 packs. What is the largest number of donuts that he can't buy exactly?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
I do not know any formal solution but I did experimentally with a gf:
( 1 − x 5 ) ( 1 − x 9 ) ( 1 − x 1 3 ) 1
Finding the taylor series of which gives you:
⋯ + 4 x 5 0 + 4 x 4 9 + 3 x 4 8 + 2 x 4 7 + 3 x 4 6 + 4 x 4 5 + 3 x 4 4 + 2 x 4 3 + 2 x 4 2 + 3 x 4 1 + 3 x 4 0 + 2 x 3 9 + 2 x 3 8 + 2 x 3 7 + 3 x 3 6 + 2 x 3 5 + x 3 4 + 2 x 3 3 + 2 x 3 2 + 2 x 3 1 + x 3 0 + x 2 9 + 2 x 2 8 + 2 x 2 7 + x 2 6 + x 2 5 + x 2 4 + 2 x 2 3 + x 2 2 + x 2 0 + x 1 9 + 2 x 1 8 + x 1 5 + x 1 4 + x 1 3 + x 1 0 + x 9 + x 5 + 1
Looks like everything higher than 21 is possible.
Read on for a proof that all integer quantities > 21 can be expressed as a multiple sum of these quantites:
22 = 13 + 9
23 = 13 + 5 + 5
24 = 9 + 5 + 5 + 5
25 = 5 + 5 + 5 + 5 + 5
26 = 13 + 13
To get a number higher than 26, you just need to add 5's to the extreme right of the sequences...
Analytical Solution:
When the value of the coins are in arithmetic progression, this formula works:
F r o b e n i u s ( a , a + d , a + 2 d + . . . a + s d ) = ( ⌊ s a − 2 ⌋ + 1 ) a + ( d − 1 ) \ ( a − 1 ) − 1
Plugin a=5,d=4,s=2. The answer is then 21
Thanks to @bobbym none for the analytical solution.