It’s time for another Project Euler exercise. This time around it’s problem 16:

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}?

## Analysis

I have tried to found an elegant way to solve this problem at a mathematical level, but I couldn't gain any insight relating powers of 2 to their representation in base 10 (I'd love to know if such a thing exists). Therefore I resorted to solve this problem with brute force.

Luckily F# (and now all other .NET 4.0 cousin languages) sports the` BigInteger`

numeric type which helps tackling such huge numbers.

There are basically two approaches to solve this problem:

- Transform the result of exponentiation into a
*string*and iterate through the string adding up all the individual digits, or - Do without strings, and decompose the big number into the individual digits on my own.

I have decided to take the second route because it seemed like a more interesting exercise (the first approach could probably lead to a one-liner). ^{[1]}.

Let’s consider a generic number *n* and consider how we can describe it as a sum of powers of 10:

For example

and *k = 2,* *d _{0} = 3*,

*d*, and

_{1}= 2*d*

_{2}= 4

So, given a generic number *n*, we need to find the highest power of ten ( *k *) such that

(logarithms will help us there). After *k* is found, we can start diving n by *10 ^{k}* to find

*d*and use the reminder of the division to calculate

_{k}*d*and so forth until we reach

_{k-1}*d*.

_{0}## Solution

#light open System open System.Numerics let rec decompose_rec n power_of_ten accu = match power_of_ten with | i when i = 1I -> accu @ [n] |_ -> let d = n / power_of_ten let digits = accu @ [d] decompose_rec (n - (d * power_of_ten)) (power_of_ten / 10I) digits let decompose n = let power = floor (log10 (float n)) let initial_power_of_ten = BigInteger.Pow(10I, int32 power) decompose_rec n initial_power_of_ten [] let sum_digits n = decompose n |> List.sum

A recruiter for a very big company once asked me something very similar during an interview as a coding exercise ↩^{[1]}

Pingback: DotNetShoutout