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

Comments are closed