Project Euler Problem 16 Solution

Question

$2^{15} = 32768$ and the sum of its digits is $3 + 2 + 7 + 6 + 8 = 26$.

What is the sum of the digits of the number $2^{1000}$?

sumDigits ::  Integer -> Integer
sumDigits n = sumDigits' n 0
where sumDigits' 0 acc = acc
sumDigits' n acc = sumDigits' (div n 10) (acc + (mod n 10))

main ::  IO ()
main = print $sumDigits$ 2^1000
$ghc -O2 -o sumExp sumExp.hs$ time ./sumExp
real   0m0.001s
user   0m0.000s
sys    0m0.000s

Python

#!/usr/bin/env python
print(sum(int(digit) for digit in str(2**1000)))
$time python3 sum-exp.py real 0m0.015s user 0m0.008s sys 0m0.004s Ruby #!/usr/bin/env ruby puts (2**1000).to_s.each_char.inject(0) {|s,v| s+v.to_i} $ time ruby sum-exp.rb
real   0m0.049s
user   0m0.044s
sys    0m0.004s

Rust

fn main() {
let mut decimal = vec![1];
for _ in 0..1000 {
let mut carry = 0;
for i in 0..decimal.len() {
let mut digit = decimal[i];
digit = 2 * digit + carry;
carry = digit / 10;
decimal[i] = digit % 10;
}
if carry > 0 {
decimal.push(carry);
}
}
println!("{}", decimal.iter().sum::<u64>());
}
$rustc -C target-cpu=native -C opt-level=3 -o digits digits.rs$ time ./digits
real   0m0.002s
user   0m0.000s
sys    0m0.000s