[Haskell-cafe] Zumkeller numbers
Frank Buss
fb at frank-buss.de
Mon Dec 7 18:45:22 EST 2009
> 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
More information about the Haskell-Cafe
mailing list