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

Normal int can't help you with such a large number. Not even long. They are never designed to handle numbers such huge. int can store around 10 digits (exact max: 2,147,483,647) and long for around 19 digits (exact max: 9,223,372,036,854,775,807). However, A quick calculation from built-in Windows calculator tells me 2^1000 is a number of more than 300 digits.

(side note: the exact value can be obtained from int.MAX_VALUE and long.MAX_VALUE respectively)

As you want precise sum of digits, even float or double types won't work because they only store significant digits for few to some tens of digits. (7 digit for float, 15-16 digits for double). Read here for more information about floating point representation, double precision

However, C# provides a built-in arithmetic BigInteger for arbitrary precision, which should suit your (testing) needs. i.e. can do arithmetic in any number of digits (Theoretically of course. In practice it is limited by memory of your physical machine really, and takes time too depending on your CPU power)

---

Back to your code, I think the problem is here

Math.Pow(2, powerOfTwo)

This overflows the calculation. Well, not really, but it is the double precision is not precisely representing the actual value of the result, as I said.

Answer 2

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.

Answer 3

A solution without using the BigInteger class is to store each digit in it's own int and then do the multiplication manually.

static void Problem16()
{
    int[] digits = new int[350];

    //we're doing multiplication so start with a value of 1
    digits[0] = 1;
    //2^1000 so we'll be multiplying 1000 times
    for (int i = 0; i < 1000; i++)
    {
        //run down the entire array multiplying each digit by 2
        for (int j = digits.Length - 2; j >= 0; j--)
        {
            //multiply
            digits[j] *= 2;
            //carry
            digits[j + 1] += digits[j] / 10;
            //reduce
            digits[j] %= 10;
        }
    }

    //now just collect the result
    long result = 0;
    for (int i = 0; i < digits.Length; i++)
    {
        result += digits[i];
    }

    Console.WriteLine(result);
    Console.ReadKey();
}

Answer 4

I used bitwise shifting to left. Then converting to array and summing its elements. My end result is 1366, Do not forget to add reference to System.Numerics;

BigInteger i = 1;
         i = i << 1000;
        char[] myBigInt = i.ToString().ToCharArray();
        long sum = long.Parse(myBigInt[0].ToString());
        for (int a = 0; a < myBigInt.Length - 1; a++)
        {
            sum += long.Parse(myBigInt[a + 1].ToString());
        }
        Console.WriteLine(sum);

Answer 5

since the question is c# specific using a bigInt might do the job. in java and python too it works but in languages like c and c++ where the facility is not available you have to take a array and do multiplication. take a big digit in array and multiply it with 2. that would be simple and will help in improving your logical skill. and coming to project Euler. there is a problem in which you have to find 100! you might want to apply the same logic for that too.

Answer 6

Try using BigInteger type , 2^100 will end up to a a very large number for even double to handle.

Answer 7

BigInteger bi= new BigInteger("2"); 
bi=bi.pow(1000); 
// System.out.println("Val:"+bi.toString()); 
String stringArr[]=bi.toString().split(""); 
int sum=0; 
for (String string : stringArr) 
{ if(!string.isEmpty()) sum+=Integer.parseInt(string); } 
System.out.println("Sum:"+sum);
------------------------------------------------------------------------
output :=> Sum:1366

Answer 8

Here's my solution in JavaScript

(function (exponent) {
  const num = BigInt(Math.pow(2, exponent))
  let arr = num.toString().split('')
  arr.slice(arr.length - 1)
  const result = arr.reduce((r,c)=> parseInt(r)+parseInt(c))
  console.log(result)
})(1000)

Answer 9

This is not a serious answer—just an observation.

Although it is a good challenge to try to beat Project Euler using only one programming language, I believe the site aims to further the horizons of all programmers who attempt it. In other words, consider using a different programming language.

A Common Lisp solution to the problem could be as simple as

(defun sum_digits (x)
    (if (= x 0)
        0
        (+ (mod x 10) (sum_digits (truncate (/ x 10))))))

(print (sum_digits (expt 2 1000)))

Answer 10

 main()
 {
   char c[60];
  int k=0;
     while(k<=59)
      {
    c[k]='0';
   k++;

    }
       c[59]='2';
       int n=1;
     while(n<=999)
       {
       k=0;
     while(k<=59)
      {
        c[k]=(c[k]*2)-48;
        k++;
      } 
    k=0;
     while(k<=59)
        {
        if(c[k]>57){ c[k-1]+=1;c[k]-=10;   }
       k++;
         }
       if(c[0]>57)
        {
         k=0;
         while(k<=59)
           {
         c[k]=c[k]/2;
          k++;
           }
           printf("%s",c);
             exit(0);
           }

            n++;
            }
          printf("%s",c);
              } 

Answer 11

Python makes it very simple to compute this with an oneliner:

print sum(int(digit) for digit in str(2**1000))

or alternatively with map:

print sum(map(int,str(2**1000)))