Sum digits that result from an exponential

Question

I am working on an exercise and seemed to be stuck more with how to approach the problem mathematically, rather than syntactically.

The idea is simple when a number is relatively small. Given a base and power, the program should sum the digits of the result. Let's use an example to explain what I want to do.

base 2 and power 8 is given and thus 2^8 = 256 then the program should sum the digits of the answer so 2+5+6 = 13 and that is the whole point, to find the sum of the digits of the result of a base raised to a power.

Now, this is in an easy example, if I move to a ridiculously huge number, let's say 2^1000, this is almost impossible to just throw into anything that I have tried as we lose precision because the result is huge and gets truncated. The answer must be precise.

I thought maybe there is a mathematical way to do this differently, somehow break it up into smaller chuncks but really I can't think of any relationships other than:

2^1000 = 2^500*2^500

1000 log(2) = log(ans)

Either way, this doesn't get me anywhere near digits in the result that I can start summing.

I hope that I explained it clearly.

For what it is worth, I am using C++ (and gave lua a shot too) and maybe I could use a library but this number would have 302 digit places and I should write my program to handle an exponent of 1000. I really think I am missing some mathematical trick here.

EDIT Partial Solution Found

I have spent a little time with lua trying to solve this today, and I will give it a shot with C++ tonight to see if I get different results. I can find the source of the error, but I have found a solution that works for most cases. Just not for 2^1000, and some other exponents with very large numbers.

The solution works described and the Comment from MooseBoys.

I make use of a modular exponentiation. The lua code is below:

-- Function purpose:  Calculate modular exponent (see wiki in comment 
from MooseBoys)
--
-- @param b: base
-- @param e: exponent
-- @param m: modulation
-- @result c: result
-- 
--  example: 2^15    = 32768
--  ModPow(2,15,10)  = 8
--  ModPow(2,15,100) = 68
--
local ModPow = function(b,e,m)
   local c = 1

   for i = 1, e do
       c = c*b%m
   end

   return c
end

-- Function purpose: Check uniqueness of result from last one.
-- ModPow will not return leading 0, so in the case 2^20 = 1048576
-- Sum result would equal 35 because:
-- ModPow(2,20,10^5) = 48576
-- ModPow(2,20,10^6) = 48576  
-- 
-- Also there is an issue with rounding I am working on.  Current Problem
-- Sometimes, result is          6.xxxxxxxxxx2e+294
-- and with leading 0 result is  6.xxxxxxxxxx3e+294  
-- So the result does not catch there was a leading 0 since s1 and s2 
-- are not equal
-- However, this fix is giving me problems (assuming mod exponent always 
-- grows by an order of magnitude.. 10^(n+1) each cycle), I assumed 
-- just checking exponent value is good enough
-- Now I get some strange results as outlined blow    
-- 
-- @param s1: Current result from ModPow (as string)
-- @param s2: Last result of ModPow (as string)
-- @result bool based on whether or not this number is valid to add to the sum 
local CheckUnique = function(s1,s2)  

   if s1:find('e') and s2:find('e') then   --fix rounding?
      if(s1:sub(s1:find('e'),s1:len())==s2:sub(s2:find('e'),s2:len())) then print(0) return false end
   elseif (s1 == s2) then print(0) return false  --fix leading 0
   end

   print(s1) --test
   return true
end


--self explanitory
local base = 2
local exp = 1000
local mod = 10

--Counters and value holders
local sum = 0
local lval = 0
local val,valS = 1,'1'
local cycle = 1


--Know when to stop
local endval = base^exp
print(endval)

while val ~= endval do

   val = ModPow(base,exp,mod^cycle)      
   valS = tostring(val)

   if(CheckUnique(valS,lval)) then         --is unique   
       sum = sum + tonumber(valS:sub(1,1)) --sum leading digit    
   end

   lval = valS
   cycle = cycle+1

end

print(sum)

The problem lies within the result.
You can imagine, printing every result from the mod cycle should be something like

Value: 1048576
6
76
576
8576
48576
0
1048576
sum: 31

I put a print(0) on there when the check detects leading 0, otherwise, prints value of c. You can see, each first digit will get added to give the correct sum. Each net line should contain the previous line plus the new digit, like a growing heading basically.

However, the problem I can't solve is now when I extend this to a large number, let's say the solution I cam going for. 2^1000..

Results: (Healthy lines, near the end)

2.6725480652012e+288
6.2672548065201e+289
8.6267366100831e+290
1.8626730674387e+291
7.186267401715e+292
0
6.0718626734093e+294
8.6071862673409e+295
0
5.0860718626736e+297
1.5086071862673e+298
7.1508607186267e+299

The last line for instance, is the same as if you list the first digits going backwards in the list: 7.1508607186267e+299

7 15086071862

Being excited, I found the answer to be incorrect. I looked deeper in to the lines and found these unhealthy lines:

9.18229858679e+069
7.5447775000848e+070
8.8906306939456e+069
4.1746958410049e+072
5.0621122825342e+073
4.1602034907325e+074
1.9248790609684e+075 -- no such order 454879 but have 924879?
....
8.3104764719996e+086
3.8310476472e+087
4.6735451839797e+088
8.0281504870817e+089
3.0808317990698e+090
9.0430240225156e+091 --no such order 938438...?

There appear to be several areas where this happens, and only on exponents over 200ish.. I checked with 100 and it was perfect. noticed mistakes in 200 such as

2.9937827928353e+018
0
2.0299378279284e+020
2.2029937827928e+021
7.8493010541604e+022
5.0206666406882e+023
0
3.384239167984e+025

Anyone have any new tips on what may be the problem? (sorry, my lua interperter may be different, not sure about lua in general.. I am just using an IDE that is used for game scripts)

Okay, getting closer. My C++ program handles things a big better and here is the code for it. Still getting the wrong answer, but at least I am getting the same amount of digits. I can't seem to figure out what is wrong with this now. The thing is, this exercise is on a website, I don't know the correct answer, just that my program is giving me the wrong answer for 2^1000. It passes the other test cases I give it (the ones I can do manual and check the answer up to 2^20)

#include <iostream>
#include <cmath>


double ModPow(int,int,long double);

int main() {


    int base = 2;
    int power = 1000;
    long double mod = 10;
    long double val = 0;
    int i = 0;
    int sum = 0;

    double ans = pow(base,power);
    std::cout << ans << std::endl;





    while(ans != val) {

        val = ModPow(base,power,mod);
        std::cout<< val << "   ";
        sum += int(floor(val/(mod/10)));
        mod = mod * 10;
        i += 1;
        if(i%5 == 0) std::cout << std::endl;

    }

    std::cout << std::endl << sum << std::endl;
    std::cout << i << std::endl;



    std::cin.ignore();
    return 0;

}


double ModPow(int b, int e, long double m) {

    double c = 1;

    for(int i = 1; i <= e; i++) {
        c = fmod(c*b,m);
    }


    return c;
}

Here, I can see that there is strange behavior during the loop still. Logically, the exp should increase by one each time as I keep adding a digit. I see behavior at e+22 and it drops back to e+21, not sure why. Here is the full result of my program (I have made the doubles long doubles, and added file writing but results are the same as code above)

6   76   376   9376   69376   
69376   8.06938e+006   6.80694e+007   6.68069e+008   5.66807e+009   
5.66807e+009   2.05668e+011   7.20567e+012   3.72057e+013   8.37206e+014   
6.83721e+015   8.68372e+016   3.86837e+017   4.38684e+018   2.43868e+019   
6.24387e+020   2.62439e+021   8.81371e+022   7.17853e+021   6.67056e+024   
5.66706e+025   2.56671e+026   6.11305e+027   1.49872e+026   7.84562e+029   
8.79213e+030   5.26226e+031   2.66375e+032   7.26638e+033   4.84075e+034   
3.21959e+035   6.35788e+036   6.73897e+037   6.73897e+037   6.73897e+037   
2.62589e+038   2.98945e+041   2.98945e+041   6.02989e+043   9.17698e+044   
7.16921e+045   7.05229e+046   6.70523e+047   6.5113e+048   4.65113e+049   
8.52121e+050   3.85212e+051   7.38521e+052   4.19563e+053   5.91881e+054   
4.39205e+055   3.9345e+056   9.04097e+057   9.04097e+057   3.68596e+059   
1.49612e+060   7.7534e+061   7.39705e+061   4.22204e+063   6.98596e+063   
6.92886e+065   4.69289e+066   8.22986e+067   1.82299e+068   9.1823e+069   
7.54478e+070   1.14456e+071   4.11446e+072   3.62523e+073   9.90302e+074   
1.92488e+075   4.59175e+076   5.88549e+077   1.35968e+078   6.13597e+079   
6.6136e+080   4.66136e+081   7.48063e+082   6.12132e+083   8.8392e+084   
7.86463e+085   6.94822e+086   6.32933e+087   5.62433e+088   6.56243e+089   
2.3548e+090   5.60251e+090   7.14338e+091   9.90736e+093   6.14551e+094   
5.791e+095   2.5791e+096   5.12015e+097   1.81734e+098   3.08347e+099   
4.30835e+100   4.43083e+101   9.44308e+102   8.62251e+103   4.79117e+104   
4.47912e+105   4.70365e+106   6.26271e+107   9.63625e+108   1.34535e+109   
2.5938e+110   4.77635e+110   7.92388e+112   2.33449e+113   9.38763e+114   
1.74483e+115   4.23631e+116   3.8324e+117   3.10928e+118   8.8341e+119   
9.80234e+120   5.28235e+121   4.52823e+122   8.69571e+123   7.59308e+124   
6.61087e+123   8.34403e+126   8.26135e+127   3.82614e+128   6.83699e+128   
5.48343e+130   7.05731e+131   2.02676e+132   1.20268e+133   3.72264e+134   
4.37226e+135   5.43723e+136   1.68563e+137   9.63719e+138   3.70399e+139   
1.84462e+140   6.61036e+141   4.66104e+142   3.85213e+143   2.38521e+144   
7.39926e+145   4.95209e+146   2.70772e+147   1.27077e+148   9.49987e+149   
6.39539e+150   9.72139e+151   5.89019e+152   7.15679e+153   7.15679e+153   
3.38172e+154   5.84268e+156   9.72579e+157   4.87575e+158   5.6501e+159   
1.85286e+160   4.18529e+161   4.60739e+162   7.12977e+163   5.71298e+164   
8.86201e+165   7.8862e+166   5.82415e+167   4.61194e+168   8.46119e+169   
7.95321e+170   9.01956e+171   7.90196e+172   1.40488e+173   2.38969e+174   
9.12607e+175   8.5208e+176   2.61635e+177   7.26163e+178   1.87538e+179   
6.18754e+180   6.6906e+181   2.05665e+182   3.79061e+183   4.37906e+184   
4.43791e+185   9.87813e+186   1.98781e+187   7.03446e+188   1.57091e+189   
5.7816e+190   7.57816e+191   2.1734e+191   3.5815e+193   9.77689e+194   
8.97769e+195   1.08115e+196   5.10812e+197   4.6079e+198   4.46079e+199   
5.44608e+200   3.69583e+201   3.36958e+202   1.94715e+203   9.19309e+204   
1.7556e+205   9.45675e+206   5.94568e+207   6.45002e+208   9.11561e+209   
1.17058e+210   8.60292e+211   7.86029e+212   2.48236e+213   1.2582e+214   
6.04576e+215   9.60458e+216   4.34447e+217   5.43445e+218   8.42133e+219   
9.84213e+220   1.8562e+221   8.38891e+221   1.08389e+223   7.01599e+223   
1.07016e+225   3.10702e+226   4.3107e+227   1.50548e+228   1.06711e+229   
8.65791e+230   9.86579e+231   8.18076e+232   2.68057e+232   1.85488e+234   
1.85488e+234   2.26339e+236   4.66336e+237   6.27494e+238   5.24964e+239   
3.52496e+240   2.99353e+240   9.96218e+242   8.99622e+243   4.9693e+243   
1.33007e+245   3.78439e+246   1.99925e+247   8.51404e+248   8.47445e+249   
2.95141e+250   7.13201e+251   1.7132e+252   9.76862e+253   9.36726e+254   
3.92421e+255   6.39242e+256   8.42555e+256   4.87969e+258   4.09894e+259   
2.17963e+260   1.61217e+261   8.27277e+261   4.08273e+263   4.53756e+264   
9.67271e+265   9.67271e+265   9.19793e+267   1.91979e+268   2.52109e+267   
5.12996e+270   6.60659e+271   9.64583e+272   6.96458e+273   3.07557e+274   
7.59723e+275   4.30703e+276   6.07449e+277   2.87595e+278   5.82907e+279   
4.59589e+279   2.07609e+281   6.20761e+282   9.17199e+283   5.9172e+284   
5.9172e+284   7.05917e+286   6.70229e+287   2.67023e+288   6.26707e+289   
8.62671e+290   1.86267e+291   7.18627e+292   7.18627e+292   6.07186e+294   
8.60719e+295   8.60719e+295   5.08607e+297   1.50861e+298   7.15086e+299   
7.15086e+299   1.07151e+301 

Answer 1

You want a solution that doesn't directly involve just doing 2**1000? Well, we can do it manually. How many digits does 2**1000 have? Definitely at most 1,000.

Thus:

int sum_digits(int e) {
    std::vector<int> digits(e);
    digits[0] = 1;
    int last_digit = 1;

    for (int power = 0; power < e; ++power) {
        int carry = 0;
        for (int idx = 0; idx < last_digit; ++idx) {
            int prod = digits[idx] * 2 + carry;
            if (prod > 9) {
                carry = 1;
                prod -= 10;
            }
            else {
                carry = 0;
            }
            digits[idx] = prod;
        }

        if (carry) {
            digits[last_digit++] = 1;
        }
    }

    // then just sum 'em  
    return std::accumulate(digits.begin(), digits.end(), 0);
}

That's pretty quick and obviously correct. Sure the big-Oh time isn't great, but for powers of 1000, 10k, and 100k coliru gives me the answer 0.4ms, 28ms, and 2.8s. Not bad for grade school math?

Answer 2

You mentioned Lua. So I gather you're free to choose a programming language. Then why not simply pick a language that supports big numbers? You say "It completely avoids the point of the exercise, which is to understand the math behind the problem and solve it using an algorithm", but the algorithms you got so far are just "brute force". I don't see too much merit in them.

Whatever, in Ruby it's:

(2**1000).to_s.chars.map(&:to_i).reduce(:+)

this gives 1366.

To verify the result I also tried it in giac:

s:=convert(2^1000,string)
sum(expr(mid(s,n,1)), n, 0, length(s)-1)

(gives 1366 too.)

Turns out I didn't have to: WolframAlpha too can solve it.