Somma di numeri che fanno una sequenza

Question

Mentre guardavo il rugby la scorsa notte mi chiedevo se i punteggi fossero impossibili dato che puoi segnare solo punti in 3, 5 o 7. Non ci è voluto 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.

Estendendosi su questa idea per 5, 7 e 9 si ottengono 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 fatto questi nella mia testa, qualcuno può suggerire un buon algoritmo che determinerebbe il punteggio più basso possibile al di sopra del quale tutti i punteggi sono raggiungibili considerando 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(); 

quindi controllare la lista per una sequenza più lunga di 3 (il più piccolo punteggio possibile). Sembra piuttosto poco pratico e lento per qualcosa che va oltre il caso banale.

Answer 1

C'è solo un numero irraggiungibile al di sopra del quale tutti i punteggi sono raggiungibili.

Questo è chiamato il numero 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 tagliare verso il basso lo spazio di ricerca), e per 3 numeri a, b, un limite inferiore netto (sqrt (3abc) -abc) e sono noti algoritmi abbastanza veloci.

Se i numeri sono in progressione aritmetica, è nota una formula esatta (vedere wiki). Lo dico perché nei tuoi esempi tutti i numeri sono in progressione aritmetica.

Quindi, per rispondere alla tua domanda, trova il numero di Frobenius e aggiungine 1.

Spero che questo aiuti.