Suma de números monótonos crecientes (II)

propuesto por josejuan

En el anterior desafío se pidió obtener un algoritmo polinómico y se probó que en base 10 la suma vale 320214537. Ahora se pide utilizar dicho algoritmo para calcular las sumas para las bases 60 y 300.

Enunciado
La suma de todos los números en base 60 cuyos dígitos forman una sucesión monótona creciente, suman

   37851759964142317188220652
   81050413316059401332286757
   29683404507251517718626716
   96140624970292053615487705 (en base 10)


Si la base es 300, la suma alcanza

    415533748267293207257621322025788644561738491859538573229302
    124795268191840891456967655929825952966924748034200273844170
    757659907065588900253362975393110033663344375937246791059366
    512697698590176482669333335167572289324745301079542669405827
    145477577879189254977559011395202369600229789587114441453859
    859484066124981921625567208779855019395100939768384594381514
    257670846079805889799784671834070275192321190631434276584768
    926373141076474122618595012054973748071764979068703381306762
    593501885420667380423601882046488567438103216026437378334758
    336397380418544695560174258204858030587982030362478818239599
    038941445405455313172082619152610590663913326192455212965496
    433615167672379218555088943073928042394932895271856554691124
    8620705970745044025 (en base 10)


Si el algoritmo obtenido en el desafío anterior posee X instrucciones (sumas, restas, comparaciones, ...) y a la CPU le lleva T tiempo ejecutarlas (ej. si tiene 1000 instrucciones, en una CPU a 1GHz es un microsegundo).

Entonces, si dicho algoritmo tiene O(n), obtener éste último número no debería llevarle más de 300 veces T (digamos que unos 0,3 milisegundos).

Si dicho algoritmo fuera O(n^2), obtener éste último número no debe llevarle más de 90000 veces T (digamos que unos 0,1 segundos).

Si dicho algoritmo fuera O(n^3), el tiempo aproximado rondaría los 27 segundos.

Aunque nuestro algoritmo fuera O(n^4), el tiempo aproximado sería de 2,25 horas.

Pero si el tiempo de nuestro algoritmo fuera exponencial, ¿cuanto le costaría calcular, no ya para la base 300, sino para la base 60?

Si nuestro algoritmo es O(2^n), el tiempo aproximado para la base 60 sería de unos 18 milenios...

¿Cuanto tiempo le lleva a tu algoritmo?

Ver todo el enunciado

Preguntas sobre el desafío

¿Tienes dudas sobre el desafío? plantéala aquí

Plantea tu pregunta

1 Solución

Dar mi solución