[Haskell-cafe] Zumkeller numbers
Daniel Fischer
daniel.is.fischer at web.de
Tue Dec 8 07:15:49 EST 2009
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
More information about the Haskell-Cafe
mailing list