Problem 29 "Distinct powers"

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

22=4, 23=8, 24=16, 25=32
32=9, 33=27, 34=81, 35=243
42=16, 43=64, 44=256, 45=1024
52=25, 53=125, 54=625, 55=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, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

問 29 「個別のべき乗」

2 ≤ a ≤ 5 と 2 ≤ b ≤ 5について, \( 2^5 \) を全て考えてみよう:

これらを小さい順に並べ, 同じ数を除いたとすると, 15個の項を得る:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

2 ≤ a ≤ 100, 2 ≤ b ≤ 100 で同じことをしたときいくつの異なる項が存在するか?

struct Index {
    i: usize,
    _ite: Box<dyn Iterator<Item = usize>>,
}

impl Index {
    fn increment(&mut self) {
        self.i += self._ite.next().unwrap();
    }
    fn new() -> Self {
        Self {
            i: 5,
            _ite: Box::new(vec![2usize, 4].into_iter().cycle()),
        }
    }
}

fn rule_out(sieve: &mut Vec<bool>, prime: usize) {
    for i in (prime * prime..sieve.len()).step_by(prime) {
        sieve[i] = false;
    }
}

fn primes(below: u32) -> Vec<u32> {
    let mut primes: Vec<u32> = vec![2u32, 3u32];
    let mut sieve = vec![true; below as usize];
    let sqrt = (sieve.len() as f32).sqrt() as usize;
    let mut index = Index::new();
    while index.i <= sqrt {
        if sieve[index.i] {
            primes.push(index.i as u32);
            rule_out(&mut sieve, index.i);
        }
        index.increment();
    }
    while index.i < sieve.len() {
        if sieve[index.i] {
            primes.push(index.i as u32);
        }
        index.increment();
    }
    primes
}

#[derive(PartialEq, Eq, PartialOrd, Ord, Clone, Debug)]
struct Factor {
    prime: u32,
    exp: u32,
}

fn divide_fully(n: &mut u32, d: u32, side: &mut u32, factors: &mut Vec<Factor>) {
    if *n % d != 0 {
        return;
    }
    let mut exp = 0u32;
    while {
        *n /= d;
        exp += 1;
        *n % d == 0
    } {}
    factors.push(Factor { prime: d, exp: exp });
    *side = (*n as f32).sqrt() as u32;
}

fn factorize(mut n: u32, primes: &[u32]) -> Vec<Factor> {
    let mut factors = vec![];
    let mut side = (n as f32).sqrt() as u32;
    for &p in primes.iter() {
        if p > side || n == 1 {
            break;
        }
        divide_fully(&mut n, p, &mut side, &mut factors);
    }
    if n != 1 {
        factors.push(Factor { prime: n, exp: 1 });
    }
    factors
}

fn count_duplication(arr: &mut [Vec<Factor>]) -> u32 {
    arr.sort();
    let mut dup = 0u32;
    for i in 1..arr.len() {
        if arr[i - 1] == arr[i] {
            dup += 1;
        }
    }
    dup
}

fn main() {
    let primes = primes(101);
    let mut expressions = Vec::new();
    (2..=100u32).map(|a| factorize(a, &primes)).for_each(|a| {
        for b in 2..=100u32 {
            let mut ab = a.to_vec();
            ab.iter_mut().for_each(|f| f.exp *= b);
            expressions.push(ab);
        }
    });
    let c = expressions.len() as u32 - count_duplication(&mut expressions);

    println!("{}", c);
    assert_eq!(c, 9183);
}