Project Euler #29: Distinct 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 #29.
Introduction
How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?
The first part of this problem is: does 100^100 fit in a Rust integer? It seems like it doesn’t, so we must find a smarter way of solving this little mystery. We know the total distinct terms is going to be < 9801, because of the grid size ((100 - 1) * 2). We can start with that and reduce the duplicate terms, but how many duplicates do we get per row? We know f.e. 2^6 is the same as 4^3. Other examples:
64 can be noted down as:
2*2*2*2*2*2
4*4*4
8*8
1024 can be noted down as:
2*2*2*2*2*2*2*2*2*2 (10 2's)
4*4*4*4*4 (5 4's)
32*32 (2 32's)
The prime factors
My first train of thought is: turn 1 to a 100 into their distinct prime factors. I’m going to use the is_prime method from “Largest prime factor” and write a method to determine the prime factors:
fn prime_factors(mut number: u64) -> Vec<u64> {
let mut factors: Vec<u64> = vec![];
let mut factor: u64 = 2;
while number > 1 {
if is_prime(factor) && number % factor == 0 {
factors.push(factor);
number /= factor;
} else {
factor += 1;
}
}
factors
}
The prime factors of 4 are [2,2], if I were to take the power of 4 from 4, that’s 256, or 2^8 in prime factors. To elaborate:
2^4 = [2,2,2,2] (4 times a 2)
4^2 = [2,2] + [2,2] (also: 2 times [2,2])
2^6 = [2,2,2,2,2,2] (6 times a 2)
4^3 = [2,2] + [2,2] + [2,2] (3 times [2,2])
8^2 = [2,2,2] + [2,2,2] (2 times [2,2,2])
2^8 = [2,2,2,2,2,2,2,2] (8 times a 2)
4^3 = [2,2] + [2,2] + [2,2] + [2,2] (4 times [2,2])
16^2 = [2,2,2,2] + [2,2,2,2] (2 times [2,2,2,2])
The first rough version, in code, looks like this:
for i in 2..=100 {
for j in 2..=100 {
let mut list = prime_factors(i);
for n in 0..list.len() {
let mut t = vec![list[n]; j - 1];
list.append(&mut t);
}
list.sort();
println!("A: {}, B: {}, TOTAL: {:?}", i, j, list);
}
}
The next step would be to push all the list vectors into another vector and checking if the previous vector has already passed once before. However, comparing <Vec>'s with each other is going to be a pain. Especially when the vector for 100^100 looks like: 200 2’s followed by 200 5’s. In theory, we could solve it like this, but there might be an easier way.
Finding an easier way out …
There has to be an easier solution. Perhaps it’s: only the perfect numbers will be in here more than once? Perhaps the Wikipedia article on Exponentiation [1] can be of use? In that article they mention some interesting facts which may or may not be of use. One of the things that catches my eye is their power table.
So a couple of things that catch my eye:
2^4 = 4^2
2^6 = 4^3 = 8^2
2^8 = 4^4
2^9 = 8^3
2^10 = 4^5
etc.
3^6 = 9^3
3^8 = 9^4
3^10 = 9^5
etc.
Assuming the first row of 2^n’s will give unique results (and they will), we’ll have 99 unique values. The next row, with value 3^n, will also give unique results and won’t interfere with the 2^n’s. Pretty much, for any prime number, taking the power of that number will give unique results. For the number 4, skip, (99 - 2) / 2 = 48 numbers. For the number 6, even though it’s a composite, we’ll also allow all numbers. For the number 8 we skip the first (99 - 2) / 4 = 24 outcomes. For the number 10 we’ll also allow the first 99 digits. Again, thinking about it in this way won’t get me anywhere near the actual answer, because I fail to see the pattern.
.. back to the prime factors
Switching back to the prime factors, there’s a simple way of comparing those large vectors. Casting them to a String of course:
fn problem_29(max: u64) -> u64 {
let mut totals: Vec<String> = vec![];
for a in 2..=max {
for b in 2..=max {
let mut factors = prime_factors(a);
for i in 0..factors.len() {
let mut n = vec![factors[i]; b as usize - 1];
factors.append(&mut n)
}
let mut string = String::from("");
for i in &factors {
string.push_str(&i.to_string());
}
if !totals.contains(&string) {
totals.push(string);
}
}
}
totals.len() as u64
}
#[test]
fn test_problem_29() {
assert_eq!(problem_29(5), 15);
assert_eq!(problem_29(6), 23);
assert_eq!(problem_29(100), 9276);
}
This actually gives me an answer: 9276 unique numbers. This seems to be incorrect, and I might know why that is, it is because we currently don’t sort the factors. After some sorting (factors.sort()), we get to the correct answer of 9183. It’s not the fastest solution, but it is correct.
Improving the answer
After some refactoring I got rid of the sorting and after reading up on how to repeat characters in a string [2], this is the code I end up with:
fn problem_29(max: u64) -> u64 {
let mut totals: Vec<String> = vec![];
for a in 2..=max {
for b in 2..=max {
let primes = prime_factors(a);
let mut string = String::from("");
for i in 0..primes.len() {
let sub_string = primes[i]
.to_string()
.repeat(b as usize);
string.push_str(&sub_string);
}
if !totals.contains(&string) {
totals.push(string);
}
}
}
totals.len() as u64
}
#[test]
fn test_problem_29() {
assert_eq!(problem_29(5), 15);
assert_eq!(problem_29(6), 23);
assert_eq!(problem_29(100), 9183);
}
The code above is a bit nicer, but it still takes 4 seconds to calculate. The reason why that is, is because 100^100 is denoted as a String containing 200 2’s and 200 5’s, a 400 character String if you will. We can compress that information to: 2|200|5|200|; a string denoting the same information, but with a lot less characters. To make that change, we first change the prime_factors method. It needs to return a tuple of unique prime factors and their counts:
fn prime_factors(mut number: u8) -> Vec<(u8, u8)> {
let mut factors: Vec<(u8, u8)> = vec![];
let mut factor: u8 = 2;
while number > 1 {
if is_prime(factor) && number % factor == 0 {
match factors.iter().position(|(a,_)| *a == factor) {
Some(index) => factors[index].1 += 1,
None => factors.push((factor, 1))
}
number /= factor;
} else {
factor += 1;
}
}
factors
}
#[test]
fn test_prime_factors() {
assert_eq!(prime_factors(2), vec![(2, 1)]);
assert_eq!(prime_factors(3), vec![(3, 1)]);
assert_eq!(prime_factors(4), vec![(2, 2)]);
assert_eq!(prime_factors(5), vec![(5, 1)]);
assert_eq!(prime_factors(10), vec![(2, 1), (5, 1)]);
assert_eq!(prime_factors(99), vec![(3, 2), (11, 1)]);
assert_eq!(prime_factors(100), vec![(2, 2), (5, 2)]);
}
The next set of changes are all at the problem_29() method. First up, I changed the way I build up the string. Instead of using repeat() I can use something simple like format! to concatenate the amount of prime factors and their counts. However, what I noticed is that after applying those changes the code still seems very slow, which mainly has to do with !totals.contains(..). Using .contains() does a search every loop cycle, which becomes slower and slower once totals starts to increase. The simple solution here, after some trial and error, is to drop it from the code and use sort() and dedup() at the end of the for-loop, like this:
fn problem_29(max: u16) -> u16 {
let mut totals: Vec<String> = vec![];
for a in 2..=max {
let primes = prime_factors(a as u8);
for b in 2..=max {
let string = primes
.iter()
.map(|(n, len)| format!("{}|{}|", n, *len as u16 * b))
.collect();
totals.push(string)
}
}
totals.sort();
totals.dedup();
totals.len() as u16
}
The speed increase here is quite significant; the runtime reduces from 4 seconds to 0.02 seconds. Now that’s what I call podracing!
Sources
[2] Fill string with repeated character
The full solution is available on GitHub.
