Generación de enteros a partir de una combinación lineal de enteros

Question

Dados unos enteros positivos $t_1, ..., t_n$ tal que $\mathrm{gcd}(t_1, ..., t_n) = 1$ . Ahora creamos una combinación lineal de estos: $k_1 t_1 + ... + k_n t_n$ donde $k_1, ..., k_n$ son enteros no negativos que puedes elegir para generar diferentes enteros.

¿Cuál es el menor $N$ tal que todos los enteros mayores o iguales a $N$ puede ser generada por la combinación lineal?

Ejemplo: $k_1 3 + k_2 4$ puede generar $0, 3, 4, 6, 7, 8, 9, ...$ . Así que aquí $N = 6$ y $k_1 = 2, k_2 = 0$ .

Answer 1

Este es un problema famoso, a veces llamado el problema de la moneda de Frobenius.

Si $n=2$ se sabe que la respuesta a su pregunta es $N = t_1 t_2 - (t_1 + t_2) + 1$ . Una prueba de esto se puede encontrar en la respuesta a este pregunta reciente .

Para tres o más enteros, no se conoce una solución de forma cerrada para $N$ . Hay algunos límites en los valores de $N$ en el $n = 3$ caso, así como algunos algoritmos para determinar $N$ . Para más información y referencias, consulte el Wikipedia y MathWorld páginas sobre el problema de la moneda de Frobenius.

Básicamente, el problema se considera resuelto cuando $n = 2$ , resuelto parcialmente (debido a los límites y algoritmos) cuando $n = 3$ y sin resolver cuando $n \geq 4$ .

Actualización: Guy's Problemas no resueltos de la teoría de los números dice: "El caso $n = 3$ fue resuelto explícitamente por primera vez por Selmer y Beyer, utilizando un algoritmo de fracción continua". Así que supongo que el $n=3$ el caso ha sido resuelto. Supongo que habría que desenterrar su artículo (está en las referencias de MathWorld) para ver su solución.