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
| n <= 1 = False
isPrime n | otherwise = not $ or [n `rem` x == 0 | x <- [2..floor $ sqrt $ fromIntegral n]]
candidates :: [Int]
= filter isPrime $ concatMap (\n -> map (read . concatMap show) $ permutations [1..n]) [1..7]
candidates
main :: IO ()
= print $ maximum candidates main
$ ghc -O2 -o pandigital-prime pandigital-prime.hs
$ time ./pandigital-prime
real 0m0.025s
user 0m0.025s
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):
= sorted(int(d) for d in str(num))
digits 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:
2)
res.append(//= 2
n # try odd numbers up to sqrt(n)
= math.sqrt(n+1)
limit = 3
i while i <= limit:
if n % i == 0:
res.append(i)//= i
n = math.sqrt(n+i)
limit else:
+= 2
i if n != 1:
res.append(n)return res
def num_divisors(n):
= sorted(factorize(n))
factors = defaultdict(int)
histogram for factor in factors:
+= 1
histogram[factor] # 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():
= (convert_list_to_int(p) for p in permutations(list(range(1,8))))
pandigitals print((max(p for p in pandigitals if is_prime(p))))
if __name__ == "__main__":
main()
$ time python3 pandigital-prime.py
real 0m0.182s
user 0m0.174s
sys 0m0.008s
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 0m0.653s
user 0m0.645s
sys 0m0.008s