問題
n桁の数が"pandigital数"であるとは、そのn桁の数の各桁に1からnまでの数がちょうど１回ずつ現れる場合を言う。
例えば 15234 は5桁のpandigital数である。
さらにこれを発展させて、例えば 7254 のような数は、
39 × 186 = 7254
というように1から9までの数がちょうど１回ずつ現れる積で書ける。
これを上の話に沿って「9桁のpandigital積」と呼ぶことにしよう。
9桁のpandigiral積で書ける数の「積」の部分の和を求めよ。
ただし、同じ数が複数のpandigital積で書ける場合がある（A*B=A'*B'=Cのように）。
その場合は重複するものは除外した和を求めよ。
回答
まず、判定の計算量を減らすために、a * b = c の式で、a,b,cの各桁に制限をつけるための関係式を導こう。
両辺のlog（底は10）をとると、
log a + log b = log c
a,b,cのそれぞれが
a=A*10^n, b=B*10^m, c=C*10^l
（ただし、1.0<=A,B,C<10.0）
と書けるので、それを代入すると、
n+log A + m+log B = l + log C
移項して、
l-(n+m) = log A+ log B - log C
今、0 <= log A,B,C <1 が成り立つので、
-1+(n+m) < l < 1+(n+m)
これにより、
l=n+m
import qualified List as L
-- 1..tの文字を使うとする
t=9
-- 1..tの全ての順列を列挙する
numlist :: [[Int]]
numlist = f [1..t]
where f [] = [[]]
f xs = concat [map (x:) (f (filter (/=x) xs)) | x<-xs]
-- a*b=cの各数の桁数制限を使って、あり得る桁数の候補を作る
ketas :: [[Int]]
ketas = [[n+1,m+1,(n+m)+1]| n<-[0..t-1],
m<-[0..t-1],
n<=m, (n+1)+(m+1)+((n+m)+1)==t]
-- 桁数の列を使って、数列を分割する
split :: [Int] -> [Int] -> [[Int]]
split [] xs = []
split (k:ks) xs = take k xs : (split ks $ drop k xs)
-- 分割された数列を１０進数のリストに変換する
makenum :: [[Int]] -> [Int]
makenum [] = []
makenum (x:xs) = (f x): (makenum xs)
where f [] = 0
f (y:ys) = y+10*(f ys)
-- a * b = c の候補[a,b,c]の列を求める
kouho :: [[Int]]
kouho = filter (\y->(y!!0)*(y!!1)==(y!!2)) $
filter (\x->(x!!0)<(x!!2) && (x!!1)<(x!!2)) [makenum (split k n) |k<-ketas, n<-numlist]
main = do
-- 積cの和を求める(重複は除外)
print $ sum $ L.nub $ map (!!2) kouho
感想
またしても考える時間の圧倒的に長い問題であった。
しかも、プログラムというよりは数学の問題として解法を考える割合が９割で、プログラムに関しては１割ぐらいしか考えていないだろう。
Project Eulerはなんだかそろそろプログラムの練習というよりは、数学の訓練の色合いが濃くなって来たように感じだしている。