Problem 16 "Power digit sum"

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

問 16 「各位の数字の和」

\( 2^{15} \) = 32768 であり, 各位の数字の和は 3 + 2 + 7 + 6 + 8 = 26 となる.

同様にして, \( 2^{1000} \) の各位の数字の和を求めよ.

struct BigNum {
    v: Vec<u64>,
}

impl BigNum {
    const TEN_MIL: u64 = 10_000_000_000;
    fn double(&mut self) {
        let mut carry = 0u64;
        for con in self.v.iter_mut() {
            *con *= 2;
            *con += carry;
            if *con < Self::TEN_MIL {
                carry = 0;
                continue;
            }
            carry = 1;
            *con -= Self::TEN_MIL;
        }
        if carry != 0 {
            self.v.push(1u64);
        }
    }
    fn sum_of_digits(&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 n = BigNum { v: vec![1] };
    for _ in 0..1000 {
        n.double();
    }
    let ans = n.sum_of_digits();

    println!("{}", ans);
    assert_eq!(ans, 1366);
}