Suma de los números que hacen una secuencia

Question

Mientras observa el rugby anoche me preguntaba si alguna puntuaciones fueron imposible teniendo en cuenta que sólo se puede ganar puntos en lotes de 3, 5 o 7. No pasó mucho tiempo saber que cualquier número mayor que 4 es alcanzable. 5 = 5, 6 = 3 + 3, 7 = 7, 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5 y así sucesivamente.

Extendiéndose sobre esa idea para 5, 7 y 9 se obtiene la siguiente puntuaciones posibles:

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

Para 7, 9 y 11:

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

Me hizo estas en mi cabeza, ¿Puede alguien sugerir un algoritmo bien que determinaría la puntuación más baja posible por encima de la que todos los resultados son alcanzables dado un conjunto de puntuaciones.

Modelé de esta manera:

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

A continuación, compruebe la lista de una secuencia más larga de 3 (el más pequeño puntuación posible). Parece bastante poco práctico y lento para nada más allá del caso trivial.

Answer 1

Hay sólo un número inalcanzable por encima del cual todas las puntuaciones son alcanzables.

Esto se conoce como el número de Frobenius. Ver: http://en.wikipedia.org/wiki/Frobenius_number

La página wiki debe tener enlaces de algoritmos para resolverlo, por ejemplo: http: //www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

Para 2 números a, b se conoce una fórmula exacta (ab-ab) (que se puede utilizar para reducir su espacio de búsqueda), y durante 3 números a, b, CA cota inferior (sqrt (3 ABC) - abc) y algoritmos bastante rápido son conocidos.

Si los números están en progresión aritmética, a continuación, una fórmula exacta es conocida (ver wiki). Menciono esto porque en sus ejemplos, todos los números están en progresión aritmética.

Así que para responder a su pregunta, encontrar el número de Frobenius y añadir 1 a la misma.

Espero que ayude.