Sum of numbers making a sequence

Question

While watching the rugby last night I was wondering if any scores were impossible given you can only score points in lots of 3, 5 or 7. It didn't take long to work out that any number greater than 4 is attainable. 5=5, 6=3+3, 7=7, 8=3+5, 9=3+3+3, 10=5+5 and so on.

Extending on that idea for 5, 7 and 9 yields the following possible scores:

5,7,9,10,12,14 // and now all numbers are possible.  

For 7, 9 and 11:

7,9,11,14,16,18,20,22,23,25,27 // all possible from here

I did these in my head, can anyone suggest a good algorithm that would determine the lowest possible score above which all scores are attainable given a set of scores.

I modelled it like this:

forall a < 10:
   forall b < 10:
      forall c < 10:
          list.add(3a + 5b + 7c);
list.sort_smallest_first();

Then check the list for a sequence longer than 3 (the smallest score possible). Seems pretty impractical and slow for anything beyond the trivial case.

Answer 1

There is only one unattainable number above which all scores are attainable.

This is called the frobenius number. See: http://en.wikipedia.org/wiki/Frobenius_number

The wiki page should have links for algorithms to solve it, for instance: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

For 2 numbers a,b an exact formula (ab-a-b) is known (which you could use to cut down your search space), and for 3 numbers a,b,c a sharp lower bound (sqrt(3abc)-a-b-c) and quite fast algorithms are known.

If the numbers are in arithmetic progression, then an exact formula is known (see wiki). I mention this because in your examples all numbers are in arithmetic progression.

So to answer your question, find the Frobenius number and add 1 to it.

Hope that helps.