What is the sum of the digits of the number 2^1000? More...

#include <iostream>

Detailed Description

What is the sum of the digits of the number 2^1000?

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?

Definition in file 016.cpp.

Function Documentation

int main ( )

C++ types:
unsigned long: up to $2^{32}-1 \sim 10^{9.63}$
unsigned long long: up to $2^{64}-1 \sim 10^{19.27}$

$2^{1000}=256^{125}$

so multiply 256 by 125 times Since $2^{1000}\sim 10^{301}$ which has 302 digits, it is split to a number of segments.

Let x be the number in one segment,

$256x<2^{64} \Rightarrow x<=2^{56} \Rightarrow x <= 10^{16}$

each segments should contains at most 16 digits.

So there are a total of $302/16<=19 $ segments.

First multiply each segments by 256, then raise the "carry" digits to next segments.

Definition at line 71 of file 016.cpp.