Somme des numéros faisant une séquence

Question

En regardant le rugby hier soir, je me demandais si les scores étaient impossibles étant donné que vous ne pouvez marquer des points dans des lots de 3, 5 ou 7. Il n'a pas fallu longtemps pour comprendre que tout plus de nombre de 4 est réalisable. 5 = 5, 6 = 3 + 3, 7 = 7, 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5 et ainsi de suite.

L'extension de cette idée pour 5, 7 et 9 donne les scores possibles suivants:

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

7, 9 et 11:

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

Je ne ces dans ma tête, quelqu'un peut-il suggérer un bon algorithme qui déterminera le score le plus bas possible au-dessus duquel tous les scores sont réalisables étant donné un ensemble de scores.

Je l'ai modelée comme ceci:

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

Ensuite, vérifiez la liste pour une séquence plus longue que 3 (score de la plus petite possible). Il semble assez peu pratique et lent pour quoi que ce soit au-delà du cas trivial.

Answer 1

Il n'y a qu'un seul numéro inaccessible au-dessus duquel tous les scores sont réalisables.

Ceci est appelé le numéro de Frobenius. Voir: http://en.wikipedia.org/wiki/Frobenius_number

La page wiki devrait avoir des liens pour les algorithmes pour le résoudre, par exemple: http: //www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

Pour 2 nombres a, b une formule exacte (ab-ab) est connue (que vous pouvez utiliser pour réduire votre espace de recherche), et 3 nombres a, b, ca borne inférieure forte (RACINE (3abc) - abc) et des algorithmes très rapides sont connus.

Si les chiffres sont en progression arithmétique, alors une formule exacte est connue (voir wiki). Je mentionne cela parce que dans vos exemples, tous les chiffres sont en progression arithmétique.

Donc, pour répondre à votre question, trouver le numéro Frobenius et ajouter 1 à elle.

L'espoir qui aide.