problem29.rs

/*
Problem 29:
Consider all integer combinations of a^b for 2 <= a <= 5 and 2 <= b <= 5:
2^2 = 4, 2^3 = 8, 2^4 = 16, 2^5 = 32
3^2 = 9, 3^3 = 27, 3^4 = 81, 3^5 = 243
42 = 16, 4^3 = 64, 4^4 = 256, 4^5 = 1024
5^2 = 25, 5^3 = 125, 5^4 = 625, 5^5 = 3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
4,8, 9, 16, 25, 27, 32, 64, 81, 125, 213, 256, 625, 1024, 3125.
How many distinct terms are in the sequence generated by a^b for 2 <= a <= 100 and 2 <= b <= 100?
*/

use std::collections::HashSet;
use num_bigint::BigUint;

pub fn problem29(max_value: u32) -> usize {
    // Greatest value to compute is 100^100, which has 665 digits in base 2
    // Therefore, 100^100 is higher than the maximum value of a u128, so I'll represent numbers with BigUint
    let mut set: HashSet<BigUint>  = HashSet::new(); 

    for a in 2..max_value+1 {
        for b in 2..max_value+1 {
            set.insert(BigUint::from(a as u128).pow(b));
        } 
    }
    set.len()
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_problem29() {
        assert_eq!(problem29(5), 15);
        assert_eq!(problem29(100), 9_183);
    }
}