Project Euler – Problem 41 Solution

Yan Cui

I help clients go faster for less using serverless technologies.

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?

Solution

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)

let hasDivisor(n) =
    let upperBound = int64(sqrt(double(n)))
    [2L..upperBound] |> Seq.exists (fun x -> n % x = 0L)
let isPrime(n) = if n = 1L then false else not(hasDivisor(n))

let answer =
    [1..9]
    |> List.collect (fun m -> [1..m] |> permute)
    |> List.map (fun l -> l |> List.map string |> List.reduce (fun acc item -> acc + item))
    |> List.map int64
    |> List.filter isPrime
    |> List.max

This is a simple brute force solution which for n = 1..9 generates all permutations of 1..n, for each permutation the digits are merged into a number, e.g. [1; 4; 8; 7] –> 1487, and the max prime number is returned.

Whenever you’re ready, here are 3 ways I can help you:

  1. Production-Ready Serverless: Join 20+ AWS Heroes & Community Builders and 1000+ other students in levelling up your serverless game. This is your one-stop shop for quickly levelling up your serverless skills.
  2. I help clients launch product ideas, improve their development processes and upskill their teams. If you’d like to work together, then let’s get in touch.
  3. Join my community on Discord, ask questions, and join the discussion on all things AWS and Serverless.

2 thoughts on “Project Euler – Problem 41 Solution”

  1. Vinícius Manjabosco

    Use this method to check for primes, is 10 times faster.

    let isPrime n =
    if n float |> sqrt |> int
    let rec check i = i > maximumDivisor || (n % i 0 && check (i + 1))
    check 2

  2. Check out some of the later answers, I started to use a siev which was able to generate 1 million primes in well under a second on my machine. (didn’t know what a siev is when I put this answer together unfortunately…)

Leave a Comment

Your email address will not be published. Required fields are marked *