Project Euler #55: Lychrel numbers
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 #55.
Introduction
“How many Lychrel numbers are there below ten-thousand?”
Is a number a Lychrel number?
The puzzle states that we can take a max of 50 cycles before stopping to check if a number is a Lychrel number or not. My initial setup therefore will look like this:
fn is_lychrel(n: u32) -> bool {
let mut cycles = 50;
while cycles > 0 {
cycles -= 1
}
false
}
fn problem_55() -> usize {
(1..10_000).filter(|&n| is_lychrel(n)).count()
}
#[test]
fn test_problem_55() {
assert_eq!(problem_55(), 1)
}
The next step is to write a method to test if a number is a Lychrel number or not. The two examples I’m given in the code are 196, for a false case, and 349 and 47 for positive cases. To play it safe - because I have the sneaking suspicion some of these numbers are going to exceed the max of a u128 - I’m going to cast all numbers to vectors, by reusing the to_digits() method from “Permuted multiples”.
The next step is to simply reverse the vector from to_digits() and sum it to the other vector by reusing sum_vec() from many a previous Euler puzzle. The is_lychrel method will start to look like this:
fn is_lychrel(n: u32) -> bool {
let mut cycles = 50;
let mut digits = to_digits(n);
let mut is_lychrel = true;
while cycles > 0 {
let mut digits_rev = digits.clone();
digits_rev.reverse();
digits.sum_vec(&digits_rev);
// if digits are a palindrome, set is_lychrel
// to false and break
cycles -= 1
}
is_lychrel
}
To test if the vector is a palindrome I’ll reuse the method from “Largest palindrome product” and tweak it slightly to be able to take a vector instead of a string.
After some fiddling, the answer I get is 249 Lychrel numbers, which is the correct answer. No optimization is needed, as it resolves in 0.08s.
The full solution is available on GitHub.
