60 Days of Euler in F# - Problem 36

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:

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

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.

60 Days of Euler in F# - Problem 35

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
        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
        elif candidate = 2 then
            let next = nextPrime candidate
            if next >= max then

    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) =
    |> 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:

getPrimesBelow 1000000
|> Seq.filter isCircularPrime
|> Seq.length

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.

60 Days of Euler in F# - Problem 34

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 = 
    |> 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:

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

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.

60 Days of Euler in F# - Problem 33

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

60 Days of Euler in F# - Problem 32

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

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

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.

60 Days of Euler in F# - Problem 31

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.

let target = 200

let coins = [1; 2; 5; 10; 20; 50; 100; 200]
let combos = 
    |> 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>) = 
    |> 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
                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.

|> Seq.filter matchTarget
|> Seq.length

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)

coinChange target coins.Length

60 Days of Euler in F# - Problem 30

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

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

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

60 Days of Euler in F# - Problem 29

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

60 Days of Euler in F# - Problem 28

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

60 Days of Euler in F# - Problem 27

The Problem

Euler discovered the remarkable quadratic formula:


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.

Considering quadratics of the form:

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.

let maxA = 999L

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

let a,b,n =
    |> Seq.map (fun (a,b) -> (a,b,(numPrimesProduced a b)))
    |> Seq.maxBy (fun (a,b,n) -> n)

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.