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 ?
Permalink: http://projecteuler.net/problem=16
Are you kidding me?
In Clojure Euler: Problem 008 we learned how to sum digits in the number. Just gentle reminder:
(defn sum-of-digits [n]
(reduce + (map #(- (int %) 48) (seq (str n)))))
Now, let’s create sequence of powers of two:
(defn powers-of-2 []
(iterate (partial * 2) 1))
Unfortunately, this sequence throws integer overflow on the 64th element.
We can fix that using long arithmetics, which known as BigInteger in Java.
Change 1 to 1N.
(iterate (partial * 2) 1N)
Another way is to use automatic promotion operator (+', *').
If result of some operation is not suitable for some type,
instead of invalid computation and runtime exception, clojure automatically promotes
the type to suitable one (for example Long.MAX_VALUE +' 1 works fine and produces
correct result with type of BigInteger):
(iterate (partial *' 2) 1)
Choose powers-of-2 that you prefer and final result will look like this:
(sum-of-digits (last (take 1001 (powers-of-2))))
P.S. Automatic promotion is a beatiful thing. But be aware about losing in speed of calculations. Also, no way back. If promotion happened, depromotion won’t.
mishadoff 05 March 2013