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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s