# Project Euler 16: The sum of digits in 2^1000

Just like the solution to problem 13 the answer to problem 16 of Project Euler has become trivial with .NET 4.0. And since I am lazy I intend to exploit the tools I am given. The problem description reads

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?

If there didn’t exist a BigInteger class in .NET, then we would have needed to implement a way of storing the large result, which would need 1000 bits of storage, or around the size of 32 integers.

## Solution

However, with the class that can hold arbitrarily large in integers the task is trivial, and I decided to solve it in the following way

```int result = 0;

BigInteger number = BigInteger.Pow(2, 1000);

while (number > 0) {
result += (int) (number % 10);
number /= 10;
}
```

I have chosen an implementation where I slice of the last digit in a while loop with the modulo operator. We could have chosen to convert it to a string, split it and convert it back. This just seemed more in line with the Project Euler spirit.

The result of the code is

```The sum og digits of 2^1000 is: 1366
Solution took 0 ms
```

## Wrapping up

Intentionally this was a very short blog post, since I didn’t have much to say.  As usually the source code is available for download here. ### Posted by Kristian Amey Kelkar

Hello Everyone,
I have a simple code in C# which does not make use of BigInteger..
I have not commented about what I have done in code so that you can find out whats going on in the code.. The code is very simple..

```using System;

class mainclass
{
public static void Main(string[] args)
{
int sum = 0;

int[] arr = new int;
//Just a wild guess about the number of digits that 2 ^ 1000 will have

arr = 2;
int carry = 0;

for (int j = 1; j < 1000; j++)
{
for (int i = 0; i < arr.Length; i++)
{
int tempno = arr[i] * 2;

if (tempno > 9)
{
arr[i] = (tempno % 10) + carry;
carry = 1;
}
else
{
arr[i] = tempno + carry;
carry = 0;
}
}
}

for (int i = 0; i < arr.Length; i++)
{
sum += arr[i];
Console.Write(arr[i]);
}

Console.WriteLine();

Console.WriteLine("Sum of Digits = " + sum);
}
}
``` Kristian

Hi Amey

Thanks for the comment and the alternative solution. I always love to see and hear from other people.

I like your solution, since it doesn’t use anything special, so it would be implementable in most traditional languages. On the other hand I have no problems using the tools that the chosen language provides me for solving the problem at hand.

I have made a solution that is somewhat similar, but where I store 14 digits in each array entry. That uses less memory, but you need to chop up each number in the end, so I am not sure whether or not it is better performance wise.

If I should make any comments on the code, I would add the carry in line 19 instead. I know it won’t make any problems, but it seems easier to understand for me.

/Kristian Mark

Hi Kristian,

I have been reading your blog here for a few weeks now and I am so glad I found it. I love your solutions to the problems, here is my version (not as cool as yours).

BigInteger
.Pow(2, 1000)
.ToString()
.Aggregate(0,
(total, next) => total + (int)Char.GetNumericValue(next)) Kristian

Hi Mark

Thanks for the compliment and thanks for sharing your code. I am not very strong with LINQ, so I always enjoy when people are sharing their LINQ solutions with me. That gives me a little to pull from whenever I am trying.

/Kristian Darie

You know, that problem was not meant to be solved with the BigInteger class, unless u can easily implement multiplication of big numbers yourself. Kristian

I only partly agree with you. I know it is close to trivial when you can handle it that way, but given a toolbox you should also use the best available tool to get the job done.

…and yes I can implement multiplication on large integers if needed. Ramesh

Hi Kristian,

can you please post solution in C

thanks. Kristian

No I don’t know C well enough to write solutions in that. But you should be able to program something like Ameys solutions yourself. Mehmet

How about doing it with Binary to BCD (Binary Coded Decimal) conversion?

-pow(2,100) is easy to do with setting the most significant bit of 1
-and then converting the binary bit to BCD bit,
-and after that just summing up decimal values of BCD binary.

As you know each four bits BCD represents each digit of the decimal number.

I wander if it will be faster… Kristian

I am not familiar with that method, but the last question makes me say “try it, compare the results and share it here”. Jean-Marie Hachey

Table 1
Pattern (sequence 7-5-1-2-4-8; period 6) in the distribution of digital roots for 2^p; (p>1).
Re: Project Euler – Problem 16
“Power digit sum”

http://img11.hostingpics.net/pics/139975pe16tab1pwrdig.jpg

______

Sources:
1) Digital root
http://en.wikipedia.org/wiki/Digital_root
2) Modulo operation
http://en.wikipedia.org/wiki/Modulo_operation
3) Pitoun’s sequence: a(n+1) is digital root of a(0)+…+a(n).
http://oeis.org/A029898
(And references cited therein)
4) Kristian’s algorithm for Project Euler – Problem 16
http://www.mathblog.dk/files/euler/Problem16.cs
5) Microsoft Visual C# 2010 Express
6) Big Integer Calculator
http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm
___

Note :
From Ref. 6:
2^100=
1267650600228229401496703205376; 31 digits
Sum of digits: 115
Digital root: 7
http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm Alberto Soto

Here is my approach in C.

```#include &lt;stdio.h&gt;
#define N 1000
#define MAX 400 //Max number of digits of 2^1000

int num[MAX];

int main(){
int i, j, aux, mem = 0, sum = 0;

for(i = 1; i &lt; MAX; i++){
num[i] = 0; //initialize solution array to 0.
}
num = 1; //set solution to 2^0.

for(i=0; i&lt;N; i++){ //We will multiply N times 2.
for(j=0; j&lt;MAX; j++){ //For each digit,
aux = 2*num[j] + mem; //we multiply by 2 and add the mem value.
num[j] = aux%10; //save last digit.
mem = aux/10; //set mem to the rest digits of aux, which only can be 0 or 1.
}
}

for(i=0; i&lt;MAX; i++){ //calculate the sum.
sum += num[i];
}

printf(&quot;Solution: %d\n&quot;, sum);

return 0;
}
``` devil

#include
using namespace std;

main(){
int a={0,1};
int n,i,j;
cin>>n;
for(i=0;i<n;i++){
int carry=0;
for(j=0;j0;i–)
cout<<a[i];
int sum=0;
for(i=0;i<400;i++)
sum=sum+a[i];
cout<<endl<<sum;
} devil

A small code which can calculate the power of 2 upto 2^10000 +….

#include
using namespace std;

main(){
int a={0,1};
int n,i,j;
cin>>n;
for(i=0;i<n;i++){
int carry=0;
for(j=0;j0;i–)
cout<<a[i];
int sum=0;
for(i=0;i<400;i++)
sum=sum+a[i];
cout<<endl<<sum;
} Victor Rodriguez

Has anyone tested Amey’s solution? The expected answer is 21124, but I get 1366 with Amey’s solution. Chaitanya Varier

Hello Kristian,

I have published my own solution to this problem as well as problem #20 on my blog, which I think you might like to look at. My solutions in Java are similar to Amey’s solution and involve constructing BigInteger operations from scratch using arrays.

A link to my Project Euler # 16 solution:
http://chaitanyavarier.com/2015/08/13/pe-16/ NTK Meridional

Here’s the code in python, it can’t get simpler

```number = str(2**1000)
res = 0
for digit in number:
res += int(digit)
print (res)
``` goatcoder
```#include<iostream.h>

int main(){
int i, j, arr;
for(i=0; i<999; i++){
arr[i]=0;
}
arr=1;
//input ends

for(int k=0; k<1000; k++){
i=999;
cout<<"We're here?!!"<<endl;
do{
arr[i]*=2;
i--;
}while(i>=0);
//carry operatons
j=999;
while(j>=0){
if(arr[j]>9){
arr[j-1]+=((arr[j]-(arr[j]%10))/10);
arr[j]%=10;

}
j--;
}
//carry operations end
}
long int sum=0;
for(i=0; i<1000;i++){
sum+=arr[i];
}
cout<<sum;
return 0;
}

``` goatcoder
```#include<iostream.h>

int main(){
int i, j, arr;
for(i=0; i<999; i++){
arr[i]=0;
}
arr=1;
//input ends

for(int k=0; k<1000; k++){
i=999;
do{
arr[i]*=2;
i--;
}while(i>=0);
//carry operatons
j=999;
while(j>=0){
if(arr[j]>9){
arr[j-1]+=((arr[j]-(arr[j]%10))/10);
arr[j]%=10;

}
j--;
}
//carry operations end
}
long int sum=0;
for(i=0; i<1000;i++){
sum+=arr[i];
}
cout<<sum;
return 0;
}

``` n0kia2k7

how mush to use
result+=(number%10);
number/=10;
foreach( var i in number)
result+=i;
??????? why is no one using a double like this is what I tried doing and like a see it isn’t working but can someone please explain why
//
// main.c
// lab
//
// Created by yadin meretzki on 15/04/2019.
//

#include <stdio.h>

int main()
{
double num=2;
int sum=0;
for(int i = 1;i<1001;i++)
{
num=num*2;
}
printf(“%lf”,num);
while(num/10>0)
{
sum+=(int)(num%10);
num=num/10;
printf(“%d”,sum);
}
} why bot use a double why not use a double Felix C

I’ve been programming in C# for a few years and it is not enough anymore for GUI. I’m redoing these problems in Javascript, whose Number type has a upper limit of 2^53 -1, to get myself up to speed with the language

Here’s my code to adding a number (digit by digit) to an array of result

```// let maxPower = 15; let maxPower = 1000; let sol = 0; let ans =  for (let k = 0; k < maxPower ; k++){ let ansCopy = []; for (let m =0; m< ans.length; m++){ ansCopy.push(ans[m]); } for (let m = 0; m < ansCopy.length; m++){ add2Answer(ans, m, ansCopy[m]); } } ```

//if the power of 10 is larger than the max length of the ans array, add the val at the end of and exit the function
if (powerOf10 >= resultArray.length){
while (resultArray.length < powerOf10){ resultArray.push(0); }
resultArray[powerOf10] = val;
return;
}
//add the val of the input argument to the defined position of the ans array;
resultArray[powerOf10] += val;
//carry the extra digit by calling this function recursively
if (resultArray[powerOf10] >= 10){
resultArray[powerOf10] = resultArray[powerOf10]%10;
}
} nikhil

we can use the fact that when multiplying with 2 the carry is always 1 so no need to find carry each time
my code in c++
#include
#include<math.h>
using namespace std;
int main()
{
int arr;
arr=1;
for(int i=1;i<400;i++)
arr[i]=0;
int c=0;
for(int j=0;j<1000;j++)
{
for(int i=0;i<400;++i)
{
arr[i]*=2;
arr[i]+=c;
c=0;
if(arr[i]>9)
{
arr[i]-=10;
c=1;
}
}
}
int sum=0;
for(int i=0;i<400;i++)
sum+=arr[i];
cout<<sum;
return 0;
}