Problem: $2^{15}=32768$ and the sum of its digits is $3+2+7+6+8=26$.
What is the sum of the digits of the number $2^{1000}$?

### Sage Solution

Sage’s built-in Python and functions makes this easy.

import time   start = time.time() a = 2^1000 s = sum(a.digits()) elapsed = time.time() - start   print "%s found in %s seconds" % (s,elapsed)

It executes pretty quickly too.

1366 found in 0.000343084335327 seconds

### An Easy Python Solution

Python itself also makes this problem too easy, due to string functions.

import time   def pow2sum(exp): pow = list(str(2**1000)) return sum([int(i) for i in pow])   start = time.time() n = pow2sum(1000) elapsed = (time.time() - start) print "%s found in %s seconds" % (n,elapsed)

And it is fast:

1366 found in 0.000911951065063 seconds

### Python Without Strings Attached

Let’s do our arithmetic without string functionality. Then, I’d note that $2^{1000}<10^{1000}$ and so we know that, at most, we're dealing with 1001 digits. So, we can create a routine to multiply 2 by itself 1000 times, maintaining the result at each step in a list instead of a single integer. (This is how you'd be forced to do things in C, where arbitrary length integers are pure fiction.) Since we're only multiplying by 2 at each iteration, we know that we'll either carry a zero or one to the next stage... which does make this routine a bit more simple than your typical multiply-by-list routine.

import time   def pow2sum(exp): L = [0] * exp # make a list exp long L[0] = 1 for power in range(exp): carry, add = 0, 0 for index in range(exp): prod = L[index] * 2 + carry if prod > 9: carry = 1 prod = prod % 10 else: carry = 0 L[index] = prod return sum(L)   start = time.time() n = pow2sum(1000) elapsed = (time.time() - start) print "%s found in %s seconds" % (n,elapsed)

It runs relatively quickly, although not as quickly as the string version runs.

1366 found in 0.361020803452 seconds

### Cython Solutions

We can first trivially rewrite the string Python version.

%cython   import time   cdef pow2sum(unsigned int exp): cdef list pow = list(str(2**1000)) return sum([int(i) for i in pow])   start = time.time() n = pow2sum(1000) elapsed = (time.time() - start) print "%s found in %s seconds" % (n,elapsed)

When executed, we find that the string Cython code runs about 1.14 times as fast as the string Python code.

1366 found in 0.000799894332886 seconds

Of course, I’m more interested in seeing how much faster the arithmetic version runs.

%cython   import time from libc.stdlib cimport malloc, free   cdef pow2sum(unsigned int exp): cdef int *L = <int *>malloc(exp * sizeof(int)) cdef unsigned int power = 0,index = 0 cdef unsigned int prod, carry, add while index < exp: L[index] = 0 index += 1 L[0] = 1 while power < exp: carry, add, index = 0, 0, 0 while index < exp: prod = L[index] * 2 + carry if prod > 9: carry = 1 prod = prod % 10 else: carry = 0 L[index] = prod index += 1 power += 1 cdef int sum = 0 index = 0 while index < exp: sum += L[index] index += 1 free(L) return sum   start = time.time() n = pow2sum(1000) elapsed = (time.time() - start) print "%s found in %s seconds" % (n,elapsed)

When executed, we get the following result.

1366 found in 0.00858902931213 seconds