Problem 43

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 d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

d2d3d4=406 is divisible by 2

d3d4d5=063 is divisible by 3

d4d5d6=635 is divisible by 5

d5d6d7=357 is divisible by 7

d6d7d8=572 is divisible by 11

d7d8d9=728 is divisible by 13

d8d9d10=289 is divisible by 17

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

再帰とリストモナドを使って書いてみた。

import Data.List
import Data.Char
import Control.Monad
perm ::Eq a =>[a]->Int->[[a]]
perm _  = [[]]
perm [] _ = []
perm xs@(_:_) (n+1)=concat[map (h:)$perm(delete h xs)n|h<-xs]
pandigital xs _ [] =[xs]
pandigital [x,y] (p:ps) ds =
do z<- ds
guard(divisible p [x,y,z])
ys <- pandigital [y,z] ps $delete z ds
return $x:ys
where divisible n = (==).flip mod n.read
p043 =sum.map read$[d:dds|(d:ds)<-perm digit 3,d/='0',
dds<-pandigital ds divisor $digit(d:ds)]
where digit ="0123456789"
divisor = [2,3,5,7,11,13,17]