Esta también es una pregunta relacionada con las matemáticas, pero me gustaría implementarla en C ++ ... así que tengo un número en el formulario2^n, y tengo que calcular la suma de sus dígitos (en base 10; P). Mi idea es calcularlo con la siguiente fórmula:

sum = (2^n mod 10) + (floor(2^n/10) mod 10) + (floor(2^n/100) mod 10) + ...

para todos sus dígitos:floor(n/floor(log2(10))).

El primer término es fácil de calcular con exponencia modular, pero estoy en problemas con los demás. Ya quen es grande, y no quiero usar mi biblioteca de enteros grandes, no puedo calcularpow(2,n) sin modulo. Un fragmento de código para el primer término:

while (n--){
    temp = (temp << 1) % 10;
};

Pero por el segundo no tengo ni idea. Yo tampoco puedofloor Ellos individualmente, ya que daría '0' (2/10). ¿Es posible lograr esto? (http://www.mathblog.dk/project-euler-16/ para la solución más fácil.) Por supuesto buscaré otra forma si no se puede hacer con este método. (por ejemplo, almacenar dígitos en una matriz de bytes, como en el comentario en el enlace).

Editar: Gracias por las respuestas existentes, pero busco alguna manera de resolverlo matemáticamente. Se me ha ocurrido una idea, que se puede implementar sin vectores grandes o dígitos, voy a probar si funciona.

Entonces, tengo la ecuación de arriba para la suma. Pero2^n/10^k Se puede escribir como2^n/2^(log2 10^k) cual es2^(n-k*log2 10). Luego tomo su parte fraccionaria y su parte entera, y hago exponenciación modular en la parte entera:2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract(n-k*log2 10)). Después de la última iteración, también lo multiplico con el módulo fraccional 10. Si no funciona o si me equivoco en algún punto de la idea anterior, me atengo a la solución vectorial y acepto una respuesta.

Editar: Ok pareceNo es posible hacer una exponencia modular con un módulo no entero (?) (o no he encontrado nada al respecto). Entonces, estoy haciendo la solución basada en dígitos / vectores.

¡El código NO funciona completamente!

No da el buen valor: (1390 en lugar de 1366):

typedef long double ldb;

ldb mod(ldb x, ldb y){             //accepts doubles
    ldb c(0);
    ldb tempx(x);
    while (tempx > y){
        tempx -= y;
        c++;
    };
    return (x - c*y);
};

int sumofdigs(unsigned short exp2){
    int s = 0;
    int nd = floor((exp2) * (log10(2.0))) + 1;
    int c = 0;
    while (true){
        ldb temp = 1.0;
        int expInt = floor(exp2 - c * log2((ldb)10.0));
        ldb expFrac = exp2 - c * log2((ldb)10.0) - expInt;
        while (expInt>0){
           temp = mod(temp * 2.0, 10.0 / pow(2.0, expFrac)); //modulo with non integer b:
                //floor(a*b) mod m = (floor(a mod (m/b)) * b) mod m, but can't code it
            expInt--;
        };
        ldb r = pow(2.0, expFrac);
        temp = (temp * r);
        temp = mod(temp,10.0);
        s += floor(temp);
        c++;
        if (c == nd) break;
    };
    return s;
};