Euler Solution 43

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 43

Find the sum of all the ten digit pandigital (0..9) numbers with the following substring divisability properties:

  1. d2d3d4 is divisible by 2
  2. d3d4d5 is divisible by 3
  3. d4d5d6 is divisible by 5
  4. d5d6d7 is divisible by 7
  5. d6d7d8 is divisible by 11
  6. d7d8d9 is divisible by 13
  7. d8d9d10 is divisible by 17

where di is the ith digit of the number.

Haskell by SanguineV

Runtime: 167.035 ms (on aglaope)

{- Checking each of the possible numbers is too complex, instead build up from the
 - bottom with each one adding digits as suitable. -}

{- Start with numbers in the range 1-1000 divisible by 17 -}
div17 = filter (\x -> mod x 17 == 0) [1..1000]

{- Add each of the digits 0..9 to the front of each number divisibly by 17 and check
 - divisibility by 13 dropping last digit. -}
div13 = filter (\x -> mod (div x 10) 13 == 0) 
          (foldl (\x y -> x ++ (map (\z -> y + (z * 1000)) [0..9])) [] div17)

{- Add the digits 0, 5 to the front of each number (this ensures divisibility by 5 later)
 - and then check divisibility by 11 dropping last 2 digits. -}
div11 = filter (\x -> mod (div x 100) 11 == 0) 
           (foldl (\x y -> x ++ (map (\z -> y + (z * 10000)) [0,5])) [] div13)

{- Add digits 0..9 to the front of each number generated so far and then check for
 - divisibility by 7 dropping the last 3 digits. -}
div7 = filter (\x -> mod (div x 1000) 7 == 0) 
         (foldl (\x y -> x ++ (map (\z -> y + (z * 100000)) [0..9])) [] div11)

{- Already divisibly by 5 dropping 4 digits, so add even digits to ensure the
 - divisibility by 2 later. -}
div5 = foldl (\x y -> x ++ (map (\z -> y + (z * 1000000)) [0,2,4,6,8])) [] div7

{- Add digits 0..9 to the front of each number and check for divisibility by 3 after
 - dropping the last 5 digits. -}
div3 = filter (\x -> mod (div x 100000) 3 == 0) 
         (foldl (\x y -> x ++ (map (\z -> y + (z * 10000000)) [0..9])) [] div5)

{- Already certain to be divisible by 2, add 2 digits to the front of each number -}
div2 = foldl (\x y -> x ++ (map (\z -> y + (z * 100000000)) [0..99])) [] div3

{- Check for pandigital on the digits 0..9 -}
panDig :: Integer -> Bool
panDig n = foldl (\x y -> x && elem y (show n)) True "0123456789"

{- Filter all the potential numbers from div2 and sum the ones that are pandigital. -}
main = print (sum (filter panDig div2))
Personal tools