[Haskell-cafe] Zumkeller numbers

[Richard O'Keefe]

On Dec 9, 2009, at 1:15 AM, Daniel Fischer wrote:

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

We can improve on that somewhat:

factors 1 = [1]
factors n = 1 : candidates 2 4 n [n]
   where candidates d d2 n hi =
           if d2 < n then
              let (q,r) = divMod n d in
                if r == 0 then d : candidates (d+1) (d2+d+d+1) n (q:hi)
                          else     candidates (d+1) (d2+d+d+1) n    hi
           else if d2 == n then d:hi else hi

This never constructs a cons cell it doesn't mean to keep.

>