Euler Solution 41

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 41

Find the largest n digit (> 1) pandigital prime number.

Haskell by SanguineV

Runtime: 88.45 seconds (on aglaope)

{- Generate primes in the usual way -}
primes :: [Integer]
primes = 2:3:primes'
  where
    1:p:candidates  = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n       = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p     = n `mod` p == 0

{- Test for pandigital, note this assumes 7 digits (see why later). -}
panDig :: Integer -> Bool
panDig n = foldl (\x y -> x && elem y strN) True "1234567"
  where
    strN = show n

{- There are no pandigital primes with 1, 2 or 3 digits according to the problem.
 - Some thought shows that 1 digit fails as the only potential prime is "1", not prime.
 - The digits for n = 2,3 sum to a number divisible by 3 (i.e. 1 + 2 = 3, 1 + 2 + 3 = 6),
 - thus any 2 or 3 digit pandigital numbers are not prime. The same is true for 5, 6, 8 
 - and 9 digit pandigital numbers. So limit the search space to 7 digit primes. -}
main = print (last (filter panDig (takeWhile (< 10000000) (dropWhile (< 1000000) primes))))
Personal tools