数字2 ^ 1000的数字总和是多少？

Question

这是一个问题,从项目欧拉,而这个问题包括一些源代码,所以认为这您的扰流板警报,如果你有兴趣自己解决它.不鼓励为问题分配解决方案,这不是我想要的.我真诚地需要在正确的方向上进行一点点推动和指导.

问题如下:

2 ^ 15 = 32768,其数字之和为3 + 2 + 7 + 6 + 8 = 26.

数字2 ^ 1000的数字总和是多少？

我理解问题的前提和数学,但我一周前才开始练习C#,所以我的编程充其量只是摇摇欲坠.

我知道int,long和double绝对不足以准确地保持2 ^ 1000的300+(基数10)数字,所以需要一些策略.我的策略是设置一个逐个获取数字的计算,并希望编译器能够计算出如何计算每个数字而没有像overflow这样的错误:

using System;
using System.IO;
using System.Windows.Forms;

namespace euler016
{
    class DigitSum
    {
        // sum all the (base 10) digits of 2^powerOfTwo
        [STAThread]
        static void Main(string[] args)
        {
            int powerOfTwo = 1000;
            int sum = 0;

            // iterate through each (base 10) digit of 2^powerOfTwo, from right to left
            for (int digit = 0; Math.Pow(10, digit) < Math.Pow(2, powerOfTwo); digit++)
            {
                // add next rightmost digit to sum
                sum += (int)((Math.Pow(2, powerOfTwo) / Math.Pow(10, digit) % 10));
            }
            // write output to console, and save solution to clipboard
            Console.Write("Power of two: {0} Sum of digits: {1}\n", powerOfTwo, sum);
            Clipboard.SetText(sum.ToString());
            Console.WriteLine("Answer copied to clipboard. Press any key to exit.");
            Console.ReadKey();
        }
    }
}

它似乎完全适用于powerOfTwo <34.我的计算器超出了有效数字,所以我无法测试更高的功率.但是跟踪程序,看起来没有发生溢出:计算的位数随着powerOfTwo = 1000的增加而逐渐增加,并且数字的总和也(平均)随着powerOfTwo的增加而增加.

对于我应该执行的实际计算,我得到输出:

2的幂:1000位数:1189

但1189不是正确的答案.我的计划有什么问题？我对所有建设性的批评持开放态度.

Answer 1

为了计算这些大数字的值,你不仅需要成为一名优秀的程序员,还需要一名优秀的数学家.这里有一个提示,有一个熟悉的公式^x = e ^{x ln a},或者如果你愿意,^x = 10 ^{x log a}.

更具体到您的问题2 ¹⁰⁰⁰找到2 的公共(基数10)日志,并将其乘以1000; 这是10的幂.如果你得到10 ^53.142(53.142 = log 2值*1000) - 你最有可能 - 那么这就是10 ⁵³ x 10 ^0.142 ; 只评估10 ^0.142,你会得到1到10之间的数字; 并将其乘以10 ⁵³,但是这个10 ⁵³将没有用,因为53零和将仅为零.

用于C#中的日志计算

Math.Log(num, base);

为了更准确,您可以使用Big Integer的Log和Pow功能.

现在休息编程帮助我相信你可以从你身边.

Answer 2

正常int无法帮助你这么大的数字.不是long.它们从未被设计用于处理如此巨大的数字.int可存储大约10位数字(最大值为:)2,147,483,647和long大约19位数字(最大值为9,223,372,036,854,775,807).但是,内置Windows计算器的快速计算告诉我2^1000数字超过300位.

(边注:可以从所获得的精确值int.MAX_VALUE和long.MAX_VALUE分别)

因为你想要精确的数字总和,偶数float或double类型将不起作用,因为它们只存储少数到几十个数字的有效数字.(7浮点数,15-16双数位).有关浮点表示,双精度的更多信息,请阅读此处

但是,C#提供了BigInteger任意精度的内置算法 ,它应该适合您的(测试)需求.即可以任意数量的数字进行算术运算(理论上当然.实际上它实际上受到物理机器内存的限制,并且取决于你的CPU功率也需要时间)

回到你的代码,我认为问题出在这里

Math.Pow(2, powerOfTwo)

这溢出了计算.嗯,不是真的,但double正如我所说,精确度并不能准确地代表结果的实际价值.