Project Euler #48: Self powers
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.
Introduction
“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.
int_to_vec() and 10 digits
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.
Adjusting multiply_vec()
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()
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]);
}
Resolving problem_48
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.
Improvements
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.
