Total numbers resulting from exponential

Question

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

The idea is simple when the number is relatively small. Given the base and power, the program should summarize the numbers of the result. Let me use an example to explain what I want to do.

base 2 and power 8 and, therefore, 2^8 = 256 , then the program should summarize the digits of the answer like 2+5+6 = 13 , and this is the whole point to find the sum of the digits of the result of the base raised to the power.

Now, this is a simple example, if I turn to a ridiculously huge number, say, 2 ^ 1000, it is almost impossible to just throw in something that I tried, because we lose accuracy because the result is huge and truncated. The answer must be accurate.

I thought that maybe there is a mathematical way to do it differently, somehow break it into small chunks, but in fact I can’t think of any relationship other than:

2^1000 = 2^500*2^500

1000 log(2) = log(ans)

In any case, this does not lead me to anything but numbers, as a result, I can start the summation.

I hope that I have explained this clearly.

For what it's worth, I use C ++ (and gave lua a shot too), and maybe I could use a library, but this number would have 302 bits, and I have to write my program to handle the 1000 index. I really think that I am missing a mathematical trick here.

EDIT Partial Solution Found

I spent a little time getting lua to try to solve this problem today, and today I will give him the opportunity to see C ++ to see if I get different results. I can find the source of the error, but I found a solution that works in most cases. Just not for 2 ^ 1000, but some other indicators with very large numbers.

A description of the solution is described and a comment from MooseBoys.

I use 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 is the result.
You can imagine that printing each result from a mod cycle should be something like

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

I put print (0) there when the check detects the beginning of 0, otherwise prints the value c. You can see each first digit will be added to give the correct amount. Each blank line should contain the previous line plus a new digit, as basically a growing heading.

However, the problem that I can’t solve is now that I am distributing it to a large number, say, a solution for which I am a cam. 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 example, is the same as if you listed the first digits going back in the list: 7.1508607186267e+299

7 15086071862

Being excited, I found the answer wrong. I looked deeper on 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...? 

It seems that there are several areas where this happens, and only on exhibitors more than 200 pieces .. I checked with 100, and it was perfect. noticed errors in 200, such as

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

Does anyone have any new tips on what might be the problem? (sorry my lua interperter may be different, not sure about lua at all. I just use the IDE that is used for game scripts)

Ok, take a closer look. My C ++ program does a great job, and here is the code for it. Still getting the wrong answer, but at least I get the same numbers. I can't seem to understand what is wrong with this. The fact is that this exercise is on the website, I don’t know the right answer, just so that my program gives me the wrong answer for 2 ^ 1000. It passes the other test cases that I give them (those that I can do manually and check the answer 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 see that weird behavior is observed during the cycle. Logically, exp should increase by one every time I keep adding a digit. I see the behavior at e + 22, and he returns to e + 21, not knowing why. Here is the full result of my program (I did double long doubles and added a file entry, but the results are the same as the 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

Do you need a solution that is not directly related to doing 2**1000 ? Well, we can do it manually. How many digits does 2**1000 ? Definitely no more than 1000.

In this way:

 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); } 

This is pretty fast and obviously correct. Of course, the great time Oh is not great, but for powers of 1000, 10k and 100k, coliru gives me an answer of 0.4 ms, 28 ms and 2.8 s. Not bad for high school math?

Answer 2

You mentioned Lua. Therefore, I understand that you are free to choose a programming language. Then why not just pick a language that supports large numbers? You say: “This completely eliminates the point of the exercise, which is to understand the mathematics behind the problem and solve it using an algorithm,” but the algorithms you have received so far are just “brute force.” I do not see in them too many advantages.

Whatever the case, in Ruby it is:

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

this gives 1366.

To check the result, I also tried it in giac:

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

(also gives 1366).

It turns out I do not need: WolframAlpha can also solve the problem.

Answer 3

For exhibitors up to 1000, you really don't need to do anything extraordinary. Here's an example in Python, it computes it instantly. Creating large C ++ integers that support addition and multiplication is very simple, and with these two commands you can implement power in O(n log n) arithmetic operations.

 >>> sum(int(x) for x in str(2**10000)) 13561 

Edit: I missed the fact that the number itself will have 300 digits. This is still good for modern computers, here is an example of calculating the number of digits in a number, which is the result of raising a number consisting of 300 2s by the 1000th power:

 >>> sum(int(x) for x in str(int("2" * 300)**1000)) 1347957 

Still calculating pretty fast