60 Days of Euler in F# - Problem 49

The Problem

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

The Solution

First, let's write a function to generate a series of 3 numbers that increases by 3330.

let series n = [n; n+3330;n+3330+3330]

Next, we need a function to determine if all elements in a list contain exactly the same digits.

let haveSameDigits l =

    let first::others = 
        l 
        |> List.map (fun x -> x.ToString())

    let containsChar (c : char) (s : string) =
        s.IndexOf(c) >= 0

    let rec haveSame (others : string list) =
        match others with
        | [] -> true
        | x::xs ->
            if (first |> Seq.forall (fun c -> containsChar c x)) then
                haveSame xs
            else
                false

    haveSame others

The haveSameDigits function takes a list l as input. It starts out by finding the first term in the list and separating it from all the others. Then it calls the internal haveSame function which checks all the values in others to see if each other element contains all the digits in first.

Now we need a way to determine if all the elements in a list are prime.

let intsqrt i = int(sqrt(float i))

let isPrime i =
    if i <= 1 then false
    elif i = 2 then true
    elif (i &&& 1) = 0 then false
    else
        let sr = intsqrt i
        seq { 3..2..sr } |> Seq.forall (fun f -> i%f<>0)

let allArePrime l = 
    l |> List.forall isPrime

The allArePrime function returns true if all the elements in the input list l are prime. The functions intsqrt and isPrime are old friends from many other Euler problems.

Now we need a function to return a sequence of primes.

let rec nextPrime x =
    match x with
    | x when isPrime x -> x
    | x -> nextPrime (x + 1)

let getPrimesBelow max =
    let primeGenerator candidate =
        if candidate > max then
            None
        elif candidate = 2 then
            Some(2,3)
        else
            let next = nextPrime candidate
            if next >= max then
                None
            else
                Some(next,next+2)

    Seq.unfold primeGenerator 2

Again, the getPrimesBelow function is familiar if you've been following this series. We're going to use it to generate a sequence of 4-digit primes since we know from the problem definition that the value we're looking for has 4 digits.

For our last helper function, we need a simple way to concatenate together a list of integers, since that's the format required for the answer.

let listToString l = 
    System.String.Join("", l |> List.map (fun x -> x.ToString()))

Now we can solve the problem:

getPrimesBelow 10000
|> Seq.filter (fun n -> n > 1487)
|> Seq.map (fun n -> series n)
|> Seq.filter allArePrime
|> Seq.filter haveSameDigits
|> Seq.map listToString
|> Seq.head

We start by getting all primes below 10000 and then filtering out anything <= 1487. The problem definition gives us this starting point.

Next, we convert each element in the sequence into the series we're interested in. We filter out any of those series where not allArePrime and don't haveSameDigits.

And finally, we convert each element in the sequence to concatenated strings and return the head. That is the answer.

60 Days of Euler in F# - Problem 48

The Problem

The series, 11 + 22 + 33 + ... + 1010 = 10405071317.

Find the last ten digits of the series, 11 + 22 + 33 + ... + 10001000.

The Solution

I don't know what people working in C are doing to solve these problems that involve enormous integer values. But fortunately we're on the .NET stack and we have BigInteger. It makes solving this problem trivial.

let sum =
    Seq.unfold (fun state -> Some(state, state+1)) 1
    |> Seq.map (fun n -> pown (bigint n) n)
    |> Seq.take 1000
    |> Seq.sum
let str = string sum
str.Substring(str.Length - 10)

We start out by generating natural numbers with Seq.unfold. We use Seq.map to raise each element to its own power using pown. Then we take the first 1000 elements of that sequence. Then we sum those.

Next, we convert that number to a string. If you're curious, that string has 3001 characters in it. Last, we use Substring to get the last 10 digits of the string. That is our answer.

60 Days of Euler in F# - Problem 47

The Problem

The first two consecutive numbers to have two distinct prime factors are:

  • 14 = 2 × 7
  • 15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

  • 644 = 2² × 7 × 23
  • 645 = 3 × 5 × 43
  • 646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

The Solution

Once again, we need primes. Lots of them. So we'll start by stealing the getSomePrimes function from yesterday.

let intsqrt i = int(sqrt(float i))

let isPrime i =
    if i <= 1 then false
    elif i = 2 then true
    elif (i &&& 1) = 0 then false
    else
        let sr = intsqrt i
        seq { 3..2..sr } |> Seq.forall (fun f -> i%f<>0)

let rec nextPrime i =
    match i with
    | i when isPrime i -> i
    | i -> nextPrime (i + 1)

let getSomePrimes num =
    let primeGenerator (candidate,count) =
        if count > num then
            None
        elif candidate = 2 then
            Some(2,(3,count+1))
        else
            let next = nextPrime candidate
            Some(next,(next+2,count+1))

    Seq.unfold primeGenerator (2,1)

let factors = getSomePrimes 1000 |> List.ofSeq

So how many primes do we need? As with yesterday's problem, I don't know. I'm going to pick 100 because "it sounds good" and adjust later if I need to.

Why 100? We're looking for 4 prime factors. If we generate 1000 primes and take the last 4, we get:

  • 7883
  • 7901
  • 7907
  • 7919

If you multiply those 4 numbers together you get 3,899,919,746,694,739. That's way out of 32-bit integer territory. Are we willing to bet that the answer is less than that? Yes, we are.

Now we'll write a function to get the prime factors of a number.

let f n =
    let rec getFactors (acc : Set<int>) (factors : int list) =
       match factors with
       | [] -> acc
       | x::xs -> 
            if n % (x*x) = 0 then
                getFactors (Set.add (x*x) acc) xs
            elif n % x = 0 then
                getFactors (Set.add x acc) xs
            else
                getFactors acc xs

    getFactors Set.empty<int> factors

The function f takes a number n and returns its prime factors.

The recursive internal getFactors function simply starts with a list of factors and tests them all to see if they are factors of n. The problem definition clearly shows that squares of primes are allowed to be counted as a "distinct factor" so we account for that case.

Now we need a function to look at a number and see if it has the specified number of distinct prime factors. In fact, we need to know if several consecutive numbers have that property, so we'll take a list of numbers as input instead of just a single number. We need to verify that:

  • Each number has 4 distinct factors
  • The set of 4 numbers has 16 distinct factors

The problem definition doesn't come right out and say that "distinct prime factors" means "distinct across the 4 consecutive numbers", but you don't get the right answer without accounting for that.

[<Literal>]
let factorCount = 4

[<Literal>]
let requiredDistinct = 16

let haveDistinctPrimeFactors numbers =
    let numbersFactors = 
        numbers
        |> Seq.map f
        |> List.ofSeq

    let distinctCount =
        numbersFactors
        |> List.reduce (fun acc elem -> acc + elem)
        |> Set.count

    (numbersFactors |> List.forall (fun x -> (Set.count x) = factorCount)) &&
    (distinctCount = requiredDistinct)

The haveDistinctPrimeFactors function starts by computing a couple of values.

numbersFactors becomes a list of factors for each of the input numbers.

distinctCount is the count of the distinct factors across all 4 input numbers. The factors are of type Set so when we add them together, we wind up with the union of all 4 sets. Thus, the count of that union is the number of distinct factors.

If the count of distinct factors for each input is 4 and the count of distinct factors is requiredDistinct then the function returns true; otherwise, it returns false.

Now we can solve the problem:

#time
Seq.unfold (fun state -> Some(state, state+1)) 647
|> Seq.filter (fun x -> haveDistinctPrimeFactors [x..x+3])
|> Seq.head
#time

We start by using Seq.unfold to generate an infinite sequence of numbers starting at 647. The problem definition says that 644..646 is the first set of consecutive numbers of have 3 prime factors, so we'll start looking right after that.

Next, we filter out any values that don't have the required distinct prime factors and return the head of the resulting sequence. That is the answer.

60 Days of Euler in F# - Problem 46

The Problem

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

  • 9 = 7 + 2×12
  • 15 = 7 + 2×22
  • 21 = 3 + 2×32
  • 25 = 7 + 2×32
  • 27 = 19 + 2×22
  • 33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

The Solution

As we do with some many of these problems, we need some primes. The problem definition asks us to find odd composite numbers that meet the criteria. In this case "odd composite" is simply a way of saying "the multiple of two primes other than 2".

We'll start by stealing the getSomePrimes function from Problem 7. This function generates a specified number of primes.

let intsqrt i = int(sqrt(float i))

let isPrime i =
    if i <= 1 then false
    elif i = 2 then true
    elif (i &&& 1) = 0 then false
    else
        let sr = intsqrt i
        seq { 3..2..sr } |> Seq.forall (fun f -> i%f<>0)

let rec nextPrime i =
    match i with
    | i when isPrime i -> i
    | i -> nextPrime (i + 1)

let getSomePrimes num =
    let primeGenerator (candidate,count) =
        if count > num then
            None
        elif candidate = 2 then
            Some(2,(3,count+1))
        else
            let next = nextPrime candidate
            Some(next,(next+2,count+1))

    Seq.unfold primeGenerator (2,1)

The plan of attack is to multiply primes together to generate the composites. We also need a list of primes to add squares to to test for solutions. How many primes do we need? I have no idea and lack the mathematical analysis capabilities to figure it out. So I think 1000 is a good place to start. We can adjust later if we need to. Because computing primes is expensive, I'm storing them in a List so they only get generated once.

let primes = 
    getSomePrimes 1000 
    |> Seq.skip 1
    |> List.ofSeq

primes will contain a list of 999 primes. It skips over 2 (the first element in the list) so that we don't generate any even numbers.

Now we need some squares to add to our primes.

let generateSquares state =
    Some(state * state, state + 1)

let squares =
    Seq.unfold generateSquares 1
    |> Seq.take 1000
    |> List.ofSeq

We use Seq.unfold to generate squares for the first 1000 integers. Again, 1000 is just a number I picked to get started. We can adjust later if we need to.

Now we need a way to test possible solutions:

let inline isMatch p s n = p + s*2 = n

let findSquare p n = 
    squares 
    |> Seq.filter (fun s -> isMatch p s n)
    |> Seq.tryHead

let solution n =
    primes
    |> Seq.filter (fun p -> p < n)
    |> Seq.map (fun p -> (p,findSquare p n))
    |> Seq.filter (fun (_,square) -> square.IsSome)
    |> Seq.tryHead

The isMatch function takes a prime p, a square s, and a composite number n as input. If these inputs satisfy the conjecture, it returns true.

findSquare takes a prime p and a composite number n as input. It returns the first square that satisfies the conjecture; otherwise it returns None.

The solution function takes a composite number n as input. It takes our list of primes, filters out any below n, and tries to findSquare that satisfies the conjecture with that prime. If a solution is found, it returns the solution; otherwise it returns None.

Now we can solve the problem:

let crossJoin xs ys = 
    xs
    |> Seq.collect (fun x -> ys |> Seq.map (fun y -> x, y))

#time
crossJoin primes primes
|> Seq.map (fun (a,b) -> a*b)
|> Seq.sort
|> Seq.map (fun n -> (n, solution n))
|> Seq.filter (fun (n,solution) -> solution.IsNone)
|> Seq.head
|> fst
#time

We start by cross joining all our primes with each other prime, multiplying them together to get composite numbers, and then sorting the resulting sequence. The sort step is necessary because we are looking for the smallest composite that fails to satisfy the conjecture.

Next, we use Seq.map to generate a solution for each composite. Then we filter out composites where there is no solution. The head of the resulting sequence is the answer.

Note: Above, we arbitrarily chose 1000 primes and 1000 squares. It turns out this generates enough data to find the answer. If it didn't, we'd have to experiment with increasing these numbers until we finally found the answer.

60 Days of Euler in F# - Problem 45

The Problem

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...

Pentagonal Pn=n(3n−1)/2 1, 5, 12, 22, 35, ...

Hexagonal Hn=n(2n−1) 1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

The Solution

Plan of attack:

  • Starting from 286, generate a sequence of triangle numbers
  • Test each one for pentagonality
  • Test each one for hexagonality
  • When we find one that is both pentagonal and hexagonal, we have our answer.

Let's start with the easy stuff:

let firstT = 285L + 1L
let firstP = 165L + 1L
let firstH = 143L + 1L

Based on the problem definition, we know that the first time T, P, and H line up is at n = 285, 165, and 143, respectively. So when we start generating sequences, we're going to start at one past those.

let t n = n * (n + 1L) / 2L
let p n = n * (3L * n - 1L) /2L
let h n = n * (2L * n - 1L)

The above trio of functions generate the nth triangle, pentagonal, and hexagonal number.

Now, we need a quick way to test for pentagonal and hexagonal numbers. So we'll make maps containing 100000 of each class of numbers. 100000 is a number I just made up on the spot because it "seemed reasonable". We can adjust later if need be.

let makeMap f first =
    let nums =
        Seq.unfold (fun state -> Some(f state, state + 1L)) first
        |> Seq.mapi (fun i x -> (x,i+1))
        |> Seq.take 100000
        |> List.ofSeq

    let max = fst (nums |> List.last)
    let map = Map.ofList nums
    (max,map)

let pentagonalMax,pentagonalMap = makeMap p firstP
let hexagonalMax,hexagonalMap = makeMap h firstH
let maxToCheck = min pentagonalMax hexagonalMax

let isPentagonal n = Map.containsKey n pentagonalMap
let isHexagonal n = Map.containsKey n hexagonalMap

The makeMap function takes a starting value and a sequence unfolding function. It generates the sequence and converts it into a map. It returns both the maximum value in the map and the map itself.

Using makeMap we generate pentagonal and hexagonal maps and their maximums. The value maxToCheck gets bound to the minimum of pentagonalMax and hexagonalMax. We'll stop generating triangle numbers when they get above this value.

Finally, we have a pair of functions, isPentagonal and isHexagonal that can check for pentagonality and hexagonality, respectively.

Now we need a bunch of triangle numbers to start testing:

let generateTriangle state =
    let number = t state
    if (number > maxToCheck) then
        None
    else
        Some(number, state + 1L)

let triangleNumbers =  Seq.unfold generateTriangle firstT

We use Seq.unfold to generate triangle numbers using the generator function generateTriangle. It stops generating when the number generated exceeds maxToCheck.

Now we can solve the problem:

triangleNumbers
|> Seq.filter (fun n -> isPentagonal n && isHexagonal n)
|> Seq.head

We simply take our sequence of triangle numbers, filter out any that aren't both pentagonal and hexagonal, and return the head of that sequence. That is the answer.

60 Days of Euler in F# - Problem 44

The Problem

Pentagonal numbers are generated by the formula, Pn=n(3n−1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 − 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk − Pj| is minimised; what is the value of D?

The Solution

I like it when the problem spells out the main function we're going to need to find the solution. So let's start with that:

let p n = n * (3 * n - 1) / 2

I lack the math skills to choose a good upper bound for this one, so I'll arbitrarily choose 10000. If we find we don't get the right answer, we can adjust it later.

[<Literal>]
let maxN = 10000

We we really need to get going is an array of pentagonal numbers that we can pair up. So let's take the first 10000 pentagonal numbers and stuff them in an array.

let pentagonalNumbers = 
    Seq.unfold (fun state -> Some(p state, state + 1)) 1
    |> Seq.take maxN
    |> Array.ofSeq

And since we need to test our results to see if they are pentagonal, we can use that same array to build a map that we can use to test our results for pentagonality. (Is that a word? If not, it should be.)

let pentagonalMap = 
    pentagonalNumbers 
    |> Seq.map (fun x-> (x,x)) 
    |> Map.ofSeq

let isPentagonal n = 
    Map.containsKey n pentagonalMap

To solve the problem, we'll start by pairing up our pentagonal numbers with other pentagonal numbers.

let combos = [
    for j in 0..(maxN-2) do
        for k in (j+1)..(maxN-1) -> 
            (pentagonalNumbers.[j],pentagonalNumbers.[k])
]

combos pairs up j values (all pentagonal numbers except the last one) with k values (all pentagonal numbers greater than the j value). This ensures that Pk - Pj is always positive and that j and k are never equal.

Now we can solve the problem:

combos
|> List.filter (fun (j,k) -> isPentagonal (j + k) && isPentagonal (k - j))
|> List.map (fun (j,k) -> k - j)
|> List.min

We filter out combos for which j+k is not pentagonal or k-j is not pentagonal. Then we map the filters pairs to k-j. The minimum value of k-j is the answer.

60 Days of Euler in F# - Problem 43

The Problem

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

The Solution

So, this problem is fairly simple, but it might be one of those tricky ones where the obvious solution isn't fast enough. But let's try the obvious solution and see where that gets us.

First, we'll declare a list with our prime divisors.

let divisors = [ 2; 3; 5; 7; 11; 13; 17 ]

Next, we'll write a function to take a list of digits and turn that into a number.

let toNumber (l : int list) =
    int64 (System.String.Join("", l |> List.map (fun x -> x.ToString())))

Now we need a function to determine if a given list of numbers is "special" according to the problem definition.

let isSpecial (n : int list) =
    [1..7]
    |> Seq.map (fun x -> n.[x] * 100 + n.[x+1] * 10 + n.[x+2])
    |> Seq.zip divisors
    |> Seq.forall (fun (d,n) -> n % d = 0)

The problem definition starts counting d at 1, but we're in .NET-land where things are 0-based. The list [1..7] represents the starting d.

Next, Seq.map takes that d and the two right after it and turns it into a 3-digit number.

Seq.zip creates a new sequence of each 3-digit number and all the divisors.

Finally, Seq.forAll determines if is the sequence isSpecial by ensuring each number is divisible by all the divisors.

Now we can solve the problem.

let rec distribute e = function
    | [] -> [[e]]
    | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
let rec permute = function
    | [] -> [[]]
    | e::xs -> List.collect (distribute e) (permute xs)

#time
permute [0..9]
|> Seq.filter isSpecial
|> Seq.sumBy toNumber
#time

We start with the pair of functions we used in Problem 41 for generating permutations.

Next, we get all the permutations of the digits 0..9. We filter out any of those that aren't "special", convert the ones that are into numbers, and take the sum. The sum is the answer to the problem.

60 Days of Euler in F# - Problem 42

The Problem

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

The Solution

The most obvious place to start is by writing a function for tn

let t n = n * (n + 1) /2

Whew! I'm glad we got that complicated beasty out of the way.

Now, I suspect that we're going to be seeing the same triangle numbers over and over again, so I think it might be helpful to be able to find them quickly. Let's create a Map of the first 1000 triangle numbers.

let triangleNumbers = 
    Seq.unfold (fun state -> Some(t state, state + 1)) 1
    |> Seq.map (fun x -> (x,x))
    |> Seq.take 1000
    |> Map.ofSeq

And we can use that to create a function that determines if a given n is a triangle number.

let isTriangle n = Map.containsKey n triangleNumbers

Next, we need a way to turn a word into its numeric value, per the problem definition.

let toNumeric (s : string) =
    s
    |> Seq.map (fun v -> int(v) - int('A') + 1)
    |> Seq.sum

string can be treated as Seq<char> so we simply map each character to its integer value, subtract the integer value for 'A', and add 1.

Now we can solve the problem:

let splitByMany (c : char[]) (s : string) = 
    s.Split(c, System.StringSplitOptions.RemoveEmptyEntries)

System.IO.File.ReadAllText(@"C:\Development\ProjectEuler\FSharpSolutions\WordsProblem42.txt")
|> splitByMany [| '"'; ',' |]
|> Seq.map(fun w -> (w,toNumeric w))
|> Seq.filter (fun (w,v) -> isTriangle v)
|> Seq.length

The above reads in all the words, splits them into an array, computes their numeric value, filters out any values that aren't triangle numbers, and returns the sequence length. The length of the sequence is the answer.

60 Days of Euler in F# - Problem 41

The Problem

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

The Solution

So, this seems straightforward enough. We need to take the digits 1..9 and generate all possible combinations of them and then determine if they are prime or not.

We'll start with a pair of functions I got from this Stack Overflow question. I use these functions over and over again, and not just for solving Project Euler problems. I have these in lots of production code. They are super useful. Thank you Jon Harrop.

let rec distribute e = function
    | [] -> [[e]]
    | x::xs' as xs -> (e::xs)::[for xs in distribute e xs' -> x::xs]
let rec permute = function
    | [] -> [[]]
    | e::xs -> List.collect (distribute e) (permute xs)

The distribute function distributes a value e across all possible locations in a list. So, if you execute distribute 1 [2; 3] you get:

  • [1; 2; 3]
  • [2; 1; 3]
  • [2; 3; 1]

The permute function recursively loops through each item in the input and uses distribute to distribute that element through all positions. So if you execute permute [1; 2; 3] you get:

  • [1; 2; 3]
  • [2; 1; 3]
  • [2; 3; 1]
  • [1; 3; 2]
  • [3; 1; 2]
  • [3; 2; 1]

That's great, but in addition to all the permutations of a list [1..n] we also need the permutations of [1..n-1] and [1..n-2] and so on.

let getPermutations l =
    l |> List.collect (fun e -> [1..e] |> permute)

The getPermutations function takes a list and, for each element e in the list, generates a new list [1..e] and all of its permutations.

Next, we'll steal some code from another problem for determing if a 64-bit number is prime.

let int64sqrt (i : int64) = int64(sqrt(float i))

let isPrime64 (i : int64)  =
    if i <= 1L then false
    elif i = 2L then true
    elif (i &&& 1L) = 0L then false
    else
        let sr = int64sqrt i
        seq { 3L..2L..sr } |> Seq.forall (fun f -> i%f<>0L)

And now we can solve the problem:

[1..9]
|> getPermutations
|> List.map (fun l -> System.String.Join("", l |> List.map string))
|> List.map int64
|> List.filter isPrime64
|> List.max

The code above generates all permutations of [1..9], turns those lists into strings, converts those strings to 64-bit integers, and filters out anything that isn't prime. The maximum value of the resulting list is the answer.

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.