Problem 30 "Digit fifth powers"

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44
8208 = 84 + 24 + 04 + 84
9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

問 30 「各桁の5乗」

驚くべきことに, 各桁を4乗した数の和が元の数と一致する数は3つしかない.

ただし, \( 1=1^4 \) は含まないものとする.

この数たちの和は 1634 + 8208 + 9474 = 19316 である.

各桁を5乗した数の和が元の数と一致するような数の総和を求めよ.

fn match_pow_sum(target: u32, pow_sum_999_fold: &[u32; 999]) -> bool {
    let mut digits = target;
    let mut sum = 0;
    while digits > 0 {
        let d = digits % 1000;
        digits /= 1000;
        if d == 0 {
            continue;
        }
        sum += pow_sum_999_fold[d as usize - 1];
        if sum > target {
            return false;
        }
    }
    sum == target
}

fn pow_sum_999_fold(power_ninefold: &[u32; 9]) -> [u32; 999] {
    let mut pow_sum_999_fold = [0u32; 999];
    for i in 1..=pow_sum_999_fold.len() {
        let mut sum = 0;
        let mut digits = i as u32;
        while digits > 0 {
            let d = digits % 10;
            digits /= 10;
            if d != 0 {
                sum += power_ninefold[d as usize - 1];
            }
        }
        pow_sum_999_fold[i - 1] = sum;
    }
    pow_sum_999_fold
}

fn digit_range_max(powed_nine: u32) -> u32 {
    let mut digit_min = 1u32;
    let mut pow_sum_max = powed_nine;
    while digit_min < pow_sum_max {
        digit_min *= 10;
        pow_sum_max += powed_nine;
    }
    pow_sum_max - powed_nine
}

fn main() {
    let e = 5;
    let mut power_ninefold = [0u32; 9];
    (1..=9u32).for_each(|n| power_ninefold[n as usize - 1] = n.pow(e));
    let pow_sum_999_fold = pow_sum_999_fold(&power_ninefold);
    let digits_max = digit_range_max(power_ninefold[8]);
    let sum = (2..=digits_max)
        .filter(|&d| match_pow_sum(d, &pow_sum_999_fold))
        .sum::<u32>();

    println!("{}", sum);
    assert_eq!(sum, 443839);
}