[Haskell-cafe] Zumkeller numbers

[Richard O'Keefe]

On Dec 8, 2009, at 10:33 AM, Frank Buss wrote:

> Anyone interested in writing some lines of Haskell code for  
> generating the Zumkeller numbers?
>
> http://www.luschny.de/math/seq/ZumkellerNumbers.html

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])