Problem 048


Project Euler

Self powers

Problem 48

The series, 11 + 22 + 33 + … + 1010 = 10405071317.

Find the last ten digits of the series, 11 + 22 + 33 + … + 10001000.


This problem is working with large number and using Haskell or Python is extremely easy to solve by looping through 1000 number and add up all the powers and find the last ten digits.

However, we can make some improvement of the brute force approach. The first improvement is to use modular arithmetic to ignore any digit beyond the last ten whenever we need to remember a result.

a_1 \equiv b_1 (mod~n)
a_2 \equiv b_2 (mod~n)
a_1 + a_2 \equiv b_1 + b_2 (mod~n)

(a~mod~n)(b~mod~n) \equiv ab~(mod~n)

Another improvement is to implement your own integer power function that incorporate the modular arithmetic with basic property of exponent.

a^{p+1} = a^p \cdot a
a^{pq} = a^p \cdot a^q

Therefore, let a be the base and p be the exponent,

If p is odd, then result = a \cdot a^{p-1}
If p is even, then let result = a^{\frac{p}{2}} and find result*result as the answer.

Let n = 10000000000 and do a modular arithmetic every chance you get to keep the number from overflowing. Unfortunately, even with unsigned long long, the divide and conquer algorithm to calculate exponent still overflow. I used an iterative approach with the modular arithmetic and able to calculate the answer quite quickly.

Advertisements