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))
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
