Excerpts from Henning Thielemann's message of Mon Dec 07 20:36:27 +0100 2009:

@Apfelmus:

For practical purposes I think Train should have swapped type parameters in order to make Functor act on the type of the list elements.

data Train b a = Wagon a (Train b a) | Loco b

The functor on the Loco/Caboose makes sense too and swapping the arguments is less natural to read. -- Nicolas Pouillard http://nicolaspouillard.fr

Here's a completely naive implementation, it's slow as cold molasses going uphill during a blizzard, but it doesn't seem to be wrong. I let it run in the interpreter for the last 3 minutes or so and it's reproduced the given list up to 126 (and hasn't crapped out yet). I imagine there's probably a less naive algorithm that could be done, but I rather like the straightforwardness of this one... /Joe ---------------------------- module Main where import Control.Monad(filterM) import Data.List(sort) divisors :: Int -> [Int] divisors n = [d | d <- [1..n], n `mod` d == 0] powerset = filterM (const [True, False]) (><) :: Eq a => [a] -> [a] -> [(a,a)] x >< y = [(x', y') | x' <- x, y' <- y, x' /= y'] (/\) :: Eq a => [a] -> [a] -> Bool x /\ y = null $ filter (`elem` x) y prod m n = filter (uncurry (/\)) (m >< n) eqSum :: ([Int], [Int]) -> Bool eqSum (m, n) = sum m == sum n containsAllDivisors i l = filter (\x -> (sort . uncurry (++) $ x) == divisors i) l zumkeller :: Int -> [([Int], [Int])] zumkeller n = containsAllDivisors n . filter eqSum . (\x -> prod x x) $ allParts where divs = divisors n allParts = powerset divs zumkellerP :: Int -> Bool zumkellerP = not . null . zumkeller --------------------------------------- On Dec 7, 2009, at 4:33 PM, 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

My C/C# solutions looks clumsy (but is fast). I think this can be done much more elegant in Haskell with lazy evaluation.

Not related to Haskell, but do you think semi-Zumkeller numbers are semi-perfect numbers? Maybe some Haskell code for testing it for some numbers?

-- Frank Buss, fb@frank-buss.de http://www.frank-buss.de, http://www.it4-systems.de

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

Am Montag 07 Dezember 2009 22:33:32 schrieb Frank Buss:

Anyone interested in writing some lines of Haskell code for generating the Zumkeller numbers?

http://www.luschny.de/math/seq/ZumkellerNumbers.html

My C/C# solutions looks clumsy (but is fast). I think this can be done much more elegant in Haskell with lazy evaluation.

A fairly naive but not too slow version: --------------------------------------------------------------------------------- module Main (main) where import Data.List (sort) import Control.Monad (liftM2) import System.Environment (getArgs) main = do args <- getArgs let bd = case args of (a:_) -> read a _ -> 1000 mapM_ print $ filter isZumkeller [2 .. bd] trialDivPrime :: [Int] -> Int -> Bool trialDivPrime (p:ps) n = (p*p > n) || (n `mod` p /= 0) && trialDivPrime ps n oprs = 5:7:filter (trialDivPrime oprs) (scanl (+) 11 $ cycle [2,4]) primes :: [Int] primes = 2:3:oprs factors :: Int -> [(Int,Int)] factors n | n < 0 = factors (-n) | n == 0 = [(0,1)] | otherwise = go n primes where go 1 _ = [] go m (p:ps) | p*p > m = [(m,1)] | otherwise = case m `quotRem` p of (q,0) -> case countFactors q p of (m',k) -> (p,k+1):go m' ps _ -> go m ps countFactors :: Int -> Int -> (Int,Int) countFactors n p = go n 0 where go m k = case m `quotRem` p of (q,0) -> go q (k+1) _ -> (m,k) divisors :: Int -> [Int] divisors n = sort $ foldr (liftM2 (*)) [1] ppds where ppds = map (\(p,k) -> take (k+1) $ iterate (*p) 1) $ factors n partition :: Int -> [Int] -> [[Int]] partition 0 _ = [[]] partition n [] = [] partition n (p:ps) | n < p = partition n ps | otherwise = [p:parts | parts <- partition (n-p) ps] ++ partition n ps isZumkeller :: Int -> Bool isZumkeller n | sigma < 2*n = False | odd sigma = False | otherwise = not . null $ partition target candidates where divs = divisors n sigma = sum divs target = (sigma-n) `quot` 2 candidates = reverse $ takeWhile (<= target) divs ---------------------------------------------------------------------------------------------------- Of course, with sieving, you'd be much faster.

Not related to Haskell, but do you think semi-Zumkeller numbers are semi-perfect numbers?

The site you linked to says so. I've not investigated.

Maybe some Haskell code for testing it for some numbers?

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

On Tue, 8 Dec 2009, Richard O'Keefe wrote:

is_Zumkeller :: Int -> Bool is_Zumkeller n = let facs = factors n fsum = sum facs in mod fsum 2 == 0 &&

I see this test is essential. I didn't do it and thus my program did not find that 1800 is not a Zumkeller number within an hour. With this check my program becomes dramatically faster.

can_part facs (div fsum 2)

main = print (filter is_Zumkeller [1..5000])

Am Dienstag 08 Dezember 2009 01:54:12 schrieb ajb@spamcop.net:

G'day all.

Quoting Richard O'Keefe :

...

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.

This takes 0.1 seconds on a 2GHz Dell running Linux: <snip>

Yes, I cheated by using a different algorithm.

Cheers, Andrew Bromage

Yes, what I do (after fixing an embarrassing typo from the first post). Using Int, it's a little faster, with Integer the same time. I've now added the printout of one partition. module Main (main) where import Data.List (sort) import Control.Monad (liftM2) import System.Environment (getArgs) main = do args <- getArgs let bd = case args of (a:_) -> read a _ -> 4000 mapM_ (\n -> case zumParts n of [] -> return () ((l,r):_) -> putStrLn (show n ++ " " ++ show l ++ " " ++ show r)) [1 .. bd] trialDivPrime :: [Int] -> Int -> Bool trialDivPrime (p:ps) n = (p*p > n) || (n `mod` p /= 0) && trialDivPrime ps n oprs = 5:7:filter (trialDivPrime oprs) (scanl (+) 11 $ cycle [2,4]) primes :: [Int] primes = 2:3:oprs factors :: Int -> [(Int,Int)] factors n | n < 0 = factors (-n) | n == 0 = [(0,1)] | otherwise = go n primes where go 1 _ = [] go m (p:ps) | p*p > m = [(m,1)] | otherwise = case m `quotRem` p of (q,0) -> case countFactors q p of (m',k) -> (p,k+1):go m' ps _ -> go m ps countFactors :: Int -> Int -> (Int,Int) countFactors n p = go n 0 where go m k = case m `quotRem` p of (q,0) -> go q (k+1) _ -> (m,k) divisors :: Int -> [Int] divisors n = sort $ foldr (liftM2 (*)) [1] ppds where ppds = map (\(p,k) -> take (k+1) $ iterate (*p) 1) $ factors n partition :: Int -> [Int] -> [[Int]] partition 0 _ = [[]] partition n [] = [] partition n (p:ps) | n < p = partition n ps | otherwise = [p:parts | parts <- partition (n-p) ps] ++ partition n ps zumParts :: Int -> [([Int],[Int])] zumParts n | sigma < 2*n = [] | odd sigma = [] | otherwise = [(prt ++ [n],init divs `without` prt) | prt <- prts] where divs = divisors n sigma = sum divs target = (sigma-2*n) `quot` 2 sml = takeWhile (<= target) $ init divs prts = map reverse $ partition target (reverse sml) xxs@(x:xs) `without` yys@(y:ys) | x < y = x:xs `without` yys | x == y = xs `without` ys | otherwise = xxs `without` ys xs `without` _ = xs

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

And if you use quotRem it's faster (unless you're running on some exotic hardware like NS32K). On Tue, Dec 8, 2009 at 10:19 PM, Richard O'Keefe wrote:

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" 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.

...

_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe

On Wed, 9 Dec 2009, Daniel Fischer wrote:

Am Mittwoch 09 Dezember 2009 00:02:30 schrieb Lennart Augustsson:

...

And if you use quotRem it's faster (unless you're running on some exotic hardware like NS32K).

Yes, but Henning Thielemann was busy in the exception vs. error thread, so I didn't want to distract him by using quotRem :D

Ist der Ruf erst ruiniert, lebt es sich ganz ungeniert. 8-] Is there an English translation of it?

On Wed, Dec 9, 2009 at 11:47 AM, Henning Thielemann wrote:

Ist der Ruf erst ruiniert, lebt es sich ganz ungeniert. 8-]

Is there an English translation of it?

Google translate says : "If the reputation is ruined, one can live quite openly." David.

G'day all. Quoting Dan Weston :

Ouch. That's what happens when you let a machine do the translation. How about:

"Once your good name is trashed, you can live unabashed."

"Until you've lost your reputation, you never realize what a burden it was." -- Margaret Mitchell Cheers, Andrew Bromage

Nicolas Pouillard wrote:

Excerpts from Henning Thielemann's message of Mon Dec 07 20:36:27 +0100 2009:

...

@Apfelmus:

For practical purposes I think Train should have swapped type parameters in order to make Functor act on the type of the list elements.

data Train b a = Wagon a (Train b a) | Loco b

The functor on the Loco/Caboose makes sense too and swapping the arguments is less natural to read.

Indeed, Train is a bifunctor. Choosing one over the other is as arbitrary as choosing one over the other for (,) or Either. The only difference here is that the two functors aren't "the same". There are reasons for wanting both instances depending on how the structure is being used. It's times like this that I wish Haskell had real type-level functions, at least for swap and compose, without the need for newtype wrappers or type-family peculiarities. -- Live well, ~wren