What is the sum of the digits of the number 2^1000?

Question

This is a problem from Project Euler, and this question includes some source code, so consider this your spoiler alert, in case you are interested in solving it yourself. It is discouraged to distribute solutions to the problems, and that isn't what I want. I just need a little nudge and guidance in the right direction, in good faith.

The problem reads as follows:

2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2^1000?

I understand the premise and math of the problem, but I've only started practicing C# a week ago, so my programming is shaky at best.

I know that int, long and double are hopelessly inadequate for holding the 300+ (base 10) digits of 2^1000 precisely, so some strategy is needed. My strategy was to set a calculation which gets the digits one by one, and hope that the compiler could figure out how to calculate each digit without some error like 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();
        }
    }
}

It seems to work perfectly for powerOfTwo < 34. My calculator ran out of significant digits above that, so I couldn't test higher powers. But tracing the program, it looks like no overflow is occurring: the number of digits calculated gradually increases as powerOfTwo = 1000 increases, and the sum of digits also (on average) increases with increasing powerOfTwo.

For the actual calculation I am supposed to perform, I get the output:

Power of two: 1000 Sum of digits: 1189

But 1189 isn't the right answer. What is wrong with my program? I am open to any and all constructive criticisms.

Answer 1

For calculating the values of such big numbers you not only need to be a good programmer but also a good mathematician. Here is a hint for you, there's familiar formula a^x = e^{x ln a} , or if you prefer, a^x = 10^{x log a}.

More specific to your problem 2¹⁰⁰⁰ Find the common (base 10) log of 2, and multiply it by 1000; this is the power of 10. If you get something like 10^53.142 (53.142 = log 2 value * 1000) - which you most likely will - then that is 10⁵³ x 10^0.142; just evaluate 10^0.142 and you will get a number between 1 and 10; and multiply that by 10⁵³, But this 10⁵³ will not be useful as 53 zero sum will be zero only.

For log calculation in C#

Math.Log(num, base);

For more accuracy you can use, Log and Pow function of Big Integer.

Now rest programming help I believe you can have from your side.