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.


Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!