Project Euler Problem 41 Solution

Question

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?

Haskell

import Data.List (permutations)

isPrime :: Int -> Bool
isPrime n | n <= 1 = False
          | otherwise = not $ or [n `rem` x == 0 | x <- [2..floor $ sqrt $ fromIntegral n]]

candidates :: [Int]
candidates = filter isPrime $ concatMap (\n -> map (read . concatMap show) $ permutations [1..n]) [1..7]

main :: IO ()
main = print $ maximum candidates
$ ghc -O2 -o pandigital-prime pandigital-prime.hs
$ time ./pandigital-prime
real   0m0.051s
user   0m0.048s
sys    0m0.000s

Python

#!/usr/bin/env python3
from collections import defaultdict
from itertools import *
from functools import reduce
import math

def is_pandigital(num):
    digits = sorted(int(d) for d in str(num))
    if digits == list(range(1,len(digits)+1)):
        return True
    else:
        return False

def factorize(n):
    if n < 1:
        raise ValueError('fact() argument should be >= 1')
    if n == 1:
        return []  # special case
    res = []
    # iterate over all even numbers first.
    while n % 2 == 0:
        res.append(2)
        n //= 2
    # try odd numbers up to sqrt(n)
    limit = math.sqrt(n+1)
    i = 3
    while i <= limit:
        if n % i == 0:
            res.append(i)
            n //= i
            limit = math.sqrt(n+i)
        else:
            i += 2
    if n != 1:
        res.append(n)
    return res

def num_divisors(n):
    factors = sorted(factorize(n))
    histogram = defaultdict(int)
    for factor in factors:
        histogram[factor] += 1
    # number of divisors is equal to product of 
    # incremented exponents of prime factors
    from operator import mul
    try:
        return reduce(mul, [exponent + 1 for exponent in list(histogram.values())])
    except:
        return 1

def is_prime(num):
    if num % 2 == 0:
        return False
    if num % 3 == 0:
        return False

    if num_divisors(num) == 2 and num > 1:
        return True
    else:
        return False

def convert_list_to_int(l):
    return int(''.join(str(d) for d in l))

def main():
    pandigitals = (convert_list_to_int(p) for p in permutations(list(range(1,8))))
    print((max(p for p in pandigitals if is_prime(p))))

if __name__ == "__main__":
    main()
$ time python3 pandigital-prime.py
real   0m0.296s
user   0m0.284s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
require 'mathn'
puts (1..9).flat_map { |n|
  ('1'..n.to_s).to_a.permutation.map { |p|
    p.join('').to_i
  }.select { |i| i.prime? }
}.max
$ time ruby pandigital-prime.rb
real   0m1.269s
user   0m1.260s
sys    0m0.000s