Problem Description

The series, 1¹ + 2² + 3³ + … + 10¹⁰ = 10405071317.

Find the last ten digits of the series, 1¹ + 2² + 3³ + … + 1000¹⁰⁰⁰.

Analysis

Without Python’s built-in pow() function and native large integer support this may have been more of a challenge. In fact, before revisiting this problem we solved it in Perl with the following code.

$max_n = 1000;
$m = 1e10;
$sum = 0;
 
for $n (1..$max_n) { 
	$nx = 1; 
	$nx = ($nx * $n) % $m  for (1..$n); 
	$sum = ($sum + $nx) % $m; 
}
 
print "PE 48 = $sum";

Solution

Runs < 1 second in Python.

def PE48(limit, m):
    sum = 0
    while limit:
        sum += pow(limit, limit, 10**m)
        limit -= 1
    return sum % 10**m
 
print "Answer to PE48 = ",PE48(1000, 10)

Comments

Note: (a*a*a) % n = ( (a%n) * (a%n) * (a%n) ) % n

• See also problem 97 & problem 188.
• Don’t forget that leading zeros are not printed.
• The last iteration, 1000, would not affect the last 10 digits of the sum, but was included to adhere to the problem description.
• The full answer is 3001 digits.