# Frobenius Numbers

Here are two puzzles that are typical of a class of puzzles that involve a special property of a set of integers:

- What is the largest amount that cannot be given in change with coins of denomination 5, 8 and 15 pence?
- At McDonald’s, chicken nuggets come in packs of 6, 9 or 20 nuggets. What is the largest number of nuggets that I cannot buy without splitting packs

If we look at the first of these puzzles and we list how to give change for various amounts, we obtain the list:

15 = 0 * 5 + 0 * 8 + 1 * 15

16 = 0 * 5 + 2 * 8 + 0 * 15

17 = none

18 = 2 * 5 + 1 * 8 + 0 * 15

19 = none

20 = 1 * 5 + 0 * 8 + 1 * 15

21 = 1 * 5 + 2 * 8 + 0 * 15

22 = none

23 = 0 * 5 + 1 * 8 + 1 * 15

24 = 0 * 5 + 3 * 8 + 0 * 15

25 = 2 * 5 + 0 * 8 + 1 * 15

26 = 2 * 5 + 2 * 8 + 0 * 15

27 = none

28 = 4 * 5 + 1 * 8 + 0 * 15

29 = 1 * 5 + 3 * 8 + 0 * 15

30 = 0 * 5 + 0 * 8 + 2 * 15

31 = 3 * 5 + 2 * 8 + 0 * 15

32 = 0 * 5 + 4 * 8 + 0 * 15

Now that we have solutions for 5 consecutive integers (28 .. 32), we can add 5 to each of these solutions to get solutions for the integers (33 .. 37). And since we can repeat this process indefinitely, we now know that the largest amount of change that we cannot give must be 27 pence.

This puzzle provides an example of a * Frobenius Number*. If we have a set of integers \(\left(a, b, c,\ldots\right)\) that have no common factors greater than 1 and we try to express another integer (\(n\)) as the sum of multiples of these integers \(n = p a + q b + r c + \ldots\) where the multiples \(\left(p, q, r, \ldots\right)\) are all non-negative, we find that there is always a maximum number that cannot be expressed in this way. This is called the Frobenius Number for the set of integers \(\left(a, b, c, \ldots\right)\).

Analytical expressions are known for Frobenius numbers in a few situations:

\[\begin{array} FF(a,b) & = ab-(a+b) \\ F(a,a+b,\ldots,a+kb) & =(a-1)(b-1)+a\left(\lfloor\frac{a-2}{k}\rfloor+1\right)-1 \\ F(a^k,a^{k-1}b,\ldots,ab^{k-1},b^k) & =\frac{(b-1)a^{k+1}-(a-1)b^{k+1}}{a – b}\end{array}\]

It is also known that for two values \((a-1)(b-1)/2\) integers have no representation.

But more generally it would be nice to have a program for solving such puzzles and the above example gives us a suitable method. If we try to express increasing integers as sums of multiples of our integers, as soon as we have a number of consecutive solutions where this number is equal to the smallest number in our set, we then know that we can express all higher numbers in this way. So the Frobenius Number for this set is the number immediately below the first such sequence .

This gives us a way of solving puzzles of this kind and this program implements this strategy for sets of 3 integers:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
def find_representation(a, b, c, n): for i in range(n, -1, -a): for j in range(i, -1, -b): if not j % c: return True return False def frobenius_number(a, b, c): a, b, c = sorted((a, b, c)) base = n = c while True: if find_representation(a, b, c, n): if n == base + a: return base else: base = n n += 1 |

If we now run the program for some typical problems:

1 2 3 4 5 |
print(frobenius_number(5, 8, 15)) print(frobenius_number(6, 9, 20)) print(frobenius_number(83, 89, 97)) |

we obtain the results: 27, 43 and 1421.

However, although this works well for small values, it only works for sets of three integers and it cannot handle sets that involve large integers. For example, if we try to use it to find the Frobenius Number for the three integers (9949, 9967, 9973) it proves to be hopelessly slow and appears to stop working.

Interestingly, however, the mathematics involved in Frobenius Numbers and the development of algorithms for solving such problems has been very active over the last decade because solutions are needed in molecular spectroscopy and in DNA sequence matching.

One of the neatest algorithms to be developed recently is described in this paper:

The Money Changing Problem Revisited: Computing the Frobenius Number in Time O(ka1), by Sebastian Bocker and Zsuzsanna Liptak, June 2004, Technical Report number 2004-2, University of Bielefeld, Technical Faculty.

and this is my Python implementation of it:

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 |
def gcd(a, b): while a: b, a = a, b % a return b def residue_table(a): n = [0] + [None] * (a[0] - 1) for i in range(1, len(a)): d = gcd(a[0], a[i]) for r in range(d): try: nn = min(n[q] for q in range(r, a[0], d) if n[q] != None) except: continue if nn != None: for c in range(a[0] // d): nn += a[i] p = nn % a[0] nn = min(nn, n[p]) if n[p] != None else nn n[p] = nn return n print(frobenius_number((9949, 9967, 9973))) |

The function frobenius_number takes a sequence of integer values (in a tuple, list or other Python sequence type) and returns the Frobenius Number for the sequence. In the example above it quickly gives the solution: 24,812,836. In principle this algorithm can handle any sequence lengths and it is quite fast even for long sequences and large integers.

## Frobenius Solutions

Lets assume that you have just measured the molecular weight of a chemical sample and you now want to identify what it is. You know that it consists of a number of atoms of carbon, hydrogen, oxygen, … and you also know the atomic weights of each of these elements. How can you use this information to identify the chemical that you have sampled?

Since you know the molecular weight (M) of the sample and the atomic weights of its possible constituents, you know that:

molecular_weight (M) = no_of_carbon_atoms * atomic_weight(carbon) + no_of_hydrogen_atoms * atomic_weight(hydrogen) + …..

But you don’t know how many of each type of atom are involved. But this is a Frobenius sum so it is likely that the sum will only work for particular numbers of atoms of each element. What you want to find out is whether there are sets of integers (no_of_carbon_atoms, no_of_hydrogen_atoms, …) that match your measured value of M. If you are lucky there might be only one solution but you might find thousands of solutions and hence many different chemicals that match your sample.

Either way you want to know the answer and it turns out that the above algorithm can be extended to provide this:

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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
from math import gcd as builtin_gcd def gcd(a, *r): for b in r: a = builtin_gcd(a, b) return a def lcm(a, *r): for b in r: a *= b // builtin_gcd(a, b) return abs(a) def frobenius_number(a): def __residue_table(a): n = [0] + [None] * (a[0] - 1) for i in range(1, len(a)): d = gcd(a[0], a[i]) for r in range(d): try: nn = min(n[q] for q in range(r, a[0], d) if n[q] is not None) except ValueError: continue if nn is not None: for c in range(a[0] // d): nn += a[i] p = nn % a[0] nn = min(nn, n[p]) if n[p] is not None else nn n[p] = nn return n if len(a) < 2 or gcd(*a) > 1: raise ValueError return max(__residue_table(sorted(a))) - min(a) def frobenius_solve(a, m): def __extended_residue_table(a): n = [[0] + [None] * (a[0] - 1)] for i in range(1, len(a)): n.append(n[-1][:]) d = gcd(a[0], a[i]) for r in range(d): try: nn = min(n[-1][q] for q in range(r, a[0], d) if n[-1][q] is not None) except ValueError: continue if nn is not None: for c in range(a[0] // d): nn += a[i] p = nn % a[0] nn = min(nn, n[-1][p]) if n[-1][p] is not None else nn n[-1][p] = nn return n def __frobenius_recurse(a, m, ert, c, i): if i == 0: c[0] = m // a[0] yield tuple(c) else: lc = lcm(a[0], a[i]) l = lc // a[i] for j in range(l): c[i] = j mm = m - j * a[i] r = mm % a[0] lb = ert[i - 1][r] if lb is not None: while mm >= lb: yield from __frobenius_recurse(a, mm, ert, c, i - 1) mm -= lc c[i] += l g = gcd(*a) if m <= 0 or len(a) < 2 or g > 1 and m % g: return if g > 1: a, m = sorted(x // g for x in a), m // g ert = __extended_residue_table(a) c = [0] * len(a) yield from __frobenius_recurse(a, m, ert, c, len(a) - 1) |

Here the input to frobenius_solve is a set of integers in the sequence a (e.g. the atomic weights of the elements) and a number m (e.g. the measured molecular weight) for which we want solutions.

As a simple example of the use of this program, we can use it to answer the question: “With coins of 5, 8, 9 and 12 pence, how many ways can we give change of 67 pence?” This is easily answered using the above program:

1 2 3 4 |
t = frobenius_solve((5, 8, 9, 12), 67) print(len(t), t) |

which gives the answer 21 and lists how many of each coin are used in each different way of giving change:

1 2 3 4 5 6 7 |
[7, 4, 0, 0], [10, 1, 1, 0], [2, 6, 1, 0], [ 1, 1, 6, 0], [5, 3, 2, 0], [8, 0, 3, 0], [ 0, 5, 3, 0], [3, 2, 4, 0], [11, 0, 0, 1], [3, 5, 0, 1], [2, 0, 5, 1], [ 6, 2, 1, 1], [1, 4, 2, 1], [ 4, 1, 3, 1], [7, 1, 0, 2], [2, 3, 1, 2], [ 5, 0, 2, 2], [0, 2, 3, 2], [ 3, 2, 0, 3], [1, 1, 2, 3], [2, 0, 1, 4] |

Thank you for sharing your implementation of Bocker Liptak algorithm!

The frobenius_number( ) function is missing from the second code snippet. I will try to deduce how it should work from the article, but if you could include it, that would be cool.

Thanks!

I have updated the code above to include frobenius_number(). But you might prefer to download my number_theory library described at: http://ccgi.gladman.plus.com/wp/?page_id=1500, which includes this code.

Woot! Thanks for the quick response. I will definitely check out the library.

In my spare time I work on this:

https://github.com/ConceptJunkie/rpn

and had been looking for the means to add a ‘frobenius’ operator. I’ve downloaded a ton of papers and was prepared to start trying to read and understand them when I found your code. However, using the library makes a lot more sense. I’ll just have to make it work with mpmath.

Thanks again!