Problem 56 "Powerful digit sum"

A googol (10100) is a massive number: one followed by one-hundred zeros; 100100 is almost unimaginably large: one followed by two-hundred zeros. Despite their size, the sum of the digits in each number is only 1.

Considering natural numbers of the form, ab, where a, b < 100, what is the maximum digital sum?

問 56 「もっとべき乗の数字和」

Googol \(10^{100}\)は非常に大きな数である: 1の後に0が100個続く. \(100^{100}\)は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも数字和 ( 桁の和 ) は1である.

a, b < 100 について自然数 \(a^{b}\) を考える. 数字和の最大値を答えよ.

struct BigNum {
    _v: Vec<u64>,
}

impl BigNum {
    const TEN_MIL: u64 = 10_000_000_000;
    fn new() -> Self {
        BigNum {
            _v: vec![],
        }
    }
    fn init(&mut self, base: u8) {
        self._v.clear();
        self._v.push(base as u64);
    }
    fn multiply(&mut self, n: u8) {
        let mut carry = 0u64;
        for con in self._v.iter_mut() {
            *con = *con * n as u64 + carry;
            if *con < Self::TEN_MIL {
                carry = 0;
                continue;
            }
            carry = *con / Self::TEN_MIL;
            *con %= Self::TEN_MIL;
        }
        if carry != 0 {
            self._v.push(carry);
        }
    }
    fn digit_sum(&self) -> u32 {
        let mut sum = 0u32;
        for &con in &self._v {
            let mut t = con;
            while t > 0 {
                sum += (t % 10) as u32;
                t /= 10;
            }
        }
        sum
    }
}

fn main() {
    let mut bignum = BigNum::new();
    let mut max = 0u32;
    for a in 2u8..100 {
        if a % 10 == 0 {
            continue;
        }
        bignum.init(a);
        for _ in 2u8..100 {
            bignum.multiply(a);
            max = std::cmp::max(max, bignum.digit_sum());
        }
    }

    println!("{}", max);
    assert_eq!(max, 972);
}

struct BigNum {
    _v: Vec<u64>,
}

impl BigNum {
    const TEN_MIL: u64 = 10_000_000_000;
    fn new() -> Self {
        BigNum {
            _v: vec![],
        }
    }
    fn compute(&mut self, base: u8, exp: u8) {
        self._v.clear();
        self._v.push(1);
        for _ in 0..exp {
            self._multiply(base as u64);
        }
    }
    fn _multiply(&mut self, n: u64) {
        let mut carry = 0u64;
        for con in self._v.iter_mut() {
            *con = *con * n + carry;
            if *con < Self::TEN_MIL {
                carry = 0;
                continue;
            }
            carry = *con / Self::TEN_MIL;
            *con %= Self::TEN_MIL;
        }
        if carry != 0 {
            self._v.push(carry);
        }
    }
    fn digit_sum(&self) -> u32 {
        let mut sum = 0u32;
        for &con in &self._v {
            let mut t = con;
            while t > 0 {
                sum += (t % 10) as u32;
                t /= 10;
            }
        }
        sum
    }
}

fn main() {
    let mut bignum = BigNum::new();
    let mut max = 0u32;
    for a in 2u8..100 {
        if a % 10 == 0 {
            continue;
        }
        for b in 2u8..100 {
            bignum.compute(a, b);
            max = std::cmp::max(max, bignum.digit_sum());
        }
    }

    println!("{}", max);
    assert_eq!(max, 972);
}