Definition
A positive integer n is an arithmetic number if the average of its positive divisors is also an integer.

Clearly all odd primes p must be arithmetic numbers because their only divisors are 1 and p whose sum is even and hence their average must be an integer. However, the prime number 2 is not an arithmetic number because the average of its divisors is 1.5.

Example
30 is an arithmetic number because its 7 divisors are: [1, 2, 3, 5, 6, 10, 15, 30], their sum is 72 and average 9 which is an integer.

Task
Calculate and show here:

1. The first 100 arithmetic numbers.

2. The xth arithmetic number where x = 1,000 and x = 10,000.

3. How many of the first x arithmetic numbers are composite.

Note that, technically, the arithmetic number 1 is neither prime nor composite.

Stretch
Carry out the same exercise in 2. and 3. above for x = 100,000 and x = 1,000,000.

References
 Wikipedia: Arithmetic number
 OEIS:A003601 - Numbers n such that the average of the divisors of n is an integer




fn divisor_count_and_sum(mut n: u32) -> (u32, u32) {
    let mut divisor_count = 1;
    let mut divisor_sum = 1;
    let mut power = 2;
    while (n & 1) == 0 {
        divisor_count += 1;
        divisor_sum += power;
        power <<= 1;
        n >>= 1;
    }
    let mut p = 3;
    while p * p <= n {
        let mut count = 1;
        let mut sum = 1;
        power = p;
        while n % p == 0 {
            count += 1;
            sum += power;
            power *= p;
            n /= p;
        }
        divisor_count *= count;
        divisor_sum *= sum;
        p += 2;
    }
    if n > 1 {
        divisor_count *= 2;
        divisor_sum *= n + 1;
    }
    (divisor_count, divisor_sum)
}
 
fn main() {
    let mut arithmetic_count = 0;
    let mut composite_count = 0;
    let mut n = 1;
    while arithmetic_count <= 1000000 {
        let (divisor_count, divisor_sum) = divisor_count_and_sum(n);
        if divisor_sum % divisor_count != 0 {
            n += 1;
            continue;
        }
        arithmetic_count += 1;
        if divisor_count > 2 {
            composite_count += 1;
        }
        if arithmetic_count <= 100 {
            print!("{:3} ", n);
            if arithmetic_count % 10 == 0 {
                println!();
            }
        }
        if arithmetic_count == 1000
            || arithmetic_count == 10000
            || arithmetic_count == 100000
            || arithmetic_count == 1000000
        {
            println!("\n{}th arithmetic number is {}", arithmetic_count, n);
            println!(
                "Number of composite arithmetic numbers <= {}: {}",
                n, composite_count
            );
        }
        n += 1;
    }
}