Muestro unas pequeñas optimizaciones al programa mostrado por sukoy, basado en la observacion que en el rango (a,b) es posible que exista un rango (a..lowlimit) en que cada indice sea la mitad de otro indice dentro del rango (lowlimit+1,b) y por tanto cada uno de los num[i] sera menor que los num[j] con i en el primer rango y j en el segundo y como se busca el valor mayor resulta superfluo revisar ese rango.
Ademas, si al recorrer hacia atras, se encuentran elementos en el cache, quiere decir que pertenecen a un recorrido previo y por tanto el indice actual no puede ser el maximo y se puede descartar de manera segura.
Aqui van:
Código Python:
Ver originaldef max_cycle(a, b):
cache = {1:1}
def num(cache, n):
if n in cache: return cache[n]
if n % 2:
r = cache[n] = 1 + num(cache, 3 * n + 1)
else:
r = cache[n] = 1 + num(cache, n >> 1 )
return r
def sec(a, b):
if a == b: return num(cache,a)
maxim = 0
if a > b: a,b = b,a
lowlimit = max(a,b/2,2)
for i in xrange(b,lowlimit-1,-1):
if i in cache: continue
tr = num(cache, i)
if tr > maxim:
maxim = tr
return maxim
return sec(a, b)