title: What is the sum of the digits of the number 2^1000?
body: <p>This is a <a href="http://projecteuler.net/problem=16" rel="noreferrer">problem</a> from <a href="http://projecteuler.net/" rel="noreferrer">Project Euler</a>, 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. </p>
  
  <p>The problem reads as follows:</p>
  
  <blockquote>
    <p>2^15 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.</p>
    
    <p>What is the sum of the digits of the number 2^1000?</p>
  </blockquote>
  
  <p>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. </p>
  
  <p>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:</p>
  
  <pre><code>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) &lt; 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();
          }
      }
  }
  </code></pre>
  
  <p>It seems to work perfectly for powerOfTwo &lt; 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.</p>
  
  <p>For the actual calculation I am supposed to perform, I get the output:</p>
  
  <blockquote>
    <p>Power of two: 1000 Sum of digits: 1189</p>
  </blockquote>
  
  <p>But 1189 isn't the right answer. What is wrong with my program? I am open to any and all constructive criticisms.</p>