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))
-
3\$\begingroup\$ 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? \$\endgroup\$Martin R– Martin R2019年07月23日 06:51:23 +00:00Commented Jul 23, 2019 at 6:51
-
\$\begingroup\$ there is no best answer mostly and my questions are tagged with python-3.x. \$\endgroup\$user203258– user2032582019年07月23日 07:09:05 +00:00Commented Jul 23, 2019 at 7:09
-
3\$\begingroup\$ 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"... \$\endgroup\$301_Moved_Permanently– 301_Moved_Permanently2019年07月23日 07:24:48 +00:00Commented Jul 23, 2019 at 7:24
-
\$\begingroup\$ you mean in the description? \$\endgroup\$user203258– user2032582019年07月23日 07:26:45 +00:00Commented Jul 23, 2019 at 7:26
-
1\$\begingroup\$ okay, from now on, all my posts will contain python and python 3.x. Anything else? \$\endgroup\$user203258– user2032582019年07月23日 07:35:58 +00:00Commented Jul 23, 2019 at 7:35
1 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