Project Euler Problem 16 Solution: Power digit sum

Project Euler Problem 16 Statement

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the digit sum for the number 2¹⁰⁰⁰ ?

Solution

Using arbitrary–precision integer arithmetic

print (sum(map(int, str(pow(2, 1000)))))

Text with a dashed underscore will highlight the code section being talked about when moused over or tapped.

Python natively supports arbitrary–precision integers and arithmetic using as many digits as there is available memory to perform a calculation. We use that feature to our full advantage to provide a simple solution to this problem.

To solve this problem, we calculate 2¹⁰⁰⁰ (302 digits long) and convert the result to a string so we can iterate over each character–digit (integers are not iterable, but strings are).

Then, using the map function, we iterate over the string and convert every character–digit back to an integer using the int function. Finally, we calculate a digit sum by adding them together using the sum function.

"Old School" without Python arbitrary–precision integers

We can calculate the powers of 2 by successively multiplying each power (starting with 1) by 2, and generating the series 1, 2, 4, 8, 16, 32 ... 2¹⁰⁰⁰. Each power is broken apart digit-by-digit and pushed onto the list, [digits]. This will result in the power being stored in reverse order, but that doesn't affect the digit-sum.

Pay attention to how the variable carry works in this algorithm; it can have only values of 0 or 1. Each carry with a value of 1 indicates a new decimal magnitude transition such as 2⁶=64 to 2⁷=128, 2⁹=512 to 2¹⁰=1024, and so on.

This serves an important purpose: It increases the length of the list by appending a one to the end which acts as a placeholder for the next power of 2.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 16

HackerRank Project Euler 16 requires a little more scale by having you to solve up to 100 test cases with a higher limit for 2ⁿ, where n ≤ 10,000. The first solution handles this easily without any changes.

If we choose the "old school" method, then we are required to cache all the digit-sums for the powers of 2 up to 2¹⁰⁰⁰⁰. A separate loop would host each query and simply print the answer from the cache, which is indexed by the query's value.

Python Source Code

n = int(input("2's exponent? "))
digits = [1]
for _ in range(n):
    carry = 0;
    for i,dx in enumerate(digits):
        d = 2*dx + carry
        carry, digits[i] = divmod(d,10)
    if carry>0:
        digits.append(1)
print ("Sum of the digits of 2 ^", n, " = ", sum(digits))

Run Project Euler Problem 16 using Python on repl.it.

Last Word

Using native language arbitrary–precision structures.

Simply embrace the power of arbitrary–precision integers and ignore the call to solve it in some primitive way. It’s evolution – get used to it.