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

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[400];
        //Just a wild guess about the number of digits that 2 ^ 1000 will have

        arr[0] = 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);
    }
}

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))

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

Hi Kristian,

can you please post solution in C

thanks.

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…

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
(Reference added: System.Numerics)
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

#include
using namespace std;

main(){
int a[400]={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;
}

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

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)

#include<iostream.h>

int main(){
	int i, j, arr[1000];
	for(i=0; i<999; i++){
			 arr[i]=0;
	}
	arr[999]=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;
}