[Haskell-cafe] Zumkeller numbers

[Frank Buss]

> From: Richard O'Keefe [mailto:ok at cs.otago.ac.nz]
> 
> These lines of Haskell code find the Zumkeller numbers up to 5000
> in 5 seconds on a 2.2GHz intel Mac.  The equivalent in SML took
> 1.1 seconds.  Note that this just finds whether a suitable
> partition exists; it does not report the partition.
> 
> factors :: Int -> [Int]
> 
> factors n = [m | m <- [1..n], mod n m == 0]
> 
> can_part :: [Int] -> Int -> Bool
> 
> can_part _  0 = True
> can_part xs t = loop xs []
>    where loop [] _ = False
>          loop (x:xs) ys = x <= t && can_part (xs++ys) (t-x)
>                        || loop xs ys
> 
> is_Zumkeller :: Int -> Bool
> is_Zumkeller n =
>      let facs = factors n
>          fsum = sum facs
>      in  mod fsum 2 == 0 &&
>          can_part facs (div fsum 2)
> 
> main = print (filter is_Zumkeller [1..5000])

Thanks, I like this solution! Pure functional, easy to understand, no monads
and fast :-)

-- 
Frank Buss, fb at frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de