## 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?

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