While I was on hiatus the Stack Overflow site launched. I’ve found it incredibly useful and I keep going back there again and again. One thing I love about their site is the simplified syntax they use: Markdown. I liked it so much that I wanted to use it under the covers for my blog here. I found the Markdown for WordPress and bbPress and WP MarkItUp! plugins and installed them. Markdown for WordPress allows writing posts in Markdown and MarkItUp replaces the editor toolbar with buttons related to Markdown instead of HTML.

Markdown for WordPress worked great. I had no problem editing my posts in Markdown. However, I had a problem configuring MarkItUp. Every time I tried to access the settings page for MarkItUp I received a blang page with the following error: “You do not have sufficient permissions to access this page.” The plugin hadn’t been updated in over a year, so I figured that it was a small incompatibility with WordPress 3. I delved into the markitup_class.php file included with the plugin and found this line:

```
add_options_page('WP MarkItUp!', 'WP MarkItUp!', 8, 'WP MarkItUp!',
array(&$this, 'option_page'));
```

The WordPress [Adding Administration Menu page] describes the 3rd argument as “The capability required for this menu to be displayed to the user.” and further details that, “user levels are deprecated and should not be used here!” Well…that ‘`8`

‘ certianly looks like a user level to me! I replaced the ‘`8`

‘ with the `'manage_options'`

capability and deactivated then reactivated the plugin. After that…I was still unable to access the plugin settings page.

I looked in the address bar and noticed that the URL ended in “`MarkItUp!`

“. Special characters in URLs can be fishy, so I looked at the 4th argument, the `menu_slug`

, and changed it from `'WP MarkItUp!'`

to `'markitup'`

. After going through the deactivation/reactivation procedure one more time I was finally able to access the plugin settings page. The final code looks like this:

```
add_options_page('WP MarkItUp!', 'WP MarkItUp!', 'manage_options',
'markitup', array(&$this, 'option_page'));
```

]]>The Fibonacci sequence is defined by the recurrence relation:

F

_{n}= F_{n−1}+ F_{n−2}, where F_{1}= 1 and F_{2}= 1.Hence the first 12 terms will be:

F

_{1}= 1

F_{2}= 1

F_{3}= 2

F_{4}= 3

F_{5}= 5

F_{6}= 8

F_{7}= 13

F_{8}= 21

F_{9}= 34

F_{10}= 55

F_{11}= 89

F_{12}= 144The 12th term, F

_{12}, is the first term to contain three digits.What is the first term in the Fibonacci sequence to contain 1000 digits?

Using a version of the Fibonacci sequence generator I coded up for problem #2 modified for Big Integers:

```
let fibonacci = Seq.unfold (fun (current, next) -> Some (current, (next, current + next))) (1I, 1I)
```

and the digits-to-sequence function from my solution to problem #20

```
let rec digits x =
let getNextDigit num =
if num >= 0I then None else
(num, 10I) |> BigInt.DivRem |> swap |> Some
Seq.unfold getNextDigit x
```

The solution is as simple as counting the digits in each Fibonacci number, and returning the index for the first one with 1000 digits:

```
let findFirstXDigitNumber numDigitsToFind = Seq.findIndex (numDigits >> (=) numDigitsToFind)
let answer numDigitsToFind = fibonacci |> findFirstXDigitNumber numDigitsToFind |> (+) 1
```

]]>n! means n × (n − 1) × … × 3 × 2 × 1

Find the sum of the digits in the number 100!

With F#’s BigInt support this was easy, straight-forward, and fast:

```
let swap (a, b) = (b, a)
``````
let rec digits x =
let getNextDigit num =
if num <= 0I then None else
(num, 10I) |> BigInt.DivRem |> swap |> Some
Seq.unfold getNextDigit x
let answer = BigInt.Factorial >> digits >> Seq.sum
```

]]>A number chain is created by continuously adding the square of the digits in a number to form a new number until it has been seen before.

For example,

44 → 32 → 13 → 10 → 1 → 1 85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89

Therefore any chain that arrives at 1 or 89 will become stuck in an endless loop. What is most amazing is that EVERY starting number will eventually arrive at 1 or 89.

How many starting numbers below ten million will arrive at 89?

First define some constants we’ll use in the various versions of the programs:

```
let NumDigits = 7
let limit numDigits = int(10.0**(float)numDigits) - 1 // limit 7 = 9999999
```

My first attempt utilizes this memoize function from a previous post.

```
let memoize (func:'a->'b) =
let cache = Dictionary<_, _>()
fun n ->
let (found, result) = cache.TryGetValue(n)
if found then
result
else
let result = func n
cache.[n] <- result
result
```

My first attempt converted each number into a string, sliced that string into characters, and converted each individual character to a single-digit number and summed the squares of the digits to generate the next number in the sequence. Using that generator, it then determined whether each starting number terminated at 89 using a memoized function.

`let digitize : string -> seq` = fun str -> seq {
for i = 0 to str.Length-1 do
yield int(str.[i]) - int('0')}
let generateNext1 =
let toString obj = obj.ToString()
let square x = x * x
toString >> digitize >> Seq.map square >> Seq.sum |> memoize

let rec terminatesAt1 : (int -> int) -> int -> int =
let f generateNext start =
match generateNext start with
| 1 -> 1
| 89 -> 89
| x -> terminatesAt1 generateNext x
memoize f

let numTerminatedAt1 terminatesAt terminal numDigits=
{1..limit numDigits}
|> Seq.map (terminatesAt >> (=) terminal)
|> Seq.countBy id
|> Seq.find (fun (bool, count) -> bool)
|> snd

let answer1 = lazy (numTerminatedAt1 (terminatesAt1 generateNext1) 89 NumDigits)

Even being memoized, this performed pretty badly, taking 140 seconds to produce the answer. Within the `generateNext1`

function, every number gets converted into a string which produces a lot of garbage. There is a way to calculate the digits of a number without converting it into a string and slicing the sub-digits out of it:

```
let generateNext2 =
let square x = x * x
let rec digits x = seq {
let rem = x % 10
yield rem
let dividend = x / 10
if dividend > 0 then yield! digits dividend
}
digits >> Seq.map square >> Seq.sum |> memoize
```let answer2 = lazy (numTerminatedAt1 (terminatesAt1 generateNext2) 89 NumDigits)

Which completes in 65 seconds. However, 65 seconds is still very slow. We can further optimize that function by not generating a sequence for each and every number:

```
let generateNext3 x =
let mutable sum = 0
let mutable dividend = x
while dividend > 0 do
let rem = dividend % 10
sum <- sum + rem * rem
dividend <- dividend / 10
sum
```let answer3 = lazy (numTerminatedAt1 (terminatesAt1 generateNext3) 89 NumDigits)

`generateNext3`

performs much better coming in at 44 seconds.

Next we can focus on enumerating all 10 million starting numbers. Instead of memoizing, what about storing the results in an array of 10 million elements, and prepopulating element 1 and 89?

```
let numTerminatedAt2 terminal numDigits=
let array : bool option array = Array.create ((limit numDigits)+1) None
match terminal with
| 1 -> array.[1] <- Some true; array.[89] <- Some false
| 89 -> array.[1] <- Some false; array.[89] <- Some true
| _ -> failwith "1 and 89 are the only valid terminals."
let rec terminatesAt start =
match array.[start] with
| Some bool -> bool
| None ->
let result = generateNext3 start |> terminatesAt
array.[start] <- Some result
result
for i = 1 to limit numDigits do terminatesAt i |> ignore
let mapBoolOptionToSum x =
match x with
| None -> 0
| Some false -> 0
| Some true -> 1
Array.sumBy mapBoolOptionToSum array
```let answer4 = lazy (numTerminatedAt2 89 NumDigits)

That got us to 5.5 seconds. What if we reduced the garbage generated by replacing the Option array with an array of ints?

```
let numTerminatedAt3 terminal numDigits=
let array : int array = Array.create ((limit numDigits)+1) 0
array.[1] <- 1
array.[89] <- 89
let rec terminatesAt start =
match array.[start] with
| 0 ->
let result = generateNext3 start |> terminatesAt
array.[start] <- result
result
| x -> x
for i = 1 to limit numDigits do terminatesAt i |> ignore
Array.sumBy (fun x -> if x = terminal then 1 else 0) array
```let answer5 = lazy (numTerminatedAt3 89 NumDigits)

This clocks in at just under 2 seconds! One potential optimization upon this that could be made is to recognize that the biggest result that can be obtained from summing the squares of the digits for all numbers less than 10 million is for 9999999. 9999999 results in 567 (7*9^{2}). So rather than storing all 10 million terminating numbers, we only need to store the first 567.

```
let generateTerminalArray numDigits =
let limit = numDigits
```*9*9
let array : int array = Array.create (limit+1) 0
array.[1] <- 1
array.[89] <- 89
let rec terminatesAt start =
match array.[start] with
| 0 ->
let result = generateNext3 start |> terminatesAt
array.[start] <- result
result
| x -> x
for i = 1 to limit do terminatesAt i |> ignore
array
let numTerminatedAt4 terminal numDigits =
let terminals = generateTerminalArray numDigits
let mutable sum = 0
for i = 0 to limit numDigits do
if terminals.[generateNext3 i] = terminal then sum <- sum + 1
sum

let answer6 = lazy (numTerminatedAt4 89 NumDigits)

This version took 1.5 seconds to compute. Another optimization is to recognize, that for a particular number, all permutations of that number generate the same chain. For example 12 and 21:

12 → 5 → 25 → 29 → 85 → 89 21 → 5 → 25 → 29 → 85 → 89

So if the chain for one particular permutation of a combination of numbers terminates in 89 then so will the chains for all the other permutations for that same combination of numbers. Thus, instead of brute-forcing the problem by calculating the result for each and every *permutation* of numbers, we can generate each *combination* and for every combination which terminates in 89, add to the sum the number of permutations for each combination.

`let combinations (numDigits : int) : seq` =
let rec enumerate (combo : int array) (start : int) (digit : int) = seq {
for i = start to 9 do
combo.[i] <- combo.[i] + 1
if digit = numDigits - 1
then yield combo
else yield! enumerate combo i (digit + 1)
combo.[i] <- combo.[i] - 1
}
enumerate (Array.create 10 0) 0 0

Then we need a way to generate a sequence of these arrays of digit counts - with each combination produced only once in the sequence.

To simplify the storage and calculation of the digits, each number is stored as an array of counts of each digit. I.e. The number 1223777 is stored as 0121000300 -> 0 zeros, 1 one, 2 twos, 1 three, etc. Furthermore, to reduce garbage and computation time, the combination sequence reuses the array it returns - modifying it slightly each time it is returned. `generateNext4`

is just a modified version of `generateNext3`

changed to operate on these arrays of digit counts.

```
let generateNext4 (combo : int array) =
let mutable sum = 0
for i = 0 to 9 do
let x = combo.[i]
sum <- sum + x*i*i
sum
```

The number of permutations for each combination can be found via the multinomial coefficient:

(n_{1}+n_{2}+n_{3}+...)! |

n _{1}!*n_{2}!*n_{3}!*... |

where n_{1} is the number of 1's, n_{2} is the number of 2's, n_{3} is the number of 3's, etc.

```
let factorials =
let factorial n = Seq.fold (*) 1 [1 .. n]
// store factorials in an array as a way of memoizing them
Array.init 12 factorial
```let multinomialCoefficient (x : int array) : int =
let numerator = Array.sum x |> Array.get factorials
let denominator =
let mutable result = 1
for i = 0 to 9 do
result <- result * (Array.get factorials x.[i])
result
numerator / denominator

Finally putting it all together:

```
let numTerminatedAt5 terminal numDigits =
let terminals = generateTerminalArray numDigits
combinations numDigits
|> Seq.filter (generateNext4 >> Array.get terminals >> (=) terminal)
|> Seq.sumBy multinomialCoefficient
```let answer7 = lazy (numTerminatedAt5 89 NumDigits)

This version clocks in at less than 50 milliseconds! But there's an even better algorithm, mentioned by ceebo on the Project Euler website. Instead of enumerating through all of the combinations, simply enumerate through the array of 567 terminals, and for each one which terminates in 89, count the number of numbers which generate that number. I.e., for each number from 1 to 567 which results in 89, how many numbers, after running through `generateNext`

result in that number?

let `count(digits, n)`

represent the count of numbers with `digit`

digits that result in `n`

when run through `generateNext`

.

```
count(digits, n) = count(digits-1, n-0^2) + count(digits-1, n-1^2) + count(digits-1, n-2^2) + ...
```

With the following base cases:
```
count(0, 0) = 1
count(0, n) = 0 if n > 0
count(digits, n) = 0 if n < 0
```

```
let singledigits = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]
```let rec count digits n =
match digits with
| 0 -> if n = 0 then 1 else 0
| _ ->
let summationTerm i =
let nextN = n - i*i
if nextN < 0 then 0 else count (digits-1) nextN
singledigits |> Array.sumBy summationTerm

However, due to the recursive nature of this function, it's much more efficient to memoize it. To avoid create lots of tuple garbage by storing the (digit, n) pairs in a dictionary, I instead memoized this function in a 2-dimensional array with this memoizing function:

```
let memoizeArray2D (x: int) (y : int) (f : 'a -> 'b -> 'c) : 'a -> 'b -> 'c =
let cache = Array2D.create x y None
fun a b ->
match cache.[a,b] with
| Some value -> value
| None ->
let value = f a b
cache.[a,b] <- Some value
value
```

And the `count`

function is modified to use it:

```
let singledigits = [|0; 1; 2; 3; 4; 5; 6; 7; 8; 9|]
```let rec count =
let compute digits n =
match digits with
| 0 -> if n = 0 then 1 else 0
| _ ->
let summationTerm i =
let nextN = n - i*i
if nextN < 0 then 0 else count (digits-1) nextN
singledigits |> Array.sumBy summationTerm
memoizeArray2D (NumDigits+1) (NumDigits*9*9+1) compute

And finally putting it all together:

`let numTerminatedAt6 terminal numDigits =`

generateTerminalArray numDigits
|> Array.mapi (fun i term -> if term = terminal then count numDigits i else 0)
|> Array.sum
let answer8 = lazy (numTerminatedAt6 89 NumDigits)

This clocks in under 10 ms...a 5x improvement over the previous solution. Furthermore, at higher digits, this final function scales better than the previous solution.

]]>2

^{15}= 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.What is the sum of the digits of the number 2

^{1000}?

```
open System
open Microsoft.FSharp.Math
```let digits =
let str = BigInt.Pow(2I,1000I).ToString()
seq {
for i = 0 to str.Length-1 do
yield int(str.[i]) - int('0')}

digits |> Seq.reduce (+) |> printfn "Answer = %d"

]]>Starting in the top left corner of a 2×2 grid, there are 6 routes (without backtracking) to the bottom right corner.

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

These grids can be represented as a set of nodes pointing from the upper left corner, always down and to the right. The answer is simply the number of unique traversals that can be made of that graph.

Representing the lower right corner as (0,0) and the upper left as (20,20) I’ll produce a memoized function to compute the results:

```
open System.Collections.Generic
```let memoize (func:'a->'b) =
let cache = Dictionary<_, _>()
fun n ->
let (found, result) = cache.TryGetValue(n)
if found then
result
else
let result = func n
cache.[n] <- result
result

let rec numRoutes =
let f (x,y) =
if x = 0 or y = 0
then 1L
else numRoutes (x-1,y) + numRoutes (x,y-1)
f |> memoize

let answer = lazy( numRoutes (20,20))

answer.Force() |> printfn "Answer = %d"

Pretty good, but if you look closely at the values this generates, if you’re familiar with mathematics you’ll quickly recognize Pascal’s triangle in there – the solution to this problem could easily be solved by one simple mathematical expression!

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

Here’s my first stab at a solution:

```
open Microsoft.FSharp.Math
```let isEven i = i % 2I = 0I

let rec sequence (n:bigint) =
let next n = if isEven n then n/2I else 3I*n+1I
seq { if n <> 1I then yield! sequence (next n) }

let answer1:Lazy = lazy (seq { 1I..999999I } |> Seq.map sequence |> Seq.maxBy Seq.length |> Seq.hd)

This works, but it’s really slow trying to compute all of those sequences. Let’s try to memoize this function:

```
open System.Collections.Generic
```let memoize (func:'a->'b) =
let cache = Dictionary<_, _>()
fun n ->
let (found, result) = cache.TryGetValue(n)
if found then
result
else
let result = func n
cache.[n] <- result
result

let rec length:bigint->int =
let f n =
let next n = if isEven n then n/2I else 3I*n+1I
if n = 1I then 1
else 1 + length (next n)
f |> memoize

let answer2 = lazy(seq { 1I..999999I } |> Seq.maxBy length)

Instead of generating the sequence I simply compute the length of it and save the result – the time to generate the answer dropped from over 3 minutes to under 10 seconds on my machine.

]]>The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

Starting with the prime-generating code from my solution to problem #7:

```
open System
```let dividesEvenly dividend divisor = int64(dividend % divisor) = 0L
let add x y = x + y

let rec isPrime x =
let limit = int(Math.Sqrt(float(x)))
primes |> LazyList.to_seq |> Seq.takeWhile (fun i -> i <= limit) |> Seq.exists (dividesEvenly x) |> not

and primes =
let nextPrime prevPrime =
Seq.initInfinite (add (prevPrime + 1))
|> Seq.filter isPrime
|> Seq.hd
let rec PrimesStartingFrom prime =
LazyList.consf prime (fun () -> PrimesStartingFrom (nextPrime prime))
LazyList.consf 2 (fun () -> PrimesStartingFrom 3)

All we need to do is add all of the primes below 2 million. Utilizing F#’s BigInt support we arrive at:

```
open Microsoft.FSharp.Math
```let sum =
primes
|> Seq.takeWhile (fun i -> i < 2000000)
|> Seq.map (fun i -> new bigint(i))
|> Seq.fold (+) 0I

]]>A Pythagorean triplet is a set of three natural numbers,a<b<c, for which,a+^{2}b=^{2}cFor example, 3^{2}^{2}+ 4^{2}= 9 + 16 = 25 = 5^{2}. There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the productabc.

```
let triplet =
seq {
for a = 0 to 332 do // since a < b < c the max a can be is 332
for b = a+1 to 499 do // since b < c the max b can be is 499
let c = 1000 - a - b
if a
```*a + b*b = c*c then yield (a, b, c)
}
|> Seq.hd

]]>