Project Euler No.16

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 ....
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#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
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.
Can You Explain farther more ??
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.
Last edited on
@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.
> 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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#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' ;
}
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.
Last edited on
>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



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.
Topic archived. No new replies allowed.