Project Euler Problem #48

Problem #48 is one of the many problems on Project Euler that involves modular arithmetic. The question reads:

Project Euler Problem 48: Self powers
The series, 11 + 22 + 33 + ... + 1010 = 10405071317.
Find the last ten digits of the series, 11 + 22 + 33 + ... + 10001000.

My solution involves a common technique for finding the remainder when a large power is divided by a large mod known as Exponentiation by Squaring. Here’s my solution:

Solution #1: Exponentiation by Squaring Approach

We simply use the exponentiation by squaring approach to find the remainder when each power is divided by 10^10. The remainder when a number is divided by 10^n is the same as the last n digits of the number. Thus, by converting each exponent in the list to binary and then finding the remainder when each square power of the base is divided by 10^10, the Exponentiation by Squaring approach can be used to quickly get an answer. Here is an implementation of this approach in Python 2.7:

 '''
 Author: Walker Kroubalkian
 Exponentiation by Squaring Approach to Project Euler Problem #48
 '''
 
 import time
 
 def lastDigitsPower(a,b,n):
     myMod = 10**n
     total = a
     powers = [a]
     e = 1
     while(e<b):
         total*=total
         total%=myMod
         powers.append(total)
         e*=2
     myBinary = (bin(b)[2:])[::-1]
     final = 1
     for c in range(len(myBinary)):
         if(int(myBinary[c])):
             final*=powers[c]
             final%=myMod
     return final
 
 def projectEulerProblemFortyEight(i,n):
     total = 0
     myMod = 10**n
     for c in range(1,i+1):
         total+=lastDigitsPower(c, c, n)
         total%=myMod
     return total
 
 start = time.time()
 print projectEulerProblemFortyEight(1000, 10)
 print ("--- %s seconds ---" % (time.time()-start))
 
 '''
 Prints
 
 9110846700
 --- 0.00864911079407 seconds ---
 
 for input of i = 1000, n = 10
 '''

As shown above, the Exponentiation by Squaring method can be very effective for dealing with modular arithmetic for large powers. An alternate method may use Euler’s Totient Theorem, but because this question was relatively simple, I decided not to use it for this solution.

Thanks for reading! See you tomorrow.