Project Euler #56: Powerful digit sum
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 #56.
Introduction
“Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?”
Part 1: sum_vec(), mul_vec() and to_digits()
I’ll be reusing the code originally started in “Power digit sum” to form the base of this puzzle. The next part is to take the power of a 100 of each digit and check which consecutive iteration of each vector contains the most digits (so: multiply by the same vector each time).
fn max_power_digit_sum(digit: u128) -> u64 {
let mul_digits = digit.to_digits();
let mut digits = digit.to_digits();
let mut max = 0;
for _ in 2..=100 {
digits.mul_vec(&mul_digits);
let sum = digits.iter().fold(0, |acc, &n| acc + n as u64);
if sum > max {
max = sum;
}
}
max
}
#[test]
fn test_max_power_digit_sum() {
assert_eq!(max_power_digit_sum(10), 1);
assert_eq!(max_power_digit_sum(99), 972);
}
Part 2: Resolving problem 56
To resolve problem 56 do the following:
fn problem_56() -> u64 {
let mut max = 0;
let mut a = 99;
while a > 2 {
let pds = max_power_digit_sum(a);
if pds > max {
max = pds
}
a -= 1;
}
max
}
#[test]
fn test_problem_56() {
assert_eq!(problem_56(), 972);
}
The code is not fast, but it results in the right answer. It resolves in 9.16s.
The full solution is available on GitHub.
