指数计算结果中的数字求和

Question

指数计算结果中的数字求和

6

我正在做一个练习，似乎卡在了如何数学地解决问题上，而不是语法上。这个想法很简单，当数字相对较小时，程序应该给定一个基数和幂，然后计算结果的数字之和。让我们用一个例子来解释我想做什么。

给定基数2和幂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和一些具有非常大数字的指数而言不适用。

我利用了模幂运算。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)

问题在于结果本身。
你可以想象一下，输出模运算的每一个结果就像是：

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...?

看起来这种情况发生在几个领域，而且只在指数大于200左右的情况下发生。我检查了100次，没有问题。但我注意到在200左右的指数中存在错误。

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

有人对问题有新的提示吗？（抱歉，我的lua解释器可能不同，不确定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;
}

在这里，我看到在循环过程中存在奇怪的行为。逻辑上，每添加一个数字，指数应该每次增加一。但是我在 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

- Chemistpp

1

只是一个想法，我并没有真正深入思考过，但我可能是错的。取 2 的 n 次方，最后一位数字将是 2、4、8 或 6。N % 4 分别为 1、2、3 和 0。整个数字中每个数字都存在这样的模式。只需使用这些模式然后将结果数字相加即可。 - Orange Mushroom

1

你是重复将数字相加直到得到一个个位数，还是只加一次？如果是前者，那很简单——只需对所有数字进行模9计算即可。如果是后者，则更难——你可以先计算模9，然后尝试找出要添加到结果中的修正值，以得到正确的单个求和。 - Chris Dodd

知道如何存储这些数字可能会很有用，因为2^1000甚至对于无符号长整型来说也太大了。如果你能以十进制的方式存储它，你就可以简单地将乘数相加，例如256是210^3 + 510^2 + 6*10^1。 - nico

2

使用模数为10^n的模幂运算可能是正确的起点。 - MooseBoys

@MooseBoys 是的，我认为这肯定是正确的方向。我可以获取第一个数字，但是如果我使用mod 100，我会得到第一个和第二个数字。扩展一下，随着我的mod power增加，数字将增长，我会遇到同样的问题。我需要某种方式来捕捉第一个数字后移位其他数字。我想到了一个良好的除法可以去掉额外的数字，但它必须在循环之前或循环中进行，而不仅仅是在循环结果上。然而，我认为这肯定是正确的方向，谢谢。 - Chemistpp

显示剩余8条评论

3个回答

1

您提到了Lua。所以我认为您可以自由选择编程语言。那么为什么不选择支持大数字的语言呢？您说：“这完全避开了问题的重点，即理解问题背后的数学并使用算法解决它”，但是您迄今所得到的算法只是“暴力破解”。我没有看到太多的优点。

无论如何，在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 也可以解决它。

- Niccolo M.

是的，另一个答案也建议了同样的事情。是的，我能够选择我的语言，但是，整个重点不仅在于解决问题，而且在于从每个关于数学、算法和编程的课程中学习东西。 - Chemistpp

-1

对于指数高达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

仍然计算得非常快

- Ishamael

这并不真正回答问题。 - gsamaras

嗯，就我理解的问题而言，是“如何计算数字的总和，因为我认为我不能够朴素地做到”，对此我的回答是“事实上，你可以朴素地做到”。 - Ishamael

1

这不是问题，我不会接受这个作为答案。它完全回避了练习的重点，即理解问题背后的数学原理并使用算法解决它。谢谢。 - Chemistpp

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Barry · Accepted Answer

你想要一种不直接使用“2 ** 1000”来解决的方法吗？我们可以手动计算。"2 ** 1000"最多有几位数呢？显然不超过1000位。

因此：

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

这相当快，显然是正确的。虽然大O时间并不太好，但对于1000、10k和100k的幂，coliru给出的答案分别为0.4ms、28ms和2.8s。对于小学数学来说，这还不错吧？