Calculate floor(pow(2,n)/10) mod 10 - sum of digit

问题:

This is also a math related question, but I'd like to implement it in C++...so, I have a number in the form 2^n, and I have to calculate the sum of its digits ( in base 10;P ). My idea is to calculate it with the following formula:

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

for all of its digits: floor(n/floor(log2(10))).

The first term is easy to calculate with modular exponentiation, but I'm in trouble with the others. Since n is big, and I don't want to use my big integer library, I can't calculate pow(2,n) without modulo. A code snippet for the first term:

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

but for the second I have no idea. I also cannot floor them individually, since it would give '0' (2/10). Is it possible to achieve this? (http://www.mathblog.dk/project-euler-16/ for the easier solution.) Of course I will look for other way if it cannot be done with this method. (for example storing digits in byte array, as in the comment in the link).

Edit: Thanks for the existing answers, but I look for some way to solve it mathematically. I've just came up with one idea, which can be implemented without bignum or digit-vectors, I'm gonna test if it works.

So, I have the equation above for the sum. But 2^n/10^k can be written as 2^n/2^(log2 10^k) which is 2^(n-k*log2 10). Then I take it's fractional part, and its integer part, and do modular exponentiation on the integer part: 2^(n-k*log2 10) = 2^(floor(n-k*log2 10)) * 2^(fract(n-k*log2 10)). After the last iteration I also multiply it with the fractional modulo 10. If it won't work or if I'm wrong somewhere in the above idea, I stick to the vector solution and accept an answer.

Edit: Ok, it seems doing modular exponentiation with non-integer modulo is not possible(?) (or I haven't found anything about it). So, I'm doing the digit/vector based solution.

The code does NOT work fully!

It does not give the good value: (1390 instead of 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;
};

回答1:

In the link you mention, you have the answer which will work as is for any number with n <= 63. So... why do you ask?

If you have to program your own everything then you need to know how to calculate a binary division and handle very large numbers. If you don't have to program everything, get a library for large integer numbers and apply the algorithm shown in the link:

BigNumber big_number;
big_number = 1;
big_number <<= n;
int result = 0;
while(big_number != 0) {
    result += big_number % 10;
    big_number /= 10;
}
return result;

Now, implementing BigNumber would be fun. From the algorithm we see that you need assignment, shift to left, not equal, modulo and division. A BigNumber class can be fully dynamic and allocate a buffer of integers to make said big number fit. It can also be written with a fixed size (as a template for example). But if you don't have the time, maybe this one will do:

https://mattmccutchen.net/bigint/

回答2:

You could create a vector of the digits using some of the techniques mentioned in this other question (C++ get each digit in int) and then just iterate over that vector and add everything up.

回答3:

I implemented this in JavaScript as below for finding the sum of digits of 2^1000: (Check out working CodePen)

function calculate(){
  var num = 0, totalDigits = 1,exponent =0,sum=0,i=0,temp=0, carry;  
  var arr = ['1'];

  //Logic to implement how we multiply in daily life using carry forward method
  while(exponent<1000){ //Mention the power
    carry=0;
    for(var j=arr.length-1;j>=0;j--){
      temp = arr[j]*2 + carry;
      arr[j]= temp%10;
      carry = parseInt(temp/10);
      if(carry && !j){
        arr = [carry].concat(arr); //if the last nth digit multiplication with 2 yields a carry, increase the space!
      }
    }
    exponent++;
  }
  
  for(var i=0;i<arr.length;i++){
    sum = sum+parseInt(arr[i]);
  }
  document.getElementById('result').value = sum; //In my HTML code, I am using result textbox with id as 'result'
  //console.log(arr);
  //console.log(sum);
}