This article is part of a series where I'll be diving head first into the Project Euler puzzles. I want to document the challenge of solving such a puzzle and how I got to the answer. I want to prefix this by stating that I can't cheat for any of these challenges; with that I mean I can't look up any other implementations online. After the implementation, I will validate the answer by using this document or a similar sheet.

In this article I'll be solving: Project Euler #48.

“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.”

Right out the gate, we have a problem. If we were to solve this by code, in Rust, we’ll be hit by the limit of an u128-bit integer pretty quickly. Namely, 26^26 is the upper bound of this method. In Ruby, there would be no concern whatsoever. In fact, I can get the answer pretty quickly by doing:

```
(1..1000).map{|n| n**n }.sum
# Reading off the last 10 digits: 9110846700
```

Solved!

However, in Rust we have to do something a bit more clever.

In the past, to fit huge numbers I used `int_to_vec()`

and I think we’re going with the same approach here. The last time I used these methods was for the “1000-digit Fibonacci number” problem. The first issue we have is, that within this trait we only made a method called `sum_vec()`

and `multiply_vec()`

, but no `power_vec()`

. Before I’m going to implement `power_vec()`

, I am aware of the 10 digits limitation. We need to train our methods to only take vectors of max length 11, the rest of the remainders don’t matter.

A reminder: `multiply_vec()`

currently works something like this:

```
167 x 781
700 x 100 = 70000
700 x 60 = 42000
700 x 7 = 4900
80 x 100 = 8000
80 x 60 = 4800
80 x 7 = 560
1 x 100 = 100
1 x 60 = 60
1 x 7 = 7
----------------- +
130427
```

However, for numbers >10 digits it should only do this up till 11 digits (including the only useful remainder). In specs this goes something like:

```
#[test]
fn test_vector_methods() {
let mut n = 9_000_000_000_000.to_vec();
n.multiply_vec(&9_000_000.to_vec());
assert_eq!(n.len(), 11);
assert_eq!(n, vec![0; 11]);
}
```

This would generate 11 0’s.

Writing `power_vec()`

is fairly straight forward, it’s basically multiplying with yourself n-times.

```
// Extend trait with 'power_vec'
impl VecEx<u8> for Vec<u8> {
// ...
fn power_vec(&mut self, power: u16) {
let t = self.clone();
for _ in 0..power {
self.multiply_vec(&t)
}
}
}
#[test]
fn test_power_vec() {
let mut t = 1000.to_vec();
t.power_vec(1000);
assert_eq!(t.len(), 11);
assert_eq!(t, vec![0; 11]);
}
```

To resolve this problem, the code will look something like this:

```
fn problem_48() -> u64 {
let mut start: u128 = 0;
let mut total = vec![];
while start < 1000 {
start += 1;
let mut subtotal = start.to_vec();
subtotal.power_vec(start as u16);
total.sum_vec(&subtotal);
}
total.truncate(10);
total
.iter()
.enumerate()
.fold(0, |acc, (i, t)| acc + 10_u64.pow(i as u32) * *t as u64)
}
#[test]
fn test_problem_48() {
assert_eq!(problem_48(), 9110846700);
}
```

Solved … in 19.15 seconds. I’ll come back to optimize it later.

This can be done way faster, by writing a little algorithm. The algorithm goes something like this:

```
fn power_to_10(i: u64) -> u64 {
let mut tens: u64 = 10;
let mut n = 1;
let mut i_base = i;
let mut total = 0;
let max = 10;
while n < i {
while i_base > 0 {
let base = i_base % tens;
total += base * i;
if tens > 10_u64.pow(max) {
break;
}
tens *= 10;
i_base -= base;
}
// Prevents total from getting reset to 0
// on the final iteration
if i - n > 1 {
i_base = total;
total = 0;
}
tens = 10;
n += 1;
}
total
}
#[test]
fn test_power_to_10() {
assert_eq!(power_to_10(11), 285311670611); // last 11 digits
assert_eq!(power_to_10(14), 206825558016); // last 11 digits
}
```

There are a couple of things to unpack: the first `while`

-loop is nothing more than a loop that acts as “the self power”. The inner `while`

-loop, splits a number into its base parts (so: 31353 becomes 3, 50, 300, 1000, 30000) and multiplies each individual part with `i`

. If the base contains more than 10 digits, stop the loop. This method does produce some extra digits, but that’s fine. The `problem_48`

method can be resolved something like this:

```
fn problem_48() -> u64 {
let mut start: u64 = 0;
let mut total = 1; // To combat 1^1
while start < 1000 {
start += 1;
total += power_to_10(start);
}
total % 10_u64.pow(10)
}
#[test]
fn test_problem_48() {
assert_eq!(problem_48(), 9110846700);
}
```

It runs in 0.08 seconds!

**
The full solution is available on
GitHub.
**