[Haskell-cafe] Zumkeller numbers

[Daniel Fischer]

Am Dienstag 08 Dezember 2009 08:44:52 schrieb Ketil Malde:
> "Richard O'Keefe" <ok at cs.otago.ac.nz> 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