# Euler Solution 43

### From ProgSoc Wiki

# Solutions for Problem 43

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

- d
_{2}d_{3}d_{4}is divisible by 2 - d
_{3}d_{4}d_{5}is divisible by 3 - d
_{4}d_{5}d_{6}is divisible by 5 - d
_{5}d_{6}d_{7}is divisible by 7 - d
_{6}d_{7}d_{8}is divisible by 11 - d
_{7}d_{8}d_{9}is divisible by 13 - d
_{8}d_{9}d_{10}is divisible by 17

where d_{i} 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))