对指数产生的数字求和
Sum digits that result from an exponential
我正在做一个练习，似乎更多地被困在如何从数学上而不是从句法上解决问题上。
当数字相对较小时，这个想法很简单。给定基数和幂，程序应该对结果的数字求和。让我们用一个例子来解释我想做什么。
base 2 and power 8 给出，因此
2^8 = 256 然后程序应该对答案的数字求和
2+5+6 = 13 这就是重点，求基数的幂结果的位数之和。
现在，这是一个简单的例子，如果我移动到一个非常大的数字，比方说 2^1000，这几乎不可能只是投入我尝试过的任何东西，因为我们失去了精度，因为结果是巨大并被截断。答案必须准确。
我想也许有一种数学方法可以以不同的方式做到这一点，以某种方式将它分解成更小的块，但实际上我想不出除了以下之外的任何关系：
2^1000 = 2^500*2^500
1000 log(2) = log(ans)
无论哪种方式，这都无法让我在可以开始求和的结果中接近数字。
希望我解释清楚了。
为了它的价值，我正在使用 C++（也尝试了 lua），也许我可以使用一个库，但这个数字有 302 位，我应该编写我的程序来处理1000 的指数。我真的认为我在这里遗漏了一些数学技巧。
找到编辑部分解决方案
今天我花了一点时间 lua 试图解决这个问题，今晚我会用 C++ 试一试，看看是否会得到不同的结果。我可以找到错误的根源，但我找到了适用于大多数情况的解决方案。只是不适用于 2^1000 和其他一些非常大的指数。
描述的解决方案和 MooseBoys 的评论。
我使用 mod 平方幂。 lua 代码如下：
-- 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)
问题出在结果上。
您可以想象，打印 mod 循环的每个结果应该类似于
Value: 1048576
6
76
576
8576
48576
0
1048576
sum: 31
当支票检测到前导 0 时，我将 print(0) 放在那里，否则，打印 c 的值。你可以看到，每个第一位数字都会被添加以给出正确的总和。每行应包含前一行加上新数字，基本上就像一个不断增长的标题。
但是，现在我无法解决的问题是当我将其扩展到大量时，让我们说一下我想要的解决方案。 2^1000..
结果：（健康线，接近尾声）
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
例如，最后一行与您列出列表中倒退的第一位数字相同：
7.1508607186267e+299
7 15086071862
一激动，发现答案不对。我更深入地查看了线条，发现了这些不健康的线条：
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...?
似乎有几个区域会发生这种情况，并且仅在指数超过 200ish 时发生。我检查了 100，它是完美的。注意到 200 中的错误，例如
2.9937827928353e+018
0
2.0299378279284e+020
2.2029937827928e+021
7.8493010541604e+022
5.0206666406882e+023
0
3.384239167984e+025
有人对可能出现的问题有任何新提示吗？
（抱歉，我的 lua interperter 可能不同，一般情况下不确定 lua..
我只是使用一个用于游戏脚本的 IDE)
好的，越来越近了。我的 C++ 程序可以更好地处理事情，这里是它的代码。仍然得到错误的答案，但至少我得到了相同数量的数字。我现在似乎无法弄清楚这有什么问题。问题是，这个练习是在一个网站上进行的，我不知道正确答案，只是我的程序给出了 2^1000 的错误答案。它通过了我给它的其他测试用例（我可以手动完成并检查最多 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;
}
在这里，我可以看到循环期间仍然存在奇怪的行为。从逻辑上讲，随着我不断添加数字，每次 exp 都应该增加 1。我在 e+22 处看到了行为，然后又回到了 e+21，不知道为什么。这是我的程序的完整结果（我做了双打长双打，并添加了文件写入，但结果与上面的代码相同）
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
对于高达 1000 的指数，您真的不需要做任何特别的事情。这是 Python 中的一个例子，它是即时计算的。在 C++ 中构建支持加法和乘法的大整数非常简单，只需使用这两个命令，您就可以在 O(n log n) 算术运算中实现强大的功能。
>>> sum(int(x) for x in str(2**10000))
13561
编辑：忽略了号码本身有 300 位的事实。对于现代计算机来说还是没问题的，下面是一个计算一个数的位数的例子，它是将一个由 300 个 2 组成的数提高到 1000 次方的结果：
>>> sum(int(x) for x in str(int("2" * 300)**1000))
1347957
仍然计算得很快
您想要一个不直接涉及 2**1000 的解决方案吗？好吧，我们可以手动完成。 2**1000 有多少位数？绝对最多 1,000。
因此：
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);
}
这很快而且显然是正确的。当然 big-Oh 时间不是很好，但是对于 1000、10k 和 100k 的幂，coliru 给出了 0.4ms、28ms 和 2.8s 的答案。小学数学还不错？
您提到了 Lua。所以我想你可以自由选择一种编程语言。那为什么不简单地选择一种支持大数字的语言呢？你说 "It completely avoids the point of the exercise, which is to understand the math behind the problem and solve it using an algorithm"，但你目前得到的算法只是 "brute force"。我看不出他们有什么优点。
无论如何，在 Ruby 中是：
(2**1000).to_s.chars.map(&:to_i).reduce(:+)
这给出了 1366。
为了验证结果我也在giac中试了一下：
s:=convert(2^1000,string)
sum(expr(mid(s,n,1)), n, 0, length(s)-1)
（也给出 1366。）
原来我不用:WolframAlpha也能解决
我正在做一个练习，似乎更多地被困在如何从数学上而不是从句法上解决问题上。
当数字相对较小时，这个想法很简单。给定基数和幂，程序应该对结果的数字求和。让我们用一个例子来解释我想做什么。
base 2 and power 8 给出，因此
2^8 = 256 然后程序应该对答案的数字求和
2+5+6 = 13 这就是重点，求基数的幂结果的位数之和。
现在，这是一个简单的例子，如果我移动到一个非常大的数字，比方说 2^1000，这几乎不可能只是投入我尝试过的任何东西，因为我们失去了精度，因为结果是巨大并被截断。答案必须准确。
我想也许有一种数学方法可以以不同的方式做到这一点，以某种方式将它分解成更小的块，但实际上我想不出除了以下之外的任何关系：
2^1000 = 2^500*2^500
1000 log(2) = log(ans)
无论哪种方式，这都无法让我在可以开始求和的结果中接近数字。
希望我解释清楚了。
为了它的价值，我正在使用 C++（也尝试了 lua），也许我可以使用一个库，但这个数字有 302 位，我应该编写我的程序来处理1000 的指数。我真的认为我在这里遗漏了一些数学技巧。
找到编辑部分解决方案
今天我花了一点时间 lua 试图解决这个问题，今晚我会用 C++ 试一试，看看是否会得到不同的结果。我可以找到错误的根源，但我找到了适用于大多数情况的解决方案。只是不适用于 2^1000 和其他一些非常大的指数。
描述的解决方案和 MooseBoys 的评论。
我使用 mod 平方幂。 lua 代码如下：
-- 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)
问题出在结果上。
您可以想象，打印 mod 循环的每个结果应该类似于
Value: 1048576
6
76
576
8576
48576
0
1048576
sum: 31
当支票检测到前导 0 时，我将 print(0) 放在那里，否则，打印 c 的值。你可以看到，每个第一位数字都会被添加以给出正确的总和。每行应包含前一行加上新数字，基本上就像一个不断增长的标题。
但是，现在我无法解决的问题是当我将其扩展到大量时，让我们说一下我想要的解决方案。 2^1000..
结果：（健康线，接近尾声）
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
例如，最后一行与您列出列表中倒退的第一位数字相同：
7.1508607186267e+299
7 15086071862
一激动，发现答案不对。我更深入地查看了线条，发现了这些不健康的线条：
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...?
似乎有几个区域会发生这种情况，并且仅在指数超过 200ish 时发生。我检查了 100，它是完美的。注意到 200 中的错误，例如
2.9937827928353e+018
0
2.0299378279284e+020
2.2029937827928e+021
7.8493010541604e+022
5.0206666406882e+023
0
3.384239167984e+025
有人对可能出现的问题有任何新提示吗？ （抱歉，我的 lua interperter 可能不同，一般情况下不确定 lua.. 我只是使用一个用于游戏脚本的 IDE)
好的，越来越近了。我的 C++ 程序可以更好地处理事情，这里是它的代码。仍然得到错误的答案，但至少我得到了相同数量的数字。我现在似乎无法弄清楚这有什么问题。问题是，这个练习是在一个网站上进行的，我不知道正确答案，只是我的程序给出了 2^1000 的错误答案。它通过了我给它的其他测试用例（我可以手动完成并检查最多 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;
}
在这里，我可以看到循环期间仍然存在奇怪的行为。从逻辑上讲，随着我不断添加数字，每次 exp 都应该增加 1。我在 e+22 处看到了行为，然后又回到了 e+21，不知道为什么。这是我的程序的完整结果（我做了双打长双打，并添加了文件写入，但结果与上面的代码相同）
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
对于高达 1000 的指数，您真的不需要做任何特别的事情。这是 Python 中的一个例子，它是即时计算的。在 C++ 中构建支持加法和乘法的大整数非常简单，只需使用这两个命令，您就可以在 O(n log n) 算术运算中实现强大的功能。
>>> sum(int(x) for x in str(2**10000))
13561
编辑：忽略了号码本身有 300 位的事实。对于现代计算机来说还是没问题的，下面是一个计算一个数的位数的例子，它是将一个由 300 个 2 组成的数提高到 1000 次方的结果：
>>> sum(int(x) for x in str(int("2" * 300)**1000))
1347957
仍然计算得很快
您想要一个不直接涉及 2**1000 的解决方案吗？好吧，我们可以手动完成。 2**1000 有多少位数？绝对最多 1,000。
因此：
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);
}
这很快而且显然是正确的。当然 big-Oh 时间不是很好，但是对于 1000、10k 和 100k 的幂，coliru 给出了 0.4ms、28ms 和 2.8s 的答案。小学数学还不错？
您提到了 Lua。所以我想你可以自由选择一种编程语言。那为什么不简单地选择一种支持大数字的语言呢？你说 "It completely avoids the point of the exercise, which is to understand the math behind the problem and solve it using an algorithm"，但你目前得到的算法只是 "brute force"。我看不出他们有什么优点。
无论如何，在 Ruby 中是：
(2**1000).to_s.chars.map(&:to_i).reduce(:+)
这给出了 1366。
为了验证结果我也在giac中试了一下：
s:=convert(2^1000,string)
sum(expr(mid(s,n,1)), n, 0, length(s)-1)
（也给出 1366。）
原来我不用:WolframAlpha也能解决