Yesterday I wrote about the Chicken McNugget problem: if Chicken McNuggets are sold in boxes of 6, 9, and 20, what’s the largest number of nuggets you cannot buy? That post showed that the solution was 43. The technical name for these kinds of problems is numerical monoids.
The method of solution in the previous post is reusable. But before we reuse it, let’s look at a simpler problem involving two units rather than three.
Cicada cycles
Some cicadas appear every 13 years and some every 17 years. So, for example, 43 years from now would be two 13-year cicada cycles and one 17-year cicada cycle. We could ask what the largest number of years is that cannot be expressed in terms of cicada cycles. This is known as the Frobenius number of 13 and 17.
For one thing, there is a largest number of years that cannot be expressed in terms of cicada cycles. If x and y are positive integers, there is an upper bound on the numbers that cannot be expressed as sum of non-negative integer multiples of x and y if and only if x and y are relatively prime. And if x and y are relatively prime, this upper bound is
xy − x − y.
J. J. Sylvester proved this back when Chester A. Arthur was US president [1]. It’s not quite obvious that x and y being relatively prime is sufficient for there to be an upper bound—it follows from Bézout’s lemma—but it is obvious it’s necessary: if x and y are multiples of k > 1, then all sums of integer multiples of x and y are also multiples of k, and so non-multiples of k are unreachable.
So Sylvester’s theorem shows that the Frobenius number of 13 and 17 is 13×17 – 13 – 17 = 191.
Throwing in Venus
Venus goes around the sun 13 times in the time it takes Earth to go around 8 times. That is, Venus and Earth line up every 8 years (from the perspective of our planet). What if we throw in multiples of 8 year cycles? We could, for example, express 25 years as one 17-year cicada cycle and one cycle of Venus.
We know there’s an upper bound on numbers that cannot be expressed as non-negative integer combinations of 13, 17, and 8 because we can express every number greater than 191 using 13 and 17 alone. Adding a new generator cannot increase the Frobenius number. In fact, in this case we know it lowers it because we could apply Sylvester’s theorem to 8 and 13 and show that the Frobenius number of 8, 13, and 17 is at most 83.
Algorithm
There is no analog of Sylvester’s theorem for more than two generators, but we could always compute the Frobenius number in a particular case using the approach from the McNugget post: use brute force up to a point, then use theory to argue that’s enough. In that post, the smallest generator was 6, and we used brute force until we found 6 consecutive numbers that could be produced as non-negative integer combinations of our generators. We could improve on this approach by using Sylvester’s theorem: we use brute force for all combinations that could possibly generate a result lower than an upper bound obtained by Sylvester’s theorem. There are more efficient algorithms—see [2] for references—but the following will work.
from math import gcd, floor
from itertools import product
def frobenius(generators):
"assumes the smallest two generators are relatively prime"
g = sorted(generators)
assert(len(g) > 1)
assert(gcd(g[0], g[1]) == 1)
ub = g[0]*g[1]
limits = [range(int(floor(ub/n))) for n in generators]
reachable = set()
for p in product(*limits):
combo = sum(p[i]*g[i] for i in range(len(g)))
if combo < ub:
reachable.add(combo)
complement = set(range(ub)) - reachable
return(max(complement))
print( frobenius([13, 17, 8]) )
This shows that the Frobenius number of 8, 13, and 17 is 44.
Just to do another example, the code can show that the smallest number of days not representable by multiples of 7, 30, and 365 is 209 days.
Notes
[1] J. J. Sylvester, Mathematical questions with their solutions, Educational Times 41 (1884) 171–178.
[2] Factoring in the Chicken McNugget monoid. arXiv:1709.01606