Project Euler Problem 16 in F#

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

215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 21000?

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:

     \[ 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, d0 = 3, d1 = 2, and d2 = 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 10k to find dk and use the reminder of the division to calculate dk-1 and so forth until we reach d0.

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

kick it on DotNetKicks.com

Shout it

  1. [1] A recruiter for a very big company once asked me something very similar during an interview as a coding exercise
This entry was posted in .NET, F# and tagged , , . Bookmark the permalink.
  • Pingback: DotNetShoutout

  • http://holoborodko.com/pavel/ Pavel Holoborodko

    I remember that problem.

    I decided to avoid bignum libraries, and found decimal digits of 2^1000 directly.
    Here is my solution in C #16. It is far from perfect in sense of speed and algorithm beauty but it did the job.

    By the way I think it is better to setup formula’s color to 333333 to match the text on the page.
    You can do that in QuickLaTeX settings page – ‘Font color’ option.

  • Anonymous

    Pavel, thank you for the tip. I love QuickLaTeX :)

  • http://holoborodko.com/pavel/ Pavel Holoborodko

    me too :).
    thanks for the support.