Somma di numeri che fanno una sequenza

Question

Mentre si guarda il rugby, ieri sera mi chiedevo se eventuali punteggi sono stati impossibili dato si può segnare punti solo in un sacco di 3, 5 o 7. Non ci volle molto per capire che qualsiasi numero maggiore di 4 è raggiungibile. 5 = 5, 6 = 3 + 3, 7 = 7, 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5 e così via.

Si estende su quell'idea per 5, 7 e 9 produce i seguenti punteggi possibili:

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

Per 7, 9 e 11:

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

ho questi nella mia testa, qualcuno può suggerire un algoritmo di bene che avrebbe determinato il punteggio più basso possibile di sopra del quale tutti gli spartiti sono raggiungibili dato un insieme di punteggi.

Ho modellato in questo modo:

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

Poi controllare la lista per una sequenza più lunga di 3 (il più piccolo punteggio possibile). Sembra abbastanza impraticabile e lento per tutto al di là del caso banale.

Answer 1

C'è solo un numero irraggiungibile di sopra del quale tutti gli spartiti sono raggiungibili.

Questo è chiamato il numero di Frobenius. Vedere: http://en.wikipedia.org/wiki/Frobenius_number

La pagina wiki dovrebbe avere collegamenti per gli algoritmi per risolverlo, per esempio: http: //www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

Per 2 numeri a, b una formula esatta (ab-ab) è nota (che si potrebbe usare per ridurre lo spazio di ricerca), e per 3 numeri a, b, ca tagliente limite inferiore (sqrt (3ABC) - abc) e gli algoritmi abbastanza veloci sono noti.

Se i numeri sono in progressione aritmetica, allora una formula esatta è noto (vedi wiki). Dico questo perché nei tuoi esempi tutti i numeri sono in progressione aritmetica.

Quindi, per rispondere alla tua domanda, trovare il numero di Frobenius e aggiungere 1 ad esso.

La speranza che aiuta.