Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Sum of numbers making a sequence

Tags:

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.