Fue dificil para mí así que compartí el problema con un amigo y descubrimos que, para una ecuación de la forma 6a+9b+20c=n, dejando pivotear el valor de a, los valores de b y c solo toman valores de (0,1) y (0,1,2) respectivamente, a partir del cual se cumple que para cualquier n >= 43 se puede encontrar siempre una combinación natural y positiva para la cual existe solución, ya que existe un teorema que indica que para un n, que tuviera n+1, n+2,...n+5 soluciones continuas, entonces para cualquier solución >= n siempre existirá una combinación de constantes naturales y positivos que tuvieran solución.
Por lo que pude formular el siguiente algoritmo, para procesar el continuo y encontrar el número mas grande posible antes de alcanzar n (notese que el teorema indica n -> n+5 por lo que deben probarse 6 soluciones continuas, a la que se le agrega una a la hora de buscar la última sin n solución)
#6a + 9b + 20c
n = 1
number_of_sucessive_successes = 0
success_on_n = False
while number_of_sucessive_successes < 6:
for b in range(0, 2):
for c in range(0, 3):
for a in range(0, n + 1):
if 6*a + 9*b + 20*c == n:
success_on_n = True
if success_on_n is True:
number_of_sucessive_successes += 1
else:
number_of_sucessive_successes = 0
success_on_n = False
n += 1
print n - 7 # - 6 because last 6 were sucessive solutions, so - 1 for the last not buyable solution
Para la cual generalicé una solución para cualquier ecuación diofántica del mismo tipo:
#general solution
n = 1
number_of_sucessive_successes = 0
success_on_n = False
constants = (5, 11, 17)
while number_of_sucessive_successes < 6:
for y in range(0, n + 1):
for z in range(0, n + 1):
for x in range(0, n + 1):
if constants[0]*x + constants[1]*y + constants[2]*z == n:
success_on_n = True
if success_on_n is True:
number_of_sucessive_successes += 1
else:
number_of_sucessive_successes = 0
success_on_n = False
n += 1
print n - 7 # - 6 because last 6 were sucessive solutions, so - 1 for the last not buyable solution
J.V.
