Divide y vencerás

Este quizá sea un dicho bélico, aplicandose cuando el volumen del enemigo es muy considerable, tanto que para poder someterlo o extinguirlo sea necesario reducirlo apequeñas fracciones.

 Una filosofía que no sé hasta que punto sea atinada, sin embargo, su esencia puede ser llevada al mundo de la informática, entre otras muchas disciplinas.

Hace mucho tiempo, cuando me dedicaba a intentar resolver problemas matemáticos de un sitio especialmente dispuesto a ello me encontré una dificultad que me volvió loco. En primer instancia, por mi falta de habilidad/práctica para desarrollar...pero en especial, me rehusé a utilizar un lenguaje de programación que permitiera resolver el problema sin astucia alguna. Ya estamos empezando a hablar de un problema, eso significa que vamos casi a la mitad de este post y me llena de felicidad comentar que por fin he hallado la solución. No la he inventando yo, pero al final la he entendido y aprehendido para lo que venga.

El problema, como quien dice, lo mero bueno.

The series, 1¹ + 2² + 3³ + ... + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + ... + 100010

Dicho problema pertence al sitio de projecteuler.net, del cual estoy seguro que alguna vez tuve que haber mencionado y no ahondaré al respecto. En específico es el problema número 48, así que quien guste puede intentarlo. Mi ojbeto es plasmar únicamente lo que pude asimilar, no es dar una metodología de resolución de problemas así, aunque podría fungir en algun momento como tal.

La primer idea surgió de python, y es como conseguí acceso al foro, para posteriormente podero hallar, con un poco de suerte, de la forma que yo lo había empezado.

El código que motivó lo posterior es>

sum=0;
mod = pow (10, 10)

for x in range(1,1001):
  sum+=pow(x,x);

print sum % mod

Como ven, el tipo de dato está resuelto, y no está demás mencionar la velocidad con la que hace el cálculo de la suma de potencias. Está resuelto debido a que puede almacenar una cantidad estúpida de caracteres. Algo así como 3000 dígitos.

Encontré muchas soluciones con Java, algo que siempre me rehusé por la mala imagen que tiene ante mis ojos. Un código muy frecuente es:

package projecteuler;

import java.math.BigInteger;

public class Problem48 {

    public static void main(String[] args) {
        BigInteger sum = BigInteger.ZERO;
        for (Integer i = 1; i <= 1000; i++) {
            sum = sum.add(new BigInteger(i.toString()).pow(i));
        }
        System.out.println(sum.toString().substring(sum.toString().length()

- 10, sum.toString().length()));
    }
}

¿muy bonito no? Pero sigue sin ser lo que buscamos, queremos algo más ingenioso con tipos de datos estrictos y que pronga a prueba nuestra mente. Bueno, ya llegamos a la última parte, sí esa, dónde yo les digo el motivo bien exacto de este post. En C puro, alguien hizo el favor de subir su algoritmo, y gracias a ello entendi el concepto de "divide y vencerás"

#include

long long pow(int a)
{
        int i;
    long long ans=1;
        for(i=1;i<=a;i++)
        {
                ans*=a;
                ans=ans%1000000000000;
        }
        return ans;
}


void main()
{
    long long pow(int a);
        int i;
        long long sum=0;
         for(i=1;i<=1000;i++)
         {
                sum=(sum+pow(i))%

1000000000000;
         }
         sum=sum%1000000000000;
         printf("%lld",sum);
}

Como vemos no es un código de lo más complejo, pero la idea es la que se me hace buena. La función pow, tiene como tipo de dato long long, es decir, puede albergar muchas cifras, pero no las que necesitamos. Hasta aquí nada de nuevo, al menos para mi, pero sí en las líneas sum=(sum+pow(i))%

1000000000000 y ans=ans%1000000000000, ya que con ella se reduce la cantidad de datos a almacenar, en el sentido de que se queda con los residuos, siendo una cifra no mayor a los diez dígitos (condición del problema), así quitamos toda la basura restante que imposibilita el alacenar el dato completo. Para hacer el experimento hice el siguiente mini código.

#include

int main() {

int sum = 0;
int a = 798078764;
int b = 1000;

sum = a % b;
printf ("suma: %i", sum);

return 0;
 }

Si observan las salidas pueden entender como va eso de que el mod funge como discriminante de dígitos.

Espero les haya quedado sumamente claro el problema y la solución que esta persona dio. El tiempo también es bastante bueno.

Apéndice.

Cifra completa:

10003681991446951770953750112276467955677936806229346545837609

88100234910747716194381428659099527845945869942643191290894720

34297990640767964725986043423846803832604080969103761537037623

77136485100631157329514617742467055842668657596018158436664428

32284556880313114548151539190975398485496645576513465858582712

33640116622195618817344953167410268890832176466302030669977040

86253407660915950227913793680983693063756028138566463587737515

58775213460225796579846583334007349358624342339332981334571237

88880928310334876026136017595081560917946402687100524365210998

08635521420142429034340685609365732310793421940318644139181012

38151056509267393515760392842472501391594073463001521843811073

76702171102630750469573346789782186690664846982834660741296739

58017977916836098347224322419528453525646818682403695695661928

25555323558078061997527689983848863374786789331581565252059172

61433942460098614325923316758337107036262555453185205416611714

88582295085815896143375944632775543805183809213012188363271022

31407332201109740102580216469298331766920619646083790732807627

36061442808517156500628972850868896422679964719258292405858953

07506745783853655618785595896857562256923489147469228109139156

19834754117648358035814128670294158565669942087736286390942241

54722601500447133063011307204270428890504214262819377191859457

43022021472011884863459131908337523074769660105474239288710631

18783026036381319039052008252072057933666712918946233312793697

09407422418787204597097644430924278218773832025749008082433007

49916986982395611258111276078639003552217378466905677073440744

94145266662103839812840216303448476913957072355732716627098372

24522304679291974725911315742582406485833141540094327821304295

46350535740452099845122212642419035501784168245514125486375900

07779082539288247751653566899882749594405895102587985539527709

49351004954644542726561747839910718823868177121590423411939224

74897510790859480559450988056179637229284695542637822176251604

28008228845552540344494860195267115187092227766195753907211126

64615014061474423397476527347561996431185285861416781966834012

47304877101620067935299857588206536772743795633134954545266327

18723482339494825759821076401694316043456512117937935456463521

46302119772669498355892913235757618859497751663073421286386945

61642055255367673112981371825114946494636630737592192130568235

61667776093739425742883930712609962163464088038826569132032160

69263720618308594298797368458427649178484311547207790040169259

56941192735535110259912654460393662889217435813332000837171052

41171504606883543418862024047552177055263424469501298905901938

15824593863369410502481516667981368915666834119771347509438990

48871267944689018938504750500112052257424555556257505602132303

87910337983950333245020653238989115507013882956277763880795687

21085719649389314265671310596627542214460598805893960060360422

69214014020965192942504886702979833963532794604531423755422678

81989197481789780678955093763193658603690898474826976906544473

97801745572036792998179602304178585262679727128346578949838364

2350667978127819110846700.