Project Euler Problem 43 Solution

Question

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d_1 be the 1^{st} digit, d_2 be the 2^{nd} digit, and so on. In this way, we note the following:

\begin{aligned} d_2d_3d_4 & =406 \text{ is divisible by 2} \\ d_3d_4d_5 & =063 \text{ is divisible by 3} \\ d_4d_5d_6 & =635 \text{ is divisible by 5} \\ d_5d_6d_7 & =357 \text{ is divisible by 7} \\ d_6d_7d_8 & =572 \text{ is divisible by 11} \\ d_7d_8d_9 & =728 \text{ is divisible by 13} \\ d_8d_9d_{10} & =289 \text{ is divisible by 17} \end{aligned}

Find the sum of all 0 to 9 pandigital numbers with this property.

Haskell

import Data.List (nub)

expand :: Int -> String -> [String]
expand x "" = [s | n <- [100..999], n `rem` x == 0, let s = show n, s == nub s]
expand x s = [c:s | c <- ['0'..'9'], c `notElem` s, (read (c:take 2 s)) `rem` x == 0]

candidates :: [String]
candidates = inner [17, 13, 11, 7, 5, 3, 2, 1] [""] where
    inner [] acc = acc
    inner (x:xs) acc = inner xs $ concatMap (expand x) acc

main :: IO ()
main = print $ sum $ map read candidates

$ ghc -O2 -o pandigital-substrings pandigital-substrings.hs
$ time ./pandigital-substrings
real   0m0.003s
user   0m0.000s
sys    0m0.003s

Python

#!/usr/bin/env python
from itertools import *

def has_property(digits):
    primes = [1,2,3,5,7,11,13,17]
    for i in range(1, len(digits)-2):
        if not int(''.join(digits[i:i+3])) % primes[i] == 0:
            return False
    return True 

def convert_list_to_int(l):
    return int(''.join(str(i) for i in l))

def main():
    pandigitals = permutations((str(i) for i in range(10)))
    print(sum(convert_list_to_int(p) for p in pandigitals if has_property(p)))

if __name__ == "__main__":
    main()

$ time python3 pandigital-substrings.py
real   0m6.723s
user   0m6.723s
sys    0m0.000s

Ruby

#!/usr/bin/env ruby
primes = [1,2,3,5,7,11,13,17]
puts ('0'..'9').to_a.permutation.select { |digits| 
  (1..7).all? { |i|
    digits[i..i+2].join('').to_i % primes[i] == 0
  }
}.map { |digits| digits.join('').to_i }.reduce(:+)

$ time ruby pandigital-substrings.rb
real   0m6.471s
user   0m6.470s
sys    0m0.000s