Clojure Euler: Problem 016

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))))

github

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
blog comments powered by Disqus