Project Euler # 48 Self powers in Python

Question

The series, \1ドル^1 + 2^2 + 3^3 + \ldots + 10^{10} = 10405071317\$.

Find the last ten digits of the series, \1ドル^1 + 2^2 + 3^3 + \ldots + 1000^{1000}\$.

def self_power(n):
 """returns sum of self powers up to n."""
 total = 0
 for i in range(1, n + 1):
 total += i ** i
 return str(total)[-10:]
if __name__ == '__main__':
 print(self_power(1000))

• Martin R: You got answers to 23 of your 29 questions – is there a reason that you accepted only 3 answers too far? And why don't you tag your questions correctly with [python], as pointed out to you repeatedly?
• user203258: there is no best answer mostly and my questions are tagged with python-3.x.
• 301_Moved_Permanently: And, again, the python-3.x excerpt states, in the first few words, that you should "Use this tag along with the main python tag"...
• user203258: you mean in the description?
• user203258: okay, from now on, all my posts will contain python and python 3.x. Anything else?

Answer 1

You can compute the sum of the powers with sum() and a generator expression:

total = sum(i ** i for i in range(1, n + 1))

instead of a for-loop. Retrieving the last 10 digits can be done with the modulus operator % instead of converting it to a string:

return total % (10 ** 10)

Your code already runs in fractions of a second. For even larger exponents it would be more efficient to compute only the last 10 digits of each intermediate result. This can be done with the three-argument form of pow():

pow(x, y[, z])

Return x to the power y; if z is present, return x to the power y, modulo z (computed more efficiently than pow(x, y) % z).

Putting it together:

def self_power(n):
 """returns sum of self powers up to n."""
 MOD = 10 ** 10
 total = sum(pow(i, i, MOD) for i in range(1, n + 1))
 return total % MOD

This runs a tiny bit faster:

$ # Your version:
$ python3 -m timeit 'import euler48; euler48.self_power0(1000)'
50 loops, best of 5: 9.55 msec per loop
$ # Improved version:
$ python3 -m timeit 'import euler48; euler48.self_power(1000)'
100 loops, best of 5: 2.19 msec per loop

But it makes a big difference if the numbers become larger:

$ # Your version:
$ python3 -m timeit 'import euler48; euler48.self_power0(10000)'
1 loop, best of 5: 6.65 sec per loop
$ # Improved version:
$ python3 -m timeit 'import euler48; euler48.self_power(10000)'
10 loops, best of 5: 28.6 msec per loop