By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below

type BinaryTree =
    | Node of int * BinaryTree * BinaryTree
    | Empty

let rec calculate tree =
    match tree with
    | Node (n, left, right) -> n + List.max [(calculate left); (calculate right)]
    | Empty -> 0

let s_data =
    [
    "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 rec data_tree (data : string list) row i =
    let data_row row_number = data.[row_number].Split(' ') |> Seq.map (fun s -> System.Int32.Parse(s)) |> Seq.toList
    let length = data.Length
    match row with
    | 15 -> Empty
    | _ -> Node ((data_row row).[i], data_tree data (row + 1) i, data_tree data (row + 1) (i + 1))

data_tree s_data 0 0 |> calculate;;

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?

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

let rec translate (n:int) : string =
    if n = 0 then
        System.String.Empty
    elif dictionary |> List.exists (fun (x, s) -> x = n) then
        snd (dictionary |> List.find (fun (x, s) -> n = x)) + " "
    else
        let log10 x = x |> float |> System.Math.Log10 |> System.Math.Truncate
        let first_number x = System.Math.Truncate((x |> float) / (10.0 ** log10 x))
        let part x = (first_number x) * 10.0 ** log10 x |> int

        if 2.0 = log10 n then
            let rest = translate (n - part n)
            translate (first_number n |> int) + "hundred " + if System.String.IsNullOrWhiteSpace(rest) then "" else "and " + rest
        else
            (translate (part n)) + (translate (n - (part n)))

(List.fold (fun acc n -> acc + translate n) "" [1..1000]).Replace(" ", System.String.Empty).Length

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

How many routes are there through a 2020 grid?

let rec find_path square_size x y =
    let complete = x = square_size || y = square_size
    match complete with
    | true -> 1L
    | false -> (find_path square_size (x + 1) y) + find_path square_size x (y + 1)

// This will take some time
find_path 20 0 0

2¹⁵ = 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¹⁰⁰⁰?

let rec exp n e =
    match e = 0 with
    | true  -> 1I
    | false -> n * exp n (e - 1) 

let sum n =
    n |> string |> Seq.fold (fun acc x -> acc + System.Int32.Parse(x |> string)) 0

exp 2I 1000 |> sum

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?

let rec calculate_length (n:int64) =
    let even_f x = x / 2L
    let odd_f x = 3L * x + 1L
    let is_even = n % 2L = 0L
    if n = 1L then
        1
    else
        if is_even then
            1 + calculate_length (even_f n)
        else
            1 + calculate_length (odd_f n)

let rec find_longest n greatest =
    if n = 1000000 then
        fst greatest
    else
        let length = calculate_length (n |> int64)
        if length > (snd greatest) then
            find_longest (n + 1) (n, length)
        else
            find_longest (n + 1) greatest

find_longest 1 (0,0)