Re: [Haskell-cafe] Zumkeller numbers

Am Dienstag 08 Dezember 2009 08:44:52 schrieb Ketil Malde:

"Richard O'Keefe" writes:

...

factors n = [m | m <- [1..n], mod n m == 0]

-- saves about 10% time, seems to give the same result: factors n = [m | m <- [1..n `div` 2], mod n m == 0]++[n]

Even faster (for large enough n): factors n = mergeAll [if q == d then [d] else [d, q] | d <- [1 .. isqrt n] , let (q,r) = n `divMod` d, r == 0]

(But checking against primes is even faster, it seems)

That's peanuts, the important part is to partition smaller numbers (i.e. (sigma(n)-2*n) vs. sigma(n)). Still faster would be using the fact that if n is Zumkeller and gcd n m = 1, then n*m is Zumkeller, too.

-k