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