# Posts Tagged “fsharp”

### The Problem

There are exactly ten ways of selecting three from five, 12345:

123, 124, 125, 134, 135, 145, 234, 235, 245, and 345

In combinatorics, we use the notation, 5C3 = 10.

In general, ,where r ≤ n, n! = n×(n−1)×...×3×2×1, and 0! = 1.

It is not until n = 23, that a value exceeds one-million: 23C10 = 1144066.

How many, not necessarily distinct, values of nCr, for 1 ≤ n ≤ 100, are greater than one-million?

### The Solution

Thankfully, the problem definition has already given us the hard part of this problem. That is, figuring out the number of combinations for nCr.

The words "in general" in the problem definition made me nervous, but I couldn't think of any special cases that would apply here.

``````let rec fact n =
match n with
| 0 -> 1I
| 1 -> 1I
| _ -> bigint(n) * fact (n-1)

let rec numCombos n r =
fact n / ((fact r) * (fact (n - r)))
``````

The `numCombos` function returns the number of combinations for a given `n` and `r`.

Now we can solve the problem:

``````seq {
for n in 1..100 do
for r in 1..n do
yield (n,r)
}
|> Seq.map (fun (n,r) -> numCombos n r)
|> Seq.filter (fun n -> n > 1000000I)
|> Seq.length
``````

The problem definition specifies 1 ≤ n ≤ 100. Therefore 1 ≤ r ≤ n because you can't take more from n than n.

We'll start by generating a sequence of all possible `n` paired with the possible `r` values for that `n`.

Next, we generate the number of combinations for each `(n,r)` pair.

Finally we filter out the values where the number of combos is more than one million and count them. That is the answer.

Mood

### The Problem

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

### The Solution

Now that we've passed problem 50, the problems start to get harder. I'm going to skip around a bit. I've gone directly from problem 50 to 52 because I haven't (yet) made my problem 51 solution sufficiently fast. But I'm getting there.

To solve this problem, the first thing we need is a function to determine if `n` times `m` contains the same digits as as `n`.

``````let checkMultiple (n : int) (ns : string) (m : int) =
let multiple = (n * m).ToString()
multiple.Length = ns.Length &&
(ns |> Seq.forall (fun d -> multiple.IndexOf(d) >= 0))
``````

The `checkMultiple` function takes a number, a string representation of that number, and a multiplier as input. It multiplies `n * m` and converts the result to a string. If that string has the same length as `ns` and contains all the same characters as `ns`, then we've found a match.

``````let isAnswer n =
let ns = n.ToString()
seq { 2..6 }
|> Seq.forall (fun m -> checkMultiple n ns m)
``````

The `isAnswer` function examines an `n`. If the `checkMultiple` function returns `true` for `n` multiplied by 2..6, then it returns `true`.

Now we can find the answer.

``````seq { 1..System.Int32.MaxValue }
``````
Mood

### The Problem

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

### The Solution

Problem 50! I think after solving this one, I earn some sort of prize. I'm hoping for a luxury vacation, but I'm not holding my breath.

The first thing we need is the list of primes below 1000000. We'll start by stealing some code from problem 35 to generate those.

``````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 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

[<Literal>]
let target = 1000000

let primes = getPrimesBelow target |> List.ofSeq
``````

Now we have a list of primes. The plan of attack is to go through each and find the starting prime of the sequence that, when summed, adds up to a prime number `n`.

``````let isSumOfConsecutivePrimes n =
let rec isSum candidates sum len =
match candidates with
| [] -> None
| x::xs ->
let newSum = sum + x
let newLen = len + 1
if newSum = n then Some(newLen)
elif newSum > n then None
else
isSum xs newSum newLen

let rec findStartingPrime candidates =
match candidates with
| [] -> None
| x::_ when x > n -> None
| x::_ when x = n -> Some(n,1)
| x::xs ->
match isSum xs x 1 with
| Some l -> Some(n,l)
| _ -> findStartingPrime xs

findStartingPrime primes
``````

`isSumOfConsecutivePrimes` starts by looping through each prime and determining if that prime is the start of the sequence we're looking for. The internal function `isSum` takes the list of subsequent primes, the current sum, and the length of the current sequence. If it gets to the end of the list of primes, it returns `None`. Otherwise, if it hits the sum we're looking for, it returns the length of the sequence that generated the sum.

This is a brute force way of solving the problem. I am certain there are other, better ways to do it. But this one works.

Full disclosure: in order to get this to run under the 1-minute time limit, I had to compile it with full code optimizations turned on. To get it to run in under a minute in FSI, I had to run it in parallel.

``````#time
primes
|> Seq.map isSumOfConsecutivePrimes
|> Seq.choose (fun x -> x)
|> Seq.maxBy (fun (_,len) -> len)
|> fst
#time
``````

And here's the parallel version:

``````let isSumOfConsecutivePrimesAsync n = async {
return isSumOfConsecutivePrimes n
}

#time
primes
|> Seq.map isSumOfConsecutivePrimesAsync
|> Async.Parallel
|> Async.RunSynchronously
|> Seq.choose(fun x -> x)
|> Seq.maxBy (fun (_,len) -> len)
|> fst
#time
``````

Mood

### 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
``````

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.

Mood

### 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.

Mood

### 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
elif n % x = 0 then
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])
#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.

Mood

### 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)

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

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)
|> 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.

Mood

### 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 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)
``````

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.

Mood

### 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.

Mood

### 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.

Mood

### 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)

|> 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.

Mood

### 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.

Mood

### 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.

Mood

### The Problem

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

### The Solution

So, the solution to this is fairly straightforward. The general plan of attack is to:

• Generate all the possible `p` values
• For each `p`, generate `a` and `b` values that fit within `p`
• With `a` and `b` we can compute `c` as `p-(a+b)`
• If `a*a + b*b = c*c` then we know we have a right triangle
• Count the number of right triangles we can make
• The `p` that is able to make the most right triangles is the answer.

Almost all of that is easy. The hard question is: how do you generate the `a` and `b` values?

You could simply say that `a` is `1..p-1` and `b` is `1..p-a`. However, this generates a lot of combinations and, on the machine I originally used for this problem, it blew out the 1-minute time limit.

So we need better limits for `a` and `b`.

I am not a math guy, which limits my ability to solve some of these problems. So I consulted my friend Tony Jenkins who is a math guy who explained it to me like this:

We observe that `c` must always be greater than `a` or `b`, so we see that the maximum value of `c` in relation to `p` occurs when either `a` or `b` approaches 0.

Start with the Pythagorean Theorem. Let `b=0`. Then `a*a = c*c` which implies `a=c`. We already stated that `c>a`.

Now apply the definition of the perimiter. `a+b+c = p`, but we know that `b = 0` so `a + c = p`.

Substitution: `a = c`, which implies `2*c = p`.

Bring it all together: Divide by 2 and acknowledge the inequality to get:

`c < 0.5` so we have our upper bound for `c` for a right triangle of perimiter `p`.

Now let's find the lower bound.

Observing our right triangle, we see that `c` min in relation to `p` occurs when `a = b`.

Back to the Pythagorean Theorem:

`a*a + b*b = c*c`

Substitution:

Let `a = b`. Then `(2*a)*(2*a) = c*c`

Solve for `a`:

`a = c / sqrt 2`

We know `a + b + c = p`. Substitute for `a` and we get:

`2 * (c / sqrt 2)) + c = p` => `(2/sqrt 2 ) * c + c = p`

Factor out `c`

`c * (1 + (2/sqrt 2)) = p`

Solve for `c`:

`c = p/((1 + (2/sqrt 2)))`

So after rationalizing the denominator:

`c = (sqrt 2 – 1) * p` (our lower bound for `c`, on a right triangle of perimeter `p`).

`c` is approximately `0.41 * p`

So, for right triangles of hypoteneuse `c`, with perimeter `p`:

`.41p <= c < .5p`

Whew! Thanks, Tony!

In retrospect, I remember enough algebra and geometry to have figured this out on my own, but it helps to have an authoritative answer.

What this means for me, practically speaking, is that when generating my sequence of `a,b` I can cap them out at about `0.59 * p`. I'll still be generating invalid combinations, but we can filter those out later. The point is to limit the combinations we generate as best we can from the get-go and only apply more complex filters if we have to. This makes things faster.

With that in mind, we can generate possible `a,b` values for `p`. We'll let `a` go all the way to the upper bound, and restrict `b` to the upper bound minus `a`.

``````let generateAB p =
seq {
for a in 1..(59*p/100) do
for b in 1..(59*p/100 - a) -> (a,b)
}
``````

Now we'll generate right triangles that fit inside `p`:

``````let isRight a b c = a*a+b*b=c*c

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

let generateTriangles p =
generateAB p
|> Seq.map (fun (a,b) -> (a,b,intsqrt(a*a+b*b)))
|> Seq.filter (fun (a,b,c) -> a + b + c = p && isRight a b c)
|> Seq.map (fun (a, b, c) -> [a; b; c] |> List.sort)
|> Seq.distinct
``````

The `generateTriangles` function starts by generating the possible `a` and `b` values.

Next, it computes `c` using the Pythagorean Theorem.

Next, it filters out any `a,b,c` that isn't a right triangle.

Finally, it converts the tuple to a `List`, sorts it, then filters out any duplicates.

Now we can get the answer:

``````#time
[3..1000]
|> List.map (fun p -> (p,generateTriangles p))
|> Seq.maxBy (fun (_,l) -> Seq.length l)
|> fst
#time
``````

We start with the list of possible `p` values. We start at 3 because the problem definition specifies that the side lengths are integers. The smallest `p` is 3, i.e. when `a` and `b` and `c` are all 1.

We map the list of `p` to the right triangles that fit within it, find the `p` with the maximum number of right triangles, and that is our answer.

Mood

### The Problem

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192 192 × 2 = 384 192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

### The Solution

This is one of those problems where it helps to solve parts of the problem by analysis before proceeding on with a computational solution. I'm a programmer, so every problem I encounter looks like it can be solved with software, and my immediate reaction is usually to start coding and figure out all those pesky details later. It's a reflex I constantly have to suppress.

In order to satisfy the problem definition, all of our answers must be exactly 9 digits long. So, we know two things right off the bat:

• n can't be greater than 9 because that would result in numbers > 9 digits
• The integer being multiplied by the sequence cannot be > 10000, because 10000 concatenated with our smallest sequence (1,2) would yield a number of more than 9 digits.

Knowing these limits, the problem is pretty easy.

``````let concatProduct i s =
let muln x = string(x * i)
bigint.Parse(System.String.Join("", s |> Seq.map muln))
``````

The `concatProduct` function takes an integer `i` and a sequence of other integers `s`. It multiplies each `s` by `i`, converts that to a string, and returns all those strings concatenated.

``````let digitStrings = [1..9] |> List.map string

let isPandigital n =
let str = n.ToString()
if str.Length <> 9 then false
else
digitStrings
|> List.forall (fun x -> str.IndexOf(x) >= 0)
``````

The `isPandigital` function checks to make sure we have a string exactly 9 characters long and then uses `List.forall` to make sure each character, 1-9, is in the string.

Now, solving the problem is easy:

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

cartesianProduct (seq { 1..9999}) (seq { 2..9 })
|> Seq.map (fun (i,n) -> concatProduct i (seq { 1..n } ))
|> Seq.filter isPandigital
|> Seq.max
``````

We start by generating the cartesian product of `seq { 1..100000 }` with `seq { 2..9 }`.

Next, we map each pair to the the concatenatedProduct of `i` and `seq { 1..n }`.

Finally, we filter out any product that isn't pandigital and return the maximum, which is the answer to the problem.

Mood

### The Problem

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

### The Solution

Well, it seems like just a couple of days ago we were writing functions to generate primes below a certain number. Let's copy those here:

``````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 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
``````

Now we'll start focusing on the problem by determining if a number is a "truncatable prime" starting from the left.

``````let isTruncatablePrimeLeft n =
let rec isTruncatable s =
match s with
| "" -> true
| _ ->
if isPrime (int(s)) then isTruncatable (s.Substring(1))
else false
isTruncatable n
``````

The function above recurses over and over, chopping off the left digit each time, and checks to see if the resulting number is prime. If we get to an empty string, then all previous numbers have been prime and we return `true`.

``````let isTruncatablePrimeRight n =
let rec isTruncatable s =
match s with
| "" -> true
| _ ->
if isPrime (int(s)) then isTruncatable (s.Substring(0, s.Length - 1))
else false
isTruncatable n
``````

`isTruncatablePrimeRight` works the same way, except it truncates characters from the right.

And now we can solve the problem:

``````let isTruncatablePrime n = (isTruncatablePrimeLeft n) && (isTruncatablePrimeRight n)

getPrimesBelow 1000000
|> Seq.filter (fun x -> x >= 11)
|> Seq.filter (fun x -> isTruncatablePrime (x.ToString()))
|> Seq.take 11
|> Seq.sum
``````

We combine the left and right tests into a single function called `isTruncatablePrime`.

Then it's a simple matter of generating the sequence of primes and testing it.

Mood

### The Problem

The decimal number, 585 = 10010010012 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

### The Solution

The one is pretty easy. The hardest part, if you can call it that, is turning a number into a string of binary digits.

``````let rec intToBinary i =
match i with
| 0 | 1 -> string i
| _ ->
let bit = string (i % 2)
(intToBinary (i / 2)) + bit
``````

The `intToBinary` function simply divides the input by 2 over and over again until the value reaches 0 or 1. This final value is the value of the last binary digit. Before each division, we find `i % 2` which equals the next digit in the series. Concatenate them all together and you have a string of binary digits.

Now, we can find out if a string is a palindrome.

``````let isPalindrome n =
let s = n.ToString()
let r = System.String.Join("", s |> Seq.rev)
s = r
``````

The `isPalindrome` function simply reverses the string and compares it against the input. If they are equal, it's a palindrome.

Now we can solve the problem:

``````#time
seq { 1..999999 }
|> Seq.filter isPalindrome
|> Seq.filter (fun x -> isPalindrome (intToBinary x))
|> Seq.sum
#time
``````

We generate the sequence 1..999999 and filter out any number that is not a palindrome. Then we convert the resulting numbers to binary strings and filter out any of those that aren't palindromes. The answer is the sum of the resulting sequence.

Mood

### The Problem

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

### The Solution

We'll start with some helper functions that we've used over and over again in this series. We need to turn a string into a sequence of digits, and generate a sequence of primes below 1 million.

``````let digitize n =
let str = sprintf "%i" n
str |> Seq.map (fun x -> int(x) - int('0'))

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 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
``````

We've covered all this ground before. In Problem 3, for example. So, I won't go into the details of these functions.

Next, we need to figure out how to generate all the rotations of a number.

``````let rotate step l =
let l1,l2 = l |> List.splitAt step
List.append l2 l1

let toNumber (l : int list) =
l
|> Seq.rev
|> Seq.mapi (fun place d -> d * (pown 10 place))
|> Seq.sum

let rotationsOf n =
let digits = digitize n |> List.ofSeq
[for i in 1..((List.length digits) - 1) -> digits |> rotate i] |> List.map toNumber
``````

The `rotate` function takes as input an integer `step` and a list of digits. It uses `List.splitAt` to break the list into two chunks, and then uses `List.append` to generate a new list with the second chunk at the front. So, using the problem's example of 197, we can get the other 2 rotations as follows:

``````rotate 1 [1; 9; 7] = [9; 7; 1]
rotate 2 [1; 9; 7] = [7; 1; 9]
``````

The `toNumber` function takes a list of digits and turns them back into a number. It does this by reversing the order of the list, mapping each element in the list to d * 10place, and them summing the result. Some experimenting I did later shows that it is just as fast, if not faster, to convert the digits to a string and then use the built-in CLR functions for converting `string` to `int`, but this way is more fun so I left it as-is.

Now, we can figure out if a given number is a circular prime.

``````let isCircularPrime n =
rotationsOf n
|> List.forall isPrime
``````

`isCircularPrime` tests all rotations of `n` to see if they are prime and returns true if they are. We don't need to test `n` itself because we already know it's prime. Testing primes is computationally expensive, so eliminating that one redundant check reduces program execution time by almost 30%.

And now we can get the answer:

``````#time
getPrimesBelow 1000000
|> Seq.filter isCircularPrime
|> Seq.length
#time
``````

We generate a sequence of all primes below one million, filter out the ones that aren't circular, and return the length of the resulting sequence, which is the answer.

Mood

### The Problem

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: as 1! = 1 and 2! = 2 are not sums they are not included.

### The Solution

As usual, we'll start out with some helper functions.

``````let digitize (n : bigint) =
let str = n.ToString()
str |> Seq.map (fun x -> int(x) - int('0'))

let rec factorialBig n =
match n with
| 0 -> 1I
| 1 -> 1I
| _ -> bigint(n) * factorialBig (n-1)

let facts =
[0..9]
|> List.map (fun x -> (x,factorialBig x))
|> Map.ofList
``````

`digitize` is a function I use over and over in these Project Euler problems. It converts a number into a sequence of digits.

The `factorialBig` function is the classic recursive factorial function using `BigInteger` values.

During the course of execution, we're going to need the factorial for the numbers 0-9 over and over and over again. So we'll pre-generate all those and turn them into a `Map` so we can quickly look them up later.

``````let factorialSum n =
digitize n
|> Seq.map (fun x -> facts.[x])
|> Seq.sum
``````

The `factorialSum` function turns a number into digits, maps those digits to their factorials, and then returns the sum of those.

With that in hand, we can solve the problem:

``````#time
seq { 3I..99999I }
|> Seq.filter (fun x -> factorialSum x = x)
|> Seq.sum
#time
``````

I love it when Project Euler problems use the wording "all numbers". That means it's our job to figure out where the program is supposed to stop, otherwise we can just keep looking at numbers forever. I arbitrarily chose to stop looking after 5 digits, and it turns out that works.

Mood

### The Problem

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

### The Solution

Expressed as a ratio of "lines of text in the problem definition" to "lines of code in the solution", this is one of my longer solutions. But it works. We'll start out with some helper functions.

``````let digitize n =
let str = sprintf "%i" n
str |> Seq.map (fun x -> int(x) - int('0'))

let remove element s =
s |> Seq.filter (fun x -> x <> element)

let doubleDigits = set [11; 22; 33; 44; 55; 66; 77; 88; 99 ]
let isDoubleDigit n = Set.contains n doubleDigits

let rec gcd x y = if y = 0 then abs x else gcd y (x % y)

let fractionsEqual n1 d1 n2 d2 =
(double(n1) / double(d1)) = (double(n2) / double(d2))

let commonDigit numeratorDigits denominatorDigits =
seq { 1..9 }
|> Seq.tryFind (fun x ->
(Seq.contains x numeratorDigits) &&
(Seq.contains x denominatorDigits))
``````

The `digitize` function takes a number and turns it into a sequence of digits.

The `remove` function takes a sequence and removes a single element from it.

The set `doubleDigits` and the corresponding function `isDoubleDigit` will be used to filter out fractions that have double digits in the numerator or denominator.

The `gcd` helper function is the classic recursive Greatest Common Denominator algorithm. We use this to reduce the fractions we find to their "lowest common terms", per the problem definition.

To determine if two fractions are equal, we'll use the `fractionsEqual` function to divide numerators by denonominators and compare the result. I was actually afraid this wouldn't work due to the imprecision of floating point numbers, but I managed to get the right answer using it, so I decided to not try to do a better job here.

And finally, we need a function to find the common digit between a numerator and a denominator. The `commonDigit` function looks for all digits, 1 through 9, and checks to see if that digit exists in both the `numeratorDigits` and `denominatorDigits`.

Now we can get to the meat of the problem: determining if a numerator and a denominator are an example of a non-trivial digit-cancelling fraction.

``````let isNonTrivialDigitCancellingFraction numerator denominator =
if numerator = denominator then false
else
let numSeq = digitize numerator
let denSeq = digitize denominator
let common = commonDigit numSeq denSeq
match common with
| None -> false
| Some d ->
let newNum = numSeq |> remove d |> Seq.exactlyOne
let newDen = denSeq |> remove d |> Seq.exactlyOne
match newDen with
| 0 -> false
| _ -> fractionsEqual numerator denominator newNum newDen
``````

The function above returns false if `numerator` and `denominator` are equal. Otherwise, it turns the numbers into sequences of their digits and looks for the common digit between them. If one exists, then it removes that digit from numerator and denominator and then returns `true` if the new fraction is equal to the original.

And now we can solve the problem:

``````let num,den =
seq {
for num in 12..97 do
for den in (num+1)..98 -> (num,den)
}
|> Seq.filter (fun (num, den) -> not(isDoubleDigit num) && not(isDoubleDigit den))
|> Seq.filter (fun (num,den) -> isNonTrivialDigitCancellingFraction num den)
|> Seq.reduce (fun (num,den) (x,y) -> (num*x,den*y))

den / gcd num den
``````

The above starts by generating possible numerators and denominators.

When generating the numerator, we can skip all the single digit numbers, skip 10 because it has a 0 in it, and skip 11 because it's a double digit. We generate numerators up to 97 because the largest denominator is 98 because the denominator has to be larger than the numerator. Thus, when we generate the denominator, we start at `num+1`.

Next, we remove any elements where there is a double digit number in the numerator or the denominator. You may notice we are not filtering out numbers that end with 0. We could do that, but we don't really need to because `commonDigit` only considers the digits 1-9.

Then, we filter out anything that isn't a non-trivial digit-cancelling fraction.

Then, we use `Seq.reduce` to yield the product of all the fractions we found.

Finally, the problem definition asks for the denominator if the product fraction is expressed in lowest common terms. We find this by dividing the denominator by the Greatest Common Divisor of the numerator and denominator. This is our answer.

Mood

### 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, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

### The Solution

Let's start about by writing a function to figure out if two factors and their product form a "1 through 9 pandigital".

``````let allDigits = ['1'..'9']

let isPandigital9Product n1 n2 prod =
let containsAllDigits (digits : string) =
allDigits |> List.forall (fun c -> digits.IndexOf(c) >= 0)

let digits = sprintf "%i%i%i" n1 n2 prod
if digits.Length <> 9 then false
else containsAllDigits digits
``````

The `isPandigital9Product` function takes two numbers and their product and then turns them into a string. If the number of digits isn't 9, then we return `false`, otherwise we determine if all the digits 1..9 are found in the string.

Next, we need to generate all possible combinations of factors. We'll do this by cross-joining the sequence 1..9999 with itself.

Unfortunately, this generates nearly 100 million factors, and running our pandigital test on that many combinations makes us exceed our 1-minute time limit. I can't see a way to speed up the test very much, so the way to speed things up is to limit the number of factors we try. For every factor we eliminate, we eliminate almost 10,000 combinations.

The most obvious way I can see to do this is to eliminate all factors that have duplicate digits in them and any factors containing the digit 0. Doing this reduces the number of possible factors from 9999 to 3609. Which means that instead of testing 99,980,001 combinations, we only have to test 13,024,881, an 87% reduction. Not bad!

So let's get our combinations of factors:

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

let containsUniqueDigits n =
let digits = sprintf "%i" n
digits.IndexOf('0') < 0 &&
digits.Length = (digits |> Seq.distinct |> Seq.length)

let factors = [1..9999] |> List.filter containsUniqueDigits
``````

And now we can get the answer.

``````#time
cartesianProductSeq factors factors
|> Seq.map(fun (n1,n2) -> (n1,n2,n1*n2))
|> Seq.filter(fun (n1,n2,prod) -> isPandigital9Product n1 n2 prod)
|> Seq.map(fun(_,_,prod) -> prod)
|> Seq.distinct
|> Seq.sum
#time
``````

The above generates all the combinations of factors, combines them with their products, filters out all those that aren't pandigital, then finds the sum of the distinct products.

Mood

### The Problem

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

### The Solution

In retrospect, this is not some of my best work. But it gets the job done.

Since this is a problem of combinations, I figured the first step was to generate all the things that could be combined to get the answer.

``````[<Literal>]
let target = 200

let coins = [1; 2; 5; 10; 20; 50; 100; 200]
let combos =
coins
|> List.map (fun x -> [for i in 0..(target / x) -> (i,x)])
``````

The above declares a list of coins and from that creates all lists of coin combinations. `combos` is a list of lists of tuples. Each tuple is the number of coins and the coin value. We only consider combinations up to `target/x` because, obviously, any solutions containing those combinations would be wrong.

Now, a few helper functions:

``````let coinValue (a,b) = a * b

let sumPile (pile : List<int * int>) =
pile
|> List.sumBy coinValue

let matchTarget pile =
sumPile pile = target
``````

`coinValue` takes a tuple and multiplies the numbers together to get the value of that combination of coins.

`sumPile` takes a pile of coins and gets the total value.

`matchTarget` tells us whether or not a pile of coins matches our target of 200.

So, now we need a function to combine the combinations of coins. This gets a little bit tricky.

``````let combine() =
let rec combineRec prefix prefixSum suffixes =
seq {
if prefixSum >= target then
yield prefix
else
match suffixes with
| [] -> yield prefix
| x::xs ->
for c in x do
yield! combineRec (c::prefix) (prefixSum + coinValue c) xs
}

combineRec [] 0 combos
``````

The `combineRec` function takes a `prefix` (some combination of coins) and a list of possible `suffixes` (other combinations of coins we haven't considered). It combines the prefix with all possible suffixes and looks at the value. If it's greater than or equal to our target, it returns that combination. Otherwise, it keeps generating more combinations. Eventually, we get lots and lots of combinations, and all the ones that match our target are in there somewhere.

``````#time
combine()
|> Seq.filter matchTarget
|> Seq.length
#time
``````

The above simply generates all the combinations, filters out those that don't match the target, and finds the length of the sequence. That's the answer.

This takes about 42 seconds to run on my machine. I wasn't really happy with that, so only then did I set about investigating if there was a better way to solve the problem.

As it turns out, there is a well-known algorithm for this called the Coin Change Algorithm.

Because of course there is. Darn it. Here is the very simple implementation of that algorithm that runs in about half a second.

``````let coinsArray = [| 1; 2; 5; 10; 20; 50; 100; 200 |]
let rec coinChange n m =
if n = 0 then 1
elif n < 0 then 0
elif m <= 0 && n >= 1 then 0
else (coinChange n (m - 1)) +
(coinChange (n - coinsArray.[m-1]) m)

#time
coinChange target coins.Length
#time
``````
Mood

### The Problem

Surprisingly there are only three numbers that can be written as the sum of fourth powers of their digits:

1634 = 14 + 64 + 34 + 44

8208 = 84 + 24 + 04 + 84

9474 = 94 + 44 + 74 + 44

As 1 = 14 is not a sum it is not included.

The sum of these numbers is 1634 + 8208 + 9474 = 19316.

Find the sum of all the numbers that can be written as the sum of fifth powers of their digits.

### The Solution

This one is pretty easy. The trickiest part is the requirement that we find "the sum of all the numbers". Since there are an infinite number of integers, we first have to figure out where to stop.

95 is 59049. Eventually we will get to a number of digits n such that 10n > 95*n. It turns out that n is 6. So we only have to concern ourselves with numbers less than a million.

We'll start by cracking a number into its digits, raising those to the 5th power, and getting the sum.

``````let digitize n =
let str = sprintf "%i" n
str |> Seq.map (fun x -> int(x) - int('0'))

let pow5 n = n*n*n*n*n

let powsum n =
digitize n
|> Seq.map pow5
|> Seq.sum
``````

The `digitize` function takes a number, converts it to a string, and then converts the individual characters in that string to digits.

The `pow5` function multiples n by itself to get the 5th power. For 5th powers, this is about twice as fast as the built-in `pown` function. For higher powers, it might not be. I haven't tested it.

Finally, `powsum` puts the other two functions together to find the sum of the 5th powers of the digits of a number.

Now we can solve the problem:

``````let isSumOfPowers n =
powsum n = n

#time
seq { 2..999999 }
|> Seq.filter isSumOfPowers
|> Seq.sum
#time
``````

The above finds all the numbers between 2 and 999999 that meet the problem definition and sums them.

Mood

### The Problem

Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:

• 22=4, 23=8, 24=16, 25=32
• 32=9, 33=27, 34=81, 35=243
• 42=16, 43=64, 44=256, 45=1024
• 52=25, 53=125, 54=625, 55=3125

If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:

4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125

How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

### The Solution

Unless you're working in assembly language, this problem is pretty trivial. It almost seems designed for a functional language with a focus on pipelines. Fortunately for us, we're working with one of those.

Here's the solution in all its glory:

• Start by generating a sequence of all possible `a,b` pairs.
• For each of those, get ab
• Filter out the duplicates
• Count what we have left
``````seq {
for a in 2I..100I do
for b in 2..100 -> a,b
}
|> Seq.map (fun (a,b) -> pown a b)
|> Seq.distinct
|> Seq.length
``````
Mood

### The Problem

Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

### The Solution

Full disclosure: when I originally solved this, I went about it all wrong. I was too focused on getting the answer and not focused enough on analyzing the problem.

My original solution had a complicated function that determined which way to move next based on current direction and position. It was a `match` statement with 9 different conditions. I was just learning to use F#'s active patterns and every solution looked like it needed active patterns to me. Here's what I came up with:

``````let size = 1001

type Direction = Up|Down|Left|Right

let getNextDirection (grid : int[,]) x y direction =
match direction,x,y with
| Left,x,_ when x = 0 -> Down
| Left,x,y when grid.[x-1,y] <> 0 -> Down
| Down,_,y when y = (size - 1) -> Right
| Down,x,y when grid.[x,y+1] <> 0 -> Right
| Right,x,_ when x = (size - 1) -> Up
| Right,x,y when grid.[x+1,y] <> 0 -> Up
| Up,_,y when y = 0 -> Left
| Up,x,y when grid.[x,y-1] <> 0 -> Left
| _ -> direction
``````

I used the function above in a loop to "draw" the spiral and sum elements on the diagonals.

This is exactly the wrong approach. Here's a much better solution.

Each internal "ring" of the spiral forms a square with a side length of `n`. `t` is the total of the numbers in the previous ring. The numbers on the diagonals can all be expressed in terms of `n` and `t`. For example, when `n` is 3 and `t` is 1, then the 4 diagonals are:

• `t+(n-1)*1` = `1+(3-1)*1` = 3
• `t+(n-1)*2` = `1+(3-1)*2` = 5
• `t+(n-1)*3` = `1+(3-1)*3` = 7
• `t+(n-1)*4` = `1+(3-1)*4` = 9

The side length goes up by 2 each time. For the next side length, 5, we get:

• `t+(n-1)*1` = `9+(5-1)*1` = 13
• `t+(n-1)*2` = `9+(5-1)*2` = 17
• `t+(n-1)*3` = `9+(5-1)*3` = 21
• `t+(n-1)*4` = `9+(5-1)*4` = 25

The diagonals are all we care about, so we can ignore all the other numbers.

Knowing that, we'll first write a function to return the 4 diagonals for a given `total` and `sideLength`:

``````let diagonals total sideLength =
let inc = sideLength - 1
let dv n = total + inc * n
[| 1..4 |] |> Array.map dv
``````

Next, we construct a loop to keep calling `diagonals` and incrementing the `sideLength` until we get our answer.

``````let rec loop total sideLength diagonalSum =
let newLength = sideLength + 2
let diags = diagonals total newLength
let newSum = diagonalSum + Array.sum diags
if newLength = 1001 then
newSum
else
loop diags.[3] newLength newSum

loop 1 1 1
``````

The `diagonals` function returns the 4 diagonals for a given side length. The `loop` function figures out the next side length, gets its diagonals, and adds them to the sum. If we've hit a ring of side length 1001, it returns the total, otherwise it repeats the process.

Mood

### The Problem

Euler discovered the remarkable quadratic formula:

n2+n+41n2+n+41

It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤39. However, when n=40,402+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,412+41+41 is clearly divisible by 41.

The incredible formula n2−79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤790≤n≤79. The product of the coefficients, −79 and 1601, is −126479.

n2+an+b, where |a|<1000 and |b|≤1000

where |n| is the modulus/absolute value of n e.g. |11|=11 and |−4|=4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.

### The Solution

First, we'll define our boundaries.

``````[<Literal>]
let maxA = 999L

[<Literal>]
let maxB = 1000L
``````

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)
``````

I can't think of a more efficient way to solve the problem other than testing all possible coefficients, so let's generate all possible pairs of `a` and `b`.

``````let coefficients = [|
for a in -maxA..maxA do
for b in -maxB..maxB do
yield (a,b)
|]
``````

And we need a function for computing "quadratics of the form n2 + an + b".

``````let quadratic (n : int64) (a : int64) (b : int64) = n*n + a*n + b
``````

Now, for a given `a` and `b` we can find the number of primes produced. Here is a recursive function that keeps incrementing `n` until a non-prime occurs, then returns the count.

``````let numPrimesProduced (a : int64) (b : int64) =
let rec numPrimes n =
if isPrime64 (quadratic n a b) then numPrimes (n + 1L)
else n

numPrimes 0L
``````

Finally, we can solve the problem:

``````#time
let a,b,n =
coefficients
|> Seq.map (fun (a,b) -> (a,b,(numPrimesProduced a b)))
|> Seq.maxBy (fun (a,b,n) -> n)
#time
a*b
``````

With all the coefficient pairs as inputs, we generate the number of primes produced, then find the pair with the maximum `n`. The answer is `a*b`.

Mood

### The Problem

Find the index of the first number in the Fibonacci sequence to contain 1000 digits.

### The Solution

Once again, it's `BigInteger` to the rescue. It is very easy to generate the Fibonacci sequence.

``````let fibSeq =
let rec fibSeq n1 n2 =
seq { let n0 = n1 + n2
yield n0
yield! fibSeq n0 n1 }
seq { yield 1I ; yield 1I ; yield! (fibSeq 1I 1I) }
``````

We know the first two elements of the sequence are both `1`, so we just yield those directly. For elements after that, we call the recursive `fibSeq` function, which uses `yield` to return the sum of the previous two terms, then uses `yield!` to return the next element in the sequence. This function generates numbers forever, but F#'s sequence magic will only generate the numbers that it needs.

With this in hand, finding the answer is easy.

``````let aThousandDigits = pown 10I 999

#time
fibSeq
|> Seq.findIndex (fun f -> f >= aThousandDigits)
#time
``````
Mood

### The Problem

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

``````   012   021   102   120   201   210
``````

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

### The Solution

The first thing we need to do is write a function to generate permutations.

There are a number of approaches to this. I have yet to find one that I'm really happy with. Obviously, the more elements there are, the more permutations there are and the longer it takes to generate them.

The following function takes an array and returns all of its permutations. It uses a `Set` to keep track of which elements have been used as it recurses over the list of elements.

``````let getPermutations arr =

let rec permutations list taken =
seq {
if Set.count taken = List.length list then
yield []
else
for l in list do
if not (Set.contains l taken) then
for perm in permutations list (Set.add l taken) do
yield l::perm
}

let lst = arr |> List.ofArray
permutations lst Set.empty
``````

Now we can generate permutations of the digits `0123456789`.

``````let input = "0123456789" |> Array.ofSeq
let perms =
getPermutations input
|> Seq.map (fun l -> System.String.Join("", l))
|> Seq.sort
``````

The above generates the permutations. There are 3,628,800 of them. Then it converts each permutation into a string and sorts them. Now we can find the answer.

``````#time
perms |> Seq.item 999999
#time
``````

Since the position is 0-based, the one we want is element 999,999.

If you're like me, you probably noticed two possible optimizations here.

First: Is it strictly necessary to convert all items in the list to a string? Can't we sort it first and then only convert the item we need?

Yes, apparently we do. Even though F# is perfectly capable of comparing two arrays in the manner we need, this is apparently much slower than comparing strings. With the code as written, this executes in 11 seconds on my machine. If I move the string conversion to the end, the program exceeds the 1-minute time limit.

Second: Is that the fastest way to convert an array of digits back into a string? Yes, apparently it is. I have experimented with many different ways to do this (simple concatenation, `StringBuilder`, and others) and nothing really beats this.

Mood

### The Problem

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

### The Solution

We'll start out by stealing the `findDivisors` and `sumDivisors` functions from Problem 21

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

let findDivisors n =
let upperBound = intsqrt n

[1..upperBound]
|> Seq.filter (fun d -> n % d = 0)
|> Seq.collect (fun d -> [d; n/d])
|> Seq.filter (fun d -> d <> n)
|> Seq.distinct

let sumDivisors n = findDivisors n |> Seq.sum
``````

Next, we'll figure out if a number is "abundant" and use it to find all the abundant numbers < 28123. We only care about abundant numbers in this range because the (somewhat wordy) problem definition tells us that all the numbers we're looking for are less than 28123. Thus, even though there may be "abundant numbers" greater than this, we don't care about them.

``````let isAbundant n = sumDivisors n > n

let abundants =
seq { 1..28122 }
|> Seq.filter isAbundant
|> Array.ofSeq
``````

Next, we need a fast way to determine if a given number is the sum of two abundant numbers. We'll create a map by cross joining the array of abundants with itself, computing the sum of each pair, and building a map.

``````let crossSums =
seq {
for a in abundants do
for b in abundants do
let sum = a+b
yield sum,sum
}

let sumMap = crossSums |> Map.ofSeq
``````

With that map in hand, we can find the answer.

``````seq { 1..28123 }
|> Seq.filter (fun i -> not(sumMap.ContainsKey i))
|> Seq.sum
``````

We simply filter out all numbers in the range that don't match one of our previously computed sums. Then we sum the remaining ones.

Mood

### The Problem

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

### The Solution

This one isn't very hard, no matter what language you choose.

First, we'll implement the scoring function from the problem definition.

``````let score (s : string) =
s
|> Seq.map (fun c -> (int c) - int('A'))
|> Seq.sum
``````

Strings can be treated as `Seq<char>`. We convert each character in the string to its numeric value, then sum the result.

Now we'll solve the problem.

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

input
|> splitByMany [|'"';','|]
|> Seq.sort
|> Seq.mapi (fun i name -> (i+1) * score name)
|> Seq.sum
``````

The `splitByMany` function is a pipeline-friendly version of `String.Split`. I say it's pipeline-friendly because the parameters are designed such that you can pipe the parameters into it. In this particular case, we're piping the string `input` into it and specifying the text delimiters. This gives us the list of names.

Next, we sort the list alphabetically, then compute a value for the name based on its position in the list.

Finally, we sum those values and get our answer.

Mood

### The Problem

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n ).

If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

### The Solution

First, we have to find all the divisors of a given n.

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

let findDivisors n =
let upperBound = intsqrt n

[1..upperBound]
|> Seq.filter (fun d -> n % d = 0)
|> Seq.collect (fun d -> [d; n/d])
|> Seq.filter (fun d -> d <> n)
|> Seq.distinct
``````

Like some of our prime-finding code, we only have to check for divisors up to the square root of `n`. If `d` is a divisor less than the square root of `n`, then both `d` and `n/d` are divisors of `n`. `findDivisors` checks all numbers up to the square root of `n` for divisibility, and adds any divisors it finds along with `n/d`. Lastly, it filters out `n` itself and uses `Seq.distinct` to make sure it only returns unique divisors.

Next, we need to find out if a given `a` and `b` are "amicable" according to the problem definition.

``````let sumDivisors n = findDivisors n |> Seq.sum

let d =
seq { 1..9999 }
|> Seq.map (fun n -> n,sumDivisors n)
|> Map.ofSeq

let areAmicable (a,b) = d.[a] = b && d.[b] = a
``````

The `sumDivisors` function simply sums the divisors we found above.

Next, we build a map of divisor sums. For the numbers 1 to 9999, `n` is the key and the sum of its divisors is the value.

With that in hand, we can determine if a given `a` and `b` `areAmicable` using the test given in the problem definition.

And now we can look for the answer.

``````seq {
for a in 1..9999 do
for b in 1..9999 do
if a <> b then yield a,b
}
|> Seq.filter areAmicable
|> Seq.sumBy fst
``````

First, we build a sequence of all possible pairs of numbers from 1 to 9999, skipping the case when `a` and `b` are equal. Then we filter out the pairs that `areAmicable` and sum the `a` values to get the answer.

Mood

### The Problem

Sum the digits in 100! (factorial of 100).

### The Solution

.NET's `BigInteger` to the rescue. Again.

First, let's compute the factorial.

``````let rec factorial (n : BigInteger) =
if (n = 1I)
then 1I
else n * factorial (n - 1I)
``````

The above is the classic, recursive implementation of the factorial function.

With that in hand, finding the answer is trivial.

``````(factorial 100I).ToString()
|> Seq.map (fun c -> int32(string c))
|> Seq.sum
``````

The above converts 100! to a string, then converts that into digits and then, finally, sums those digits.

Mood

### A Confession, Before We Begin

I'm skipping problem 18. I solved it under the 1-minute time limit, but I wasn't happy with it. Problem 67 is the same as problem 18, but with a much larger input. My code ran for a long, long time and never came up with the answer. If you're interest in a really good F# solution to that problem, look here. You can compare it to my non-optimal solution:

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

let input = [|
"75"
"95 64"
"17 47 82"
"18 35 87 10"
"20 04 82 47 65"
"19 01 23 75 03 34"
"88 02 77 73 07 63 67"
"99 65 04 28 06 16 70 92"
"41 41 26 56 83 40 80 70 33"
"41 48 72 33 47 32 37 16 94 29"
"53 71 44 65 25 43 91 52 97 51 14"
"70 11 33 28 77 73 17 78 39 68 17 57"
"91 71 52 38 17 14 91 43 58 50 27 29 48"
"63 66 04 68 89 53 67 30 73 16 69 87 40 31"
"04 62 98 27 23 09 70 98 73 93 38 53 60 04 23"
|]

let lineToArray l =
l
|> splitBy ' '
|> Seq.map int
|> Array.ofSeq

let values = input |> Array.map lineToArray
let penRow = values.Length - 2
for y in penRow..(-1)..0 do
for x in 0..values.[y].Length-1 do
values.[y].[x] <- values.[y].[x] +
max values.[y+1].[x] values.[y+1].[x+1]
values.[0].[0]
``````

So, with that behind us, let's move on.

### The Problem

You are given the following information, but you may prefer to do some research for yourself. 1 Jan 1900 was a Monday. Thirty days has September, April, June and November. All the rest have thirty-one, Saving February alone, Which has twenty-eight, rain or shine. And on leap years, twenty-nine. A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400. How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

### The Solution

It may feel like cheating, but I'm not above using the .NET Framework's features to solve these problems. For example, I reduced a couple of problems down to using the `BigInteger` type. I am learning F# for all the advantages it gives me. I want to learn F# and everything about it. To me, that means not solving problems the language and framework have already solved for me. And that includes dates.

``````open System

let last = DateTime(2000,12,31)
let first = DateTime(1901,1,1)

let rec countSundays (day : DateTime) total =
let dayValue() =
if day.Day = 1 && day.DayOfWeek = DayOfWeek.Sunday
then 1
else 0

if day > last then total
else
let newTotal = total + dayValue()
countSundays next newTotal

countSundays first 0
``````

The recursive function `countSundays` takes a `day` parameter and an accumulator `total`. When it reaches the `last` day, it returns the total it has accumulated. Otherwise, it increments the day and adds 1 to the total if the day is a Sunday and also the first day of the month.

Mood

### The Problem

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

### The Solution

Ah, the classics. Converting numbers to words.

I've written dozens of variations of this algorithm in the last 25+ years. It seems every programming class and every language book has a variation of this exercise.

Let's start by making a `Map` that we can use to convert numbers to words.

``````let words = [
1, "one"
2, "two"
3, "three"
4, "four"
5, "five"
6, "six"
7, "seven"
8, "eight"
9, "nine"
10, "ten"
11, "eleven"
12, "twelve"
13, "thirteen"
14, "fourteen"
15, "fifteen"
16, "sixteen"
17, "seventeen"
18, "eighteen"
19, "nineteen"
20, "twenty"
30, "thirty"
40, "forty"
50, "fifty"
60, "sixty"
70, "seventy"
80, "eighty"
90, "ninety"
1000, "one thousand"]

let wordMap = words |> Map.ofList
``````

Since we only have to deal with numbers up to 1000, the algorithm is simple enough:

• If the number exists in our map, return that
• If the number is less than 100, return the word for tens portion and the word for the ones portion.
• Otherwise, the number is > 100 and < 1000. The range is exclusive because the map lookup already covered both 100 and 1000. Thus, all that remains is to compute the word for the hundreds place, and call then call the function recursively for what's left.
``````let rec toWords n =
match wordMap.TryFind n with
| Some v -> v
| _ ->
if n < 100 then
let ones = n%10
wordMap.[n-ones] + "-" + wordMap.[ones]
else
let hundreds = n/100
let tens = n%100
if tens = 0 then
wordMap.[hundreds] + " hundred"
else
wordMap.[hundreds] + " hundred and " + (toWords tens)
``````

With that in place, we get our answer:

``````let charCount s =
s |> Seq.filter (fun c -> c <> ' ' && c <> '-') |> Seq.length

seq { 1..1000 }
|> Seq.map toWords
|> Seq.sumBy charCount
``````
Mood

### The Problem

Compute 21000 and sum its digits.

### The Solution

Like Problem 13, this problem is trivially easy because of .NET's `BigInteger` data type.

``````(pown 2I 1000).ToString()
|> Seq.map (fun c -> int32(c) - int32('0'))
|> Seq.sum
``````

The `pown` function returns 21000 as a `BigInteger`. (Suffixing a numeric literal with `I` means it is a `BigInteger` literal)

Strings can be treated as `Seq<char>` and that's what we do here. We convert each digit into an integer and then finally sum the result.

Mood

### The Problem

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

### A Note Before We Begin

I have seen several, more clever solutions to this problem. I've seen one that starts at the bottom and works up, and another that manages to reduce the problem to a simple equation (the math of which is beyond me). So this isn't the best solution by any stretch, but it's the one that works for me.

### The Solution

This is another problem where pure bute force doesn't do the trick. But let's look at that approach first.

``````[<Literal>]
let GridSize = 20

let countRoutesTo sourceX sourceY destX destY =

let rec count sx sy =
if sx = destX && sy = destY then
1L
elif sx < GridSize && sy < GridSize then
(count (sx+1) sy) + (count sx (sy+1))
elif sx < GridSize then
(count (sx+1) sy)
else
(count sx (sy+1))

let result = count 0 0
result

#time
countRoutesTo 0 0 GridSize GridSize
#time
``````

The internal `count` function is a recursive function that computes all of the routes to `destX,destY`. It works like this:

• If we've hit the bottom right corner, the result is always 1 since we had to have made it there from one of the points adjacent to the bottom corner.
• If we're somewhere in the interior of the grid, we return `count` for a move right plus a `count` for a move down.
• If we're at the bottom edge, we return `count` for a move right.
• Otherwise, we must be at the right edge, so we return `count` for a move down.

The problem with this function is that it takes way too long to execute. I stopped it running after 20 minutes. I know it works in principle because if I reduce `GridSize` to 10, it executes in under a second. The problem is that the number of calls to `count` is a factorial of the GridSize. In fact, you can get the answer to the problem by computing (2n)!/n!2, but I didn't know that when I was writing this :)

My (ahem!) genius solution to the problem was to cache the answers for the lower right 100 squares of the grid, and then apply my brute force algorithm. If the algorithm hits a cached position, it doesn't have to do any more work and just returns the value it's currently computed plus the value from the cache.

This algorithm finds the answer in 22 seconds on my machine.

``````let countRoutesToCached sourceX sourceY destX destY =

let cachePos = GridSize / 2
let cache = System.Collections.Generic.Dictionary<int*int,int64>()

let rec count sx sy =
match cache.TryGetValue((sx,sy)) with
| true,v -> v
| _ ->
if sx = destX && sy = destY then
1L
elif sx < GridSize && sy < GridSize then
(count (sx+1) sy) + (count sx (sy+1))
elif sx < GridSize then
(count (sx+1) sy)
else
(count sx (sy+1))

for x in cachePos..GridSize do
for y in cachePos..GridSize do

let result = count 0 0
result

#time
countRoutesToCached 0 0 GridSize GridSize
#time
``````
Mood

### The Problem

The following iterative sequence is defined for the set of positive integers:

``````    *n → n/2* (*n* is even)
*n → 3n + 1* (*n* is odd)
``````

Using the rule above and starting with 13, we generate the following sequence:

``````    13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
``````

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

### The Solution

I had some fun with this one.

I originally wrote the solution to this on an Alienware laptop with a 2GHz processor and 8 cores. By default, most languages use only one of those cores at a time, so most of my solutions were running on a single core. Most of the time, that’s good enough.

My original solution, however, took long enough to execute that I had enough time to go inside and make a sandwich.

My current laptop has a 3.8Ghz processor and solves the problem in about 3.5 seconds. There has to be some other difference in play here, but I’ll be damned if I can figure out what it is.

Here’s the “purely functional” solution.

``````let isEven i = i &&& 1L = 0L
let (|Even|Odd|) i = if isEven i then Even else Odd

let next n =
match n with
| Even -> n/2L
| Odd -> 3L*n+1L

let collatz n =
let rec c n length =
if n = 1L then length
else c (next n) (length+1L)
c n 1L

#time
seq { 1L..999999L } |> Seq.maxBy collatz
#time
``````

We start with a helper function, `isEven` and an active pattern matching function that will return `Even` or `Odd` for a given number.

The `next` function finds the next number in the sequence based on the rules in the problem definition.

The `collatz` function uses a tail-recursive function to generate the length of the sequence.

Back when this was taking forever to execute, I tried three more solutions to the problem. I’ll outline them here as a learning experience.

#### Attempt #2

Since the functional approach wasn’t working for me, I tried a solution that uses mutables.

``````let collatzWithMutables start =
let mutable count = 1L
let mutable current = start

while current > 1L do
current <- next current
count <- count + 1L
count

#time
seq { 1L..999999L } |> Seq.maxBy collatzLength
#time
``````

That executes in 3.3 seconds on my machine. I’m not happy about a 5.7% reduction in speed. I think we can do better.

#### Attempt #3

The length of the sequence starting with `n` is constant. I figured that it was highly likely I would be encountering the same values over and over. If you encounter an `n` for which you’ve already computed the length, it’s not necessary to compute it again. Just add what you have now to the already-computed length for `n`.

Let’s try that:

``````let cache = System.Collections.Generic.Dictionary<int64,int64>()

let collatzWithMutablesCached start =
let mutable count = 1L
let mutable current = start

while current > 1L do
match cache.TryGetValue current with
| true,cachedCount ->
count <- count + cachedCount
current <- 1L
| _ ->
current <- next current
count <- count + 1L

count

#time
seq { 1L..999999L} |> Seq.maxBy collatzWithMutablesCached
#time
``````

That brings our time down to 0.7 seconds. I’m totally happy with that. That’s an 80% reduction.

I went back and added some code to count the number of cache hits and cache misses. There are 999,997 cache hits vs. 5,226,259 misses. So the cache hits only 16% of the time. However, those hits eliminate a whopping 150,522,402 calls to `next` which is why this is so much faster.

#### Attempt #4

I’m still feeling experimental. There’s one more approach I’d like to try.

I have 8 cores. Let’s use all of them!

``````let collatzAsync startNum endNum = async {
return
seq { startNum..endNum }
|> Seq.map (fun i -> i,collatzWithMutables i)
|> Seq.maxBy snd
}

let ranges =
[
1L,125000L
125001L,250000L
250001L,375000L
375001L,500000L
500001L,625000L
625001L,750000L
750001L,875000L
875001L,999999L
]

#time
ranges
|> Seq.map (fun (s,e) -> collatzAsync s e)
|> Async.Parallel
|> Async.RunSynchronously
|> Seq.maxBy snd
|> fst
#time
``````

I broke the problem up into 8 chunks of 125000 each. `collatzAsync` is an asynchronous function that works out the answer to the chunk using the `collatzWithMutables` function we used before.

The main body executes all those chunks in parallel and then returns the biggest answer found.

This runs in 0.9 seconds on my machine. Not as fast as the cached solution, but quite fun to write.

Mood

### The Problem

Work out the first 10 digits of the sum of a lot of really large numbers.

I won’t duplicate the list of numbers here since they exist in code form in the solution

### The Solution

The problem requires us to sum 100 50-digit integers.

This might cause problems in other languages, but thanks to the .NET Framework’s big integer type, the problem is almost trivially easy. We simply parse the input into `bigint` and then take the sum. We could even skip the parsing step by specifying the numbers as `bigint` literals (e.g. `1234I`), but where’s the sport in that?

``````open System.Numerics

let input = [
"37107287533902102798797998220837590246510135740250"
"46376937677490009712648124896970078050417018260538"
"74324986199524741059474233309513058123726617309629"
"91942213363574161572522430563301811072406154908250"
"23067588207539346171171980310421047513778063246676"
"89261670696623633820136378418383684178734361726757"
"28112879812849979408065481931592621691275889832738"
"44274228917432520321923589422876796487670272189318"
"47451445736001306439091167216856844588711603153276"
"70386486105843025439939619828917593665686757934951"
"62176457141856560629502157223196586755079324193331"
"64906352462741904929101432445813822663347944758178"
"92575867718337217661963751590579239728245598838407"
"58203565325359399008402633568948830189458628227828"
"80181199384826282014278194139940567587151170094390"
"35398664372827112653829987240784473053190104293586"
"86515506006295864861532075273371959191420517255829"
"71693888707715466499115593487603532921714970056938"
"54370070576826684624621495650076471787294438377604"
"53282654108756828443191190634694037855217779295145"
"36123272525000296071075082563815656710885258350721"
"45876576172410976447339110607218265236877223636045"
"17423706905851860660448207621209813287860733969412"
"81142660418086830619328460811191061556940512689692"
"51934325451728388641918047049293215058642563049483"
"62467221648435076201727918039944693004732956340691"
"15732444386908125794514089057706229429197107928209"
"55037687525678773091862540744969844508330393682126"
"18336384825330154686196124348767681297534375946515"
"80386287592878490201521685554828717201219257766954"
"78182833757993103614740356856449095527097864797581"
"16726320100436897842553539920931837441497806860984"
"48403098129077791799088218795327364475675590848030"
"87086987551392711854517078544161852424320693150332"
"59959406895756536782107074926966537676326235447210"
"69793950679652694742597709739166693763042633987085"
"41052684708299085211399427365734116182760315001271"
"65378607361501080857009149939512557028198746004375"
"35829035317434717326932123578154982629742552737307"
"94953759765105305946966067683156574377167401875275"
"88902802571733229619176668713819931811048770190271"
"25267680276078003013678680992525463401061632866526"
"36270218540497705585629946580636237993140746255962"
"24074486908231174977792365466257246923322810917141"
"91430288197103288597806669760892938638285025333403"
"34413065578016127815921815005561868836468420090470"
"23053081172816430487623791969842487255036638784583"
"11487696932154902810424020138335124462181441773470"
"63783299490636259666498587618221225225512486764533"
"67720186971698544312419572409913959008952310058822"
"95548255300263520781532296796249481641953868218774"
"76085327132285723110424803456124867697064507995236"
"37774242535411291684276865538926205024910326572967"
"23701913275725675285653248258265463092207058596522"
"29798860272258331913126375147341994889534765745501"
"18495701454879288984856827726077713721403798879715"
"38298203783031473527721580348144513491373226651381"
"34829543829199918180278916522431027392251122869539"
"40957953066405232632538044100059654939159879593635"
"29746152185502371307642255121183693803580388584903"
"41698116222072977186158236678424689157993532961922"
"62467957194401269043877107275048102390895523597457"
"23189706772547915061505504953922979530901129967519"
"86188088225875314529584099251203829009407770775672"
"11306739708304724483816533873502340845647058077308"
"82959174767140363198008187129011875491310547126581"
"97623331044818386269515456334926366572897563400500"
"42846280183517070527831839425882145521227251250327"
"55121603546981200581762165212827652751691296897789"
"32238195734329339946437501907836945765883352399886"
"75506164965184775180738168837861091527357929701337"
"62177842752192623401942399639168044983993173312731"
"32924185707147349566916674687634660915035914677504"
"99518671430235219628894890102423325116913619626622"
"73267460800591547471830798392868535206946944540724"
"76841822524674417161514036427982273348055556214818"
"97142617910342598647204516893989422179826088076852"
"87783646182799346313767754307809363333018982642090"
"10848802521674670883215120185883543223812876952786"
"71329612474782464538636993009049310363619763878039"
"62184073572399794223406235393808339651327408011116"
"66627891981488087797941876876144230030984490851411"
"60661826293682836764744779239180335110989069790714"
"85786944089552990653640447425576083659976645795096"
"66024396409905389607120198219976047599490197230297"
"64913982680032973156037120041377903785566085089252"
"16730939319872750275468906903707539413042652315011"
"94809377245048795150954100921645863754710598436791"
"78639167021187492431995700641917969777599028300699"
"15368713711936614952811305876380278410754449733078"
"40789923115535562561142322423255033685442488917353"
"44889911501440648020369068063960672322193204149535"
"41503128880339536053299340368006977710650566631954"
"81234880673210146739058568557934581403627822703280"
"82616570773948327592232845941706525094512325230608"
"22918802058777319719839450180888072429661980811197"
"77158542502016545090413245809786882778948721859617"
"72107838435069186155435662884062257473692284509516"
"20849603980134001723930671666823555245252804609722"
"53503534226472524250874054075591789781264330331690"
]

let sum =
input
|> Seq.map BigInteger.Parse
|> Seq.sum

sum.ToString().Substring(0, 10)

``````

Mood

### The Problem

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

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

Let us list the factors of the first seven triangle numbers:

``````     1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
``````

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

### The Solution

This one is a little tricky. Note that the factor examples the problem definition specifies include composite numbers (i.e., multiples of more than one prime). In most of the Euler problems I’ve worked on, factors are limited to primes.

Thus, to find the number of divisors for `n`, we need to check all numbers up to the square root of `n`.

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

let numDivisors n =

let factorsOver3() =
let sr = intsqrt n
seq { 3..sr }
|> Seq.filter (fun e -> n % e = 0)
|> Seq.length

match n with
| 1 -> 1
| 2 -> 2
| x when (x &&& 1) = 0 -> (2 + factorsOver3()) * 2
| _ -> (1 + factorsOver3()) * 2
``````
• If `n` is 1, then there’s only 1 divisors
• If `n` is 2, there’s 2 divisors (1 and 2)
• If `n` is even, the number of divisors is 2 (`2` and `n` itself) plus the number of factors it has > 3, times 2. Why do we multiply by two? Because if we only test up to the square root of `n`, then if we find a factor then `n/x` is also a factor.
• If `n` is odd, the number of divisors is 1 (the number `1` is a divisor) plus the number of factors over 3. We also multiply by two for the same reason as in the even case.

With that in hand, we can look for the solution:

``````let rec getOver500 t n =
if numDivisors t >= 500 then
t
else
getOver500 (t + n + 1) (n + 1)

getOver500 1 1
``````

The `getOver500` function takes two parameters, `t` which is the accumulator for the triangle number value, and `n` which is the nth natural number. If it finds a `t` with >= 500 divisors, it returns `t`, otherwise it computes the next triangle number (`t + n + 1`) and the next natural number (`n + 1`) and recurses.

Full disclosure: While I was writing this blog post, I discovered a very subtle bug. The code finds the correct answer to this problem, but it is flawed. Consider the case of 36. 36 has 9 divisors (1, 2, 3, 4, 6, 9, 12, 18, and 36) but `numDivisors` actually returns 10 for that. The `numDivisors` function, as written, will always return an even number, even though that is (in hindsight) clearly wrong. I’m leaving it here as a reminder that just because code works today, that doesn’t mean you won’t find a bug tomorrow when the inputs are different.

Looking back, I see that I was trying to be too clever by considering different cases for odd and even. There is a much simpler way that executes in almost exactly the same amount of time. Just replace the `numDivisors` function with this one:

``````let numDivisors n =
let sr = intsqrt n
seq { 1..sr }
|> Seq.filter (fun e -> n % e = 0)
|> Seq.collect (fun e -> [e; n/e])
|> Seq.distinct
|> Seq.length
``````

Mood

### The Problem

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

``````    08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 [26] 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 [63] 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 [78] 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 [14] 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
``````

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

### The Solution

First, we need that input grid in a format we can use.

``````open System

let runLength = 4
let gridSize = 20

let input = [|
"08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08"
"49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00"
"81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65"
"52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91"
"22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80"
"24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50"
"32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70"
"67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21"
"24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72"
"21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95"
"78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92"
"16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57"
"86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58"
"19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40"
"04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66"
"88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69"
"04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36"
"20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16"
"20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54"
"01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48"
|]

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

let ints =
input
|> Array.map (fun s ->
s
|> splitBy ' '
|> Array.map int32
)

let product arr =
arr |> Array.reduce (fun acc elem -> acc*elem)

``````

We define a couple of values that tell us about the problem we’re solving. We’re looking for groups of `runLength` digits. `gridSize` tells us the grid is 20x20. `input` contains the grid itself, copy/pasted from the problem definition.

The `ints` function turns our input into an array of arrays, which allows us to reference rows and columns like so: `ints.[row].[col]`

Finally, similar to what we used in Problem 8, the `product` function uses `Array.reduce` to return the product of all the elements of an array.

Next, we need to figure out how to break this grid up into chunks of 4 numbers each. Let’s start with the easiest case: breaking each row up into groups of 4.

``````let byRows() =
ints
|> Seq.collect (fun r -> r |> Array.windowed runLength)
``````

The function above uses `Array.windowed` to break up each row (which is an array itself) into groups of 4. For the first row of the grid, this function returns a sequence that looks like this:

``````[|8; 2; 22; 97|]
[|2; 22; 97; 38|]
[|22; 97; 38; 15|]
[|97; 38; 15; 0|]
[|38; 15; 0; 40|]
[|15; 0; 40; 0|]
[|0; 40; 0; 75|]
[|40; 0; 75; 4|]
[|0; 75; 4; 5|]
[|75; 4; 5; 7|]
[|4; 5; 7; 78|]
[|5; 7; 78; 52|]
[|7; 78; 52; 12|]
[|78; 52; 12; 50|]
[|52; 12; 50; 77|]
[|12; 50; 77; 91|]
[|50; 77; 91; 8|]
``````

That’s the magic of the `windowed` function.

Next, we’ll tackle the problem of breaking up each column into groups of 4.

``````let byCols() =
let getCol c =
seq {
for r in 0..gridSize-1 do
yield ints.[r].[c]
}
|> Array.ofSeq
|> Array.windowed runLength

seq {
for c in 0..gridSize-1 do
yield! getCol c
}
``````

The function above first turns the grid into arrays of columns, then uses `Array.windowed` to, once again, created groups of 4 numbers.

Now, onto diagonals, which are the most complicated case.

``````let byDiagonals() =
let getDownhill r c =
seq {
for i in 0..runLength - 1 do
yield ints.[r+i].[c+i]
} |> Array.ofSeq

let getUphill r c =
seq {
for i in 0..runLength - 1 do
yield ints.[r+i].[c-i]
} |> Array.ofSeq

seq {
for r in 0..gridSize - 1 do
for c in 0..gridSize - 1 do
if (r + runLength) < gridSize && (c + runLength) < gridSize then
yield getDownhill r c
if (r + runLength) < gridSize && (c - runLength) >= 0 then
yield getUphill r c
}
``````

This function contains two functions inside it, `getDownhill` and `getUphill`. These return an array of 4 numbers either moving downhill (where both row and column increase) or uphill (where row increases and column decreases).

The main function body simply generates each possible position in the grid and, if possible, yields a downhill and an uphill sequence from that position.

With all that in place, we can finally get our answer:

``````[ byRows(); byCols(); byDiagonals() ]
|> Seq.concat
|> Seq.map product
|> Seq.max
``````

The code above:

• Uses our three `byXxx` functions to generate all possible sequences of 4 numbers.
• Concatenates that into a single sequence consisting of 4-number arrays.
• Uses `Seq.map` to compute the product of each array
• Uses `Seq.max` to return the answer.

Mood

### The Problem

Sum the primes below 2 million.

### The Solution

We already wrote a function to generate primes below a certain number for Problem 3.

We can just use `Seq.sum` to sum those and we’re done.

``````getPrimesBelow64 2000000
|> Seq.sum
``````

Mood

This took me a lot longer to solve than it should have. In fact, I got the solution right, then started over from scratch. The end result was much better.

### The Problem

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a2 + b2 = c2

For example, 32 + 42 = 9 + 16 = 25 = 52.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

### The Solution

First, let’s define some functions that let us know when we have the right answer:

``````let max = 1000

let isTriplet (a,b,c) = a*a + b*b = c*c

let isSpecial (a,b,c) = a+b+c=max
``````

`isTriplet` returns `true` if `a,b,c` is a Pythagorean triplet. `isSpecial` returns true if the sum of `a,b,c` is 1000. If both return true for an `a,b,c`, that’s our answer.

Since we like expressing our problems as a pipeline, here’s the plan of attack.

• Use `Seq.unfold` to generate a sequence of possible triplets
• Use `Seq.filter` to filter out triplets that don’t add up to 1000
• Use `Seq.filter` to filter out non-Pythagorean triplets
• The first one of those is our answer.

The first thing we need is a sequence generator. This is made up of two functions, `incState` and `generator`. `incState` finds the next triplet.

``````let incState = function
| a,b,c when b<>(max-1) && c=max -> a,b+1,b+2
| a,b,c when b=(max-1) && c=max -> a+1,a+2,a+3
| a,b,c -> a,b,c+1
``````

I could have made this slightly simpler, but since the problem definition specifies that a < b < c, I wanted to make sure that the result of this function obeyed that rule. Doing so decreases the possible sequences from 1 billion to about 160 million, which is quite the improvement.

``````let generator ((a,_,_) as state) =
if a>=(max-1) then
None
else
Some(state, (incState state))
``````

The above generates a sequence of triplets by incrementing the state until `a` hits 999.

Now that we can tell if we have the answer and we have a sequence of possible answers, finding the answer is easy:

``````Seq.unfold generator (1, 2, 997)
|> Seq.filter isSpecial
|> Seq.filter isTriplet
``````

Mood

### The Problem

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

### F# Solution

I had a lot of fun solving this one. The solution I came up with is a great example of using the pipeline operator `|>` to break a solution into a series of steps that eventually yield the answer. First, let’s define the input:

``````let inputs = [|
"73167176531330624919225119674426574742355349194934"
"96983520312774506326239578318016984801869478851843"
"85861560789112949495459501737958331952853208805511"
"12540698747158523863050715693290963295227443043557"
"66896648950445244523161731856403098711121722383113"
"62229893423380308135336276614282806444486645238749"
"30358907296290491560440772390713810515859307960866"
"70172427121883998797908792274921901699720888093776"
"65727333001053367881220235421809751254540594752243"
"52584907711670556013604839586446706324415722155397"
"53697817977846174064955149290862569321978468622482"
"83972241375657056057490261407972968652414535100474"
"82166370484403199890008895243450658541227588666881"
"16427171479924442928230863465674813919123162824586"
"17866458359124566529476545682848912883142607690042"
"24219022671055626321111109370544217506941658960408"
"07198403850962455444362981230987879927244284909188"
"84580156166097919133875499200524063689912560717606"
"05886116467109405077541002256983155200055935729725"
"71636269561882670428252483600823257530420752963450"
|]
``````

I copied and pasted most of that right out of the problem definition, adding `"` at each end, which is super easy to do if you use column selection in Visual Studio.

Next, we’re going to need a function that computes the product of the elements in a sequence. So, for example, `product [1I..4I]` returns 24.

``````let product nums =
nums
|> Seq.reduce (fun acc elem -> acc*elem)
``````

The `product` function above uses `Seq.reduce` to multiple each element in the sequence by the previous one and then return the result.

Finally, we build our pipeline to get the result:

``````inputs
|> Seq.concat
|> Seq.map (fun c -> bigint(int(string c)))
|> Seq.windowed 13
|> Seq.map (fun s -> s,product s)
|> Seq.maxBy snd
``````

The above:

• Concatenates all the inputs into a long sequence of characters
• Converts each character to a `bigint`
• Breaks it up into sliding windows of 13 numbers each
• Converts each sequence of 13 numbers to its product
• Finds the maximum product (the answer)

Mood

### The Problem

Find the 10001st prime number.

### F# Solution

We already wrote some functions to generate sequences of prime numbers for Problem 3. We’re going to be using those functions over and over again so I’ll probably just wind up moving them to a module. But today is not that day.

That code generated a sequence of primes below a certain number. I’m going to modify that code to generate a sequence of `n` 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 x =
match x with
| x when isPrime x -> x
| x -> nextPrime (x + 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)
``````

`getSomePrimes` uses `Seq.unfold` with a generator function that generates the next prime after the current one. It stops when `num` elements have been generated.

With this code in place, we can simply generate a sequence containing 10001 primes and use `Seq.last` to give us the answer:

``````getSomePrimes 10001
|> Seq.last
``````

Mood

### The Problem

The sum of the squares of the first ten natural numbers is,

12 + 22 + … + 102 = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + … + 10)2 = 552 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

### F# Solution

I used to hate writing sequence-based algorithms in C#. Everything always just seemed so clunky. Then LINQ came along and make it much nicer.

Since sequences are first-class citizens in F#, it makes working with them very easy.

To solve this problem, we first need a function to produce the sum of the squares of the elements in a sequence.

``````let sumOfSquares nums =
nums
|> Seq.map (fun n -> n * n)
|> Seq.sum
``````

We use `Seq.map` to transform each element into its square, and then `Seq.sum` to get the sum.

Contrast that with this:

``````public static int SumOfSquares(IEnumerable<int> nums)
{
var sum = 0;
foreach (var n in nums)
{
sum += (n*n);
}
return sum;
}
``````

or this:

``````public static int SumOfSquares(IEnumerable<int> nums)
{
return nums.Sum(n => (n*n));
}
``````

Both C# functions get the job done, but the F# code reads much better to me.

Next, we need a function to produce the square of the sum of a sequence of numbers.

``````let squareOfSum nums =
nums
|> Seq.sum
|> fun n -> n * n
``````

And finally, put those functions together to get the answer:

``````(seq { 1..100 } |> squareOfSum) - (seq { 1..100 } |> sumOfSquares)
``````

Mood

### The Problem

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

### F# Solution

It is very easy to brute force this solution. However, Project Euler has this rule stated clearly on their main page:

I’ve written my program but should it take days to get to the answer?

Absolutely not! Each problem has been designed according to a “one-minute rule”, which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Given that, my initial reaction is that testing every single positive integer for all factors <= 20 is might not make it under the one-minute rule.

I’m a big believer in the principle of optimizing code later if you have to. The primary goal of code should be clarity. I try to write the clearest code I can first and then optimize it later if I have to. This is in stark contrast to the way I used to write code back in the 80s and 90s, when processor power was expensive and scarce, and programs were smaller in scope. Now, processor power is cheap and plentiful and programs are increasingly complex. In the context of large, complicated programs, it makes sense to make code clarity the primary goal. If you follow the Single Responsibility Principle, refactoring things to make them faster is very easy.

With that in mind, here is the unoptimized algorithm:

``````let factors = [| 1..20 |]

let isEvenlyDivisible i =
factors
|> Seq.forall (fun d -> i % d = 0)

let rec smallestEvenlyDivisible = function
| x when isEvenlyDivisible x -> x
| x -> smallestEvenlyDivisible (x+1)

#time
smallestEvenlyDivisible 20
#time
``````

`isEvenlyDivisble` takes an array of factors and tests the input `i` against all of them.

`smallestEvenlyDivisble` keeps incrementing `x` until it finds an `x` for which `isEvenlyDivisble` returns `true`.

Note that I’ve included `#time` directives around the part of the code that does the work. If you run this code in the F# REPL, it will spit out interesting timing data. On one of the cores in my 3.9Ghz processor, the code takes 24 seconds to run.

``````Real: 00:00:24.333, CPU: 00:00:24.328, GC gen0: 1777, gen1: 4, gen2: 1
``````

24 seconds gets us under the 1-minute rule, so my initial reaction was wrong. But the decision to go forward with the clearest code possible was right.

But I’m not really happy about the results. I think we can do much better and still meet the goal of clarity.

The array of factors seems the best candidate for optimization. It is simply not necessary to check every single one of them. At the very least, we can eliminate 1.

We can also eliminate 2. We know the solution must be even because the answer must be evenly divisible by 2. Thus, we can change the algorithm to only check even numbers, which eliminates half the work our program must do.

``````let factors = [| 3..20 |]

let isEvenlyDivisible i =
factors
|> Seq.forall (fun d -> i % d = 0)

let rec smallestEvenlyDivisible = function
| x when isEvenlyDivisible x -> x
| x -> smallestEvenlyDivisible (x+2)

#time
smallestEvenlyDivisible 20
#time
``````

Now we’re down to 10 seconds.

``````Real: 00:00:10.410, CPU: 00:00:10.406, GC gen0: 889, gen1: 2, gen2: 1
``````

We can also eliminate 20 as a factor and only check numbers that are multiples of 20.

``````let factors = [| 3..19 |]

let isEvenlyDivisible i =
factors
|> Seq.forall (fun d -> i % d = 0)

let rec smallestEvenlyDivisible = function
| x when isEvenlyDivisible x -> x
| x -> smallestEvenlyDivisible (x+20)

#time
smallestEvenlyDivisible 20
#time
``````

Now I’m down to 1.2 seconds. I’d feel reasonably good about stopping there, except that there are more factors we can eliminate from the array at only a tiny cost to clarity.

• We can eliminate 3 and 5 and leave 15, because 3 and 5 are factors of 15.
• We can eliminate 4 and 8 and leave 16.
• We can eliminate 6 and 9 and leave 18.
• We can eliminate 7 and leave 14.
• We can eliminate 10 because we’re only testing multiples of 20, which are also divisible by 10.

Thus, we only have to test factors `[| 11..19 |]`, which brings the total execution time own to 0.953 seconds on my machine.

Now I feel like I’m done.

Mood

I love palindromes.

My favorite:

A man, a plan, a canal: Panama

Today’s problem deals with “palindromic numbers” which, I admit, is a concept I never considered before I tried to solve this problem.

### Problem 4

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

### F# Solution

First, we need to find out if a number is, in fact, “palindromic”.

``````let isPalindrome i =
let chars = string(i)

let rec palindrome l r =
if l > r then
true
else
chars.[l] = chars.[r] && palindrome (l+1) (r-1)

palindrome 0 (chars.Length-1)
``````

The function above converts `i` to a string and then starts looking at the characters at either end. If they’re the same, it recurses, moving inward, and looks at the next pair of characters. Eventually the counter parameters, `l` and `r` cross, at which point we know we have a palindrome.

Next, we need to check the products of all 3-digit numbers to see which are palindromes.

``````let generator (n1,n2) =
if (n1 > 999) then None
else Some(n1*n2,if (n2 = 999) then n1+1,100 else n1,n2+1)
``````

We can pass the above `generator` function to `Seq.unfold` to generate a sequence of products of 3-digit numbers. The accumulator value is a tuple containing the two 3-digit numbers to multiply. Each iteration generates the product and increments the accumulator.

Finally, we can put it all together to get the answer:

``````Seq.unfold generator (100,100)
|> Seq.filter isPalindrome
|> Seq.max
``````

Mood

Today’s solution introduces a function we’re going to be using over and over again. Namely, generating a sequence of prime numbers. There are faster, more complicated ways to do this, but they’re not needed right now so I’m going to keep things simple.

### Problem 3

Find the largest prime factor of 600851475143.

### F# Solution

First things first: 600851475143 is outside the space of a 32-bit integer, so we need to make sure we use 64-bit numbers for everything.

My general plan of attack here is to generate prime numbers and test them as a factor of 600851475143. We don’t have to test all the factors. We can stop at the square root, because a number `n` can’t have a factor > `sqrt(n)`.

First, how do you tell if a 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)
``````

The code above tests to see if the number is 2. If it is, it’s prime. Otherwise, if it’s even, it’s not prime. Finally, it checks all odd numbers up to the square root of `i` to see if they divide evenly into `i`. If any of them do, `i` is not prime.

Now that we can tell if a number is prime, we can generate the next prime >= `i`:

``````let rec nextPrime64 (i : int64) =
match i with
| i when isPrime64 i -> i
| i -> nextPrime64 (i + 1L)
``````

The function above is a tail recursive function. Idiomatic F# uses functions like this a lot. Where loops are your friend in other languages, recursive functions are your friend in F#.

With those tools in hand, we can use `Seq.unfold` to generate a sequence of primes. This function generates all primes below the specified number.

``````let getPrimesBelow64 (max : int64) =
let primeGenerator candidate =
if candidate > max then
None
elif candidate = 2L then
Some(2L,3L)
else
let next = nextPrime64 candidate
if next >= max then
None
else
Some(next,next+2L)

Seq.unfold primeGenerator 2L
``````

And finally, with all that in place, solving the problem is easy.

``````[<Literal>]
let target = 600851475143L

getPrimesBelow64 (int64sqrt target)
|> Seq.filter (fun x -> target % x = 0L)
|> Seq.max
``````

We generate all primes below `sqrt(600851475143)` and filter out ones that are not a factor of `target`. Then we use `Seq.max` to get the answer.

Mood

Yesterday’s post was just an easy warm-up. We’re just getting started!

### Problem 2

Sum all even numbers in the Fibonacci sequence (1, 1, 2, 3, 5, 8, 13…) below 4 million.

### C# Solution

The C# solution to this is fairly straightforward.

``````var elem1 = 1;
var elem2 = 1;
var sum = 0;
while (elem2 < 4000000)
{
var newElem = elem1 + elem2;
if (newElem%2 == 0) sum += newElem;
elem1 = elem2;
elem2 = newElem;
}
Console.WriteLine(sum);
``````

### F# Solution

This F# uses a sequence generator to create an infinite sequence of Fibonacci numbers and uses the pipe operator to apply the different constraints of the problem:

• Numbers below 4,000,000
• Only even numbers

Incidentally, I’m using an “old school” trick here to determine if the number is even. If you do a bitwise `and` operation on a number with 1, the result is 0 if the number is even and the result is 1 if it’s odd. The optimizing compiler probably already does this when you write `i % 2 = 0` but old habits die hard.

``````let fibSeq =
let rec fibSeq n1 n2 =
seq { let n0 = n1 + n2
yield n0
yield! fibSeq n0 n1 }
seq { yield 1 ; yield 1 ; yield! (fibSeq 1 1) }

let isEven i = i &&& 1 = 0

fibSeq
|> Seq.filter (fun x -> x < 4000000)
|> Seq.filter isEven
|> Seq.sum
``````

But there’s a bug here. Can you spot it?

The first call to `Seq.filter` is wrong. This tells F# to go through every item in the sequence and apply the filter function. Since our sequence is infinite, we’ll eventually get an arithmetic overflow.

Since we know that the sequence is in numeric order, we can use `Seq.takeWhile` instead of `Seq.filter` for the first constraint.

``````fibSeq
|> Seq.takeWhile (fun x -> x < 4000000)
|> Seq.filter isEven
|> Seq.sum
``````

Mood

So I’ve been learning F#.

Learning a new language has never been a challenge for me. But writing idiomatic F# (those F# guys are big on idiomatic) requires a reorientation of my thinking.

With that in mind, I decided a good way to improve my skills was to solve the first 60 Project Euler problems with F#, trying to be as idiomatic as possible, while avoiding being idiotic. (See what I did there? It’s a prefix joke.)

So, without further ado, here is:

### Problem 1

Sum all positive integers less than 1000 that are multiples of 3 or 5.

### C# Solution

If I was writing this in C#, I would be using something like a for loop with a mutable iterator to do this.

``````var sum = 0;
for (var i = 1; i < 1000; ++i)
{
if (i%3 == 0 || i%5 == 0)
{
sum += i;
}
}
Console.WriteLine(sum);
``````

### F# Solution

``````seq { 1..999 }
|> Seq.filter (fun n -> n % 3 = 0 || n % 5 = 0)
|> Seq.sum
``````

Right away, we’re making use of the most common F# features:

• Sequences (`seq { 1..999}`)
• Expressing the problem as a pipeline

All the thinking happens on the second line, which filters out the values we don’t want. `Seq.sum` gives us the answer by processing the sequence created by the previous elements in the pipeline.

### But, but…

Yes, I know, you can do exactly the same thing in C# with LINQ. This is not a problem where F# particularly shines. But I’m working through all the problems anyway.

I could do it in C# and LINQ like this. It looks almost exactly like the F# solution.

``````var sum = Enumerable.Range(1, 999).Where(x => x%3 == 0 || x%5 == 0).Sum();
Console.WriteLine(sum);
``````