[Haskell-cafe] Zumkeller numbers
Richard O'Keefe
ok at cs.otago.ac.nz
Mon Dec 7 18:33:48 EST 2009
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])
More information about the Haskell-Cafe
mailing list