# Project Euler Problem 48: Self powers

The series, $1^1 + 2^2 + 3^3 + ... + 10^{10} = 10405071317$.

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

#### Version 1: The obvious way¶

```
from six.moves import map, range, reduce
```

```
sum(map(lambda k: k**k, range(1, 1000+1))) % 10**10
```

This leaves much to be desired since we have to compute a integer with at least $10^{3000}$ digits only to truncate off $10^{3000} - 10^{10} = 10^{10} (10^{2990} - 1)$ digits. Note that in most other languages such as Java, we would have had to resort to some library like `BigInteger`

to perform this computation. In Python, all numbers are represented by a (theoretically) infinite number of bits:

Integers (int)

These represent numbers in an unlimited range, subject to available (virtual) memory only. For the purpose of shift and mask operations, a binary representation is assumed, and negative numbers are represented in a variant of 2’s complement which gives the illusion of an infinite string of sign bits extending to the left.

#### Version 2: Some simple modulo arithmetic¶

We're asked to find $1^1 + 2^2 + 3^3 + ... + 1000^{1000} \mod 10^{10}$. Note that
$$a + b \mod n = (a \mod n) + (b \mod n)$$
and that
$$a \cdot b \mod n = (a \mod n) \cdot (b \mod n)$$
so we can implement modulo `sum`

and `prod`

functions.

```
def prod_mod(nums, m):
"Multiply all nums modulo m"
return reduce(lambda p, q: (p*q)%m, map(lambda n: n%m, nums))
```

```
from itertools import repeat
pow_mod = lambda n, p, m: prod_mod(repeat(n, p), m)
```

```
pow_mod(3, 3, 8)
```

```
sum_mod = lambda nums, m: reduce(lambda p, q: (p+q)%m, map(lambda n: n%m, nums))
```

```
sum_mod(map(lambda k: pow_mod(k, k, 10**10), range(1, 1000+1)), 10**10)
```

This way, we never let the result of any intermediate addition or multiplication exceed $10^{10}-1$.

## Comments

Comments powered by Disqus