Project Euler No.16

[CMinus]

Hello , Most of us might solve www.projecteuler.net Problems So Here With Problem 16 that asks to Sum the Digits of 2^1000
I made it but I feel that I am making it too hard for me :)
So here is my Code & Tell me ur opinions , Easier Methods , etc...
Thanks in advance ....

#include <string>
#include <iostream>
using namespace std;


int subtract (short num);
	  int  x[302];


int main ()
{

		x[301]=2;
	for (short power=1;power!=1000;power++)
	{
		for (short arraynum=301;arraynum!=0;arraynum--)
		{
			x[arraynum]=x[arraynum] * 2;
			}
		
		for (short arraynum=301;arraynum!=0;arraynum--)
		{	
			
			if (x[arraynum]>9)
				{
					
					subtract(arraynum);
			    }

		}
		
	}

	int sum=0;
	
		for (short arraynum=301;arraynum!=-1;arraynum--)
		{sum = sum +x[arraynum];
		}
		cout<<sum;

	cin.get();
	
	return 0;

}
int subtract (short num)
{
	if (x[num]>9)
	{
		x[num]=x[num]-10;
		x[num-1]=x[num-1]+1;
		
	}
return 0;}

PS : Please Don;t Tell me about Code Organizing Bcuz I'am bad at that

[ui uiho]

PS : Please Don;t Tell me about Code Organizing Bcuz I'am bad at that

your right. formatting is VERY important. please work on that. also there is a pattern you are missing that could make this alot easier. think of the values of the sum as get power gets higher.

[CMinus]

Can You Explain farther more ??

[ui uiho]

Well you do realize there is a pattern in which powers of 2 go up. There are patterns for all exponential equations like this. Graph 2^x And it becomes more apparent



I know he is counting the digits but there is still a pattern to how the numbers add up.

[Lowest0ne]

@ui uiho: I think C Minus is summing the digits of the power, not the power and all of the powers that came before it.

[JLBorges]

> I made it but I feel that I am making it too hard for me :)

You can make life easier by using the standard library.

#include <cmath>
#include <vector>
#include <iostream>
#include <numeric>

int main()
{
    enum { EXPONENT = 1000 } ;
    const double LOG10 = std::log(10.0) / std::log(2) ;
    const int NDIGITS = int( ( EXPONENT + LOG10 ) / LOG10 )  ;

    std::vector<int> digits( NDIGITS ) ;
    digits.front() = 1 ; // least significant digit is at position 0

    for( int i = 0 ; i < EXPONENT ; ++i )
    {
      int carry = 0 ;
      for( int j = 0 ; j < NDIGITS ; ++j )
      {
          int value = digits[j] + digits[j] + carry ;
          if( value > 9 ) { carry = 1 ; value -= 10 ; }
          else carry = 0 ;
          digits[j] = value % 10 ;
      }
    }
    std::cout << std::accumulate( digits.begin(), digits.end(), 0 ) << '\n' ;
}

[Fumbles]

Looking at the first few:

2
4
8
16 = 7
32 = 5
64 = 1
128 =2
256 =4
512 = 8
1024 =7
2048 =5
4096 = 1
etc.

So we have 2,4,8,7, 5, 1,2,4,8,7,5,1,....

I have no idea if this continues indefinitely (requires a maths proof) but, if it does, we have that:

sumdigit(2^n) =
2 if n is of the form 6k-5
4 if n is of the form 6k-4
8 if n is of the form 6k-3
7 if n is of the form 6k-2
5 if n is of the form 6k-1
1 if n is of the form 6k

1000=6k-2 gives k=167 (all the others give fractional values for k).

Hence the sum of the digits is 7.

P.S: You can adapt the sumdigit part of this for mods. This just gives a program with lots of if(power%6)=this then output that etc.

[CMinus]

>JLBorges In fact I have just read the tutorial here & I am currently reading C++ Primer by Lippman , but my exams (I study Some damn stupid stuff) are eating up my time :)
So I have on my to read list
1- The rest of C++ Primer by Lippman
2- The C++ Standard Library - A Tutorial and Reference by Nicolai

> Fumbles the final answer is 1366

[Fumbles]

I thought you had to keep going until you got a number between 0 and 9.

The only other time i've encountered summing digits is with division by 3. I figured this was an extension of that.