60 Days of Euler in F# - Problem 40

The Problem

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021...

It can be seen that the 12th digit of the fractional part is 1.

If dn represents the nth digit of the fractional part, find the value of the following expression.

d1 × d10 × d100 × d1000 × d10000 × d100000 × d1000000

The Solution

Well, this seems simple enough. We just have to write a function to find d. It's all map and reduce after that...right?

let d n =
    let rec generate i total =
        let s = i.ToString()
        if n >= total && n <= total + s.Length then
            s.[n - total - 1]
        else
            generate (i + 1) (total + s.Length)

    int(generate 1 0) - int('0')

The function d contains an internal recursive function called generate.

generate takes as input a digit position, i and an accumulator total which stores the length of the string of digits. It converts i into a string of digits. If the n we're looking for is between total and total + s.Length then we know we have found the part of the sequence that contains the magic digit we're looking for. If so, it returns that digit. Otherwise, it recurses, adding 1 to i and adding the number of digits of i to the total.

Now to solve the problem:

[0..6]
|> Seq.map (fun n -> d (pown 10 n))
|> Seq.reduce (fun acc item -> acc * item)

We start with the sequence 0..6 and use Seq.map and pown to generate the sequence 1, 10, 100, etc.

Next, we simply use Seq.reduce to multiply each number in the resulting sequence into a single value. That is our answer.

Other Posts in This Series