# Project Euler Problem 16 in F#

It's time for another Project Euler exercise. This time around it is 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 find 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).

Let's consider a generic number \(n\) and consider how we can describe it as a sum of powers of 10:

$$ n = \sum_{i=0}^k d_i10^i $$For example

$$ 423 = 3 \cdot 10^0 + 2\cdot 10^1 + 4 \cdot 10^2 $$and \( k = 2, d_0 = 3, d_1 = 2, d_2 = 4 \)

So, given a generic number \(n\), we need to find the highest power of ten (\(k\)) such that \(\frac{n}{10^k} > 0\)

(logarithms will help us there). After \(k\) is found, we can start diving \(n\) by \(10^k\) to find \(d_k\) and use the reminder of the division to calculate \(d_{k-1}\) and so forth until we reach \(d_0\).

## Leave a Comment