Re: [Haskell-cafe] Zumkeller numbers
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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." David Virebayre wrote: 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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
Am Mittwoch 09 Dezember 2009 11:47:49 schrieb Henning Thielemann: > 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-] If it were so easy. Not that I'd compare you to Serge Lang, but you also have a reputation besides the zealotism. > > Is there an English translation of it? None that I know of. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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 > ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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) nhi 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
Re: [Haskell-cafe] Zumkeller numbers
On Dec 8, 2009, at 8:44 PM, Ketil Malde wrote: "Richard O'Keefe" writes: factors n = [m | m <- [1..n], mod n m == 0] I should remark that I wasn't *trying* to write fast code. I was trying to code as directly as I could, fully expecting to have to rewrite later. I was pleasantly surprised that it was fast enough for my purposes. The focus of my attention was actually on "can this list of numbers be divided into two parts with the same sum", which was to me the novel part. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
"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] (But checking against primes is even faster, it seems) -k -- If I haven't seen further, it is by standing in the footprints of giants ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
Am Dienstag 08 Dezember 2009 01:54:12 schrieb a...@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: > > 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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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: module Main where import Control.Monad import qualified Data.List as L primesUpTo :: Integer -> [Integer] primesUpTo n | n < 13 = takeWhile (<= n) [2,3,5,11] | otherwise = takeWhile (<= n) primes where primes = 2 : 3 : sieve 0 (tail primes) 5 sieve k (p:ps) x = let fs = take k (tail primes) in [x | x<-[x,x+2..p*p-2], and [x `rem` p /= 0 | p<-fs] ] ++ sieve (k+1) ps (p*p+2) pseudoPrimesUpTo :: Integer -> [Integer] pseudoPrimesUpTo n | n <= wheelModulus = takeWhile (<= n) smallPrimes | otherwise = smallPrimes ++ pseudoPrimesUpTo' wheelModulus where largestSmallPrime = 11 verySmallPrimes = primesUpTo largestSmallPrime wheelModulus = product verySmallPrimes smallPrimes = primesUpTo wheelModulus wheel = mkWheel 1 [1] verySmallPrimes mkWheel _ rs [] = rs mkWheel n rs (p:ps) = mkWheel (p*n) (do k <- [0..p-1] r <- rs let r' = n*k + r guard (r' `mod` p /= 0) return r') ps pseudoPrimesUpTo' base | n <= base + wheelModulus = takeWhile (<= n) . map (+base) $ wheel | otherwise = map (+base) wheel ++ pseudoPrimesUpTo' (base + wheelModulus) -- Integer square root. isqrt :: Integer -> Integer isqrt n | n < 0 = error "isqrt" | otherwise = isqrt' ((n+1) `div` 2) where isqrt' s | s*s <= n && n < (s+1)*(s+1) = s | otherwise = isqrt' ((s + (n `div` s)) `div` 2) -- Compute the prime factorisation of an integer. factor :: Integer -> [Integer] factor n | n <= 0 = error "factor" | n <= primeCutoff = factor' n (primesUpTo primeCutoff) | otherwise= factor' n (pseudoPrimesUpTo (isqrt n)) where primeCutoff = 100 factor' 1 _ = [] factor' n [] = [n] factor' n (p:ps) | n `mod` p == 0 = p : factor' (n `div` p) (p:ps) | otherwise = factor' n ps -- The only function used from above is "factor". zumkeller :: Integer -> Bool zumkeller n | isPrime= False | isPrime= False | sigma `mod` 2 == 1 = False | sigma < 2*n= False | otherwise = sigmaTest ((sigma - 2*n) `div` 2) (factors n) where isPrime = case factorn of [_] -> True _ -> False factorn = factor n sigma = product . map (sum . scanl (*) 1) . L.group $ factorn factors n = reverse [ f | f <- [1..n `div` 2], n `mod` f == 0 ] sigmaTest 0 _ = True sigmaTest _ [] = False sigmaTest n (f:fs) | f > n = sigmaTest n fs | otherwise = sigmaTest (n-f) fs || sigmaTest n fs main = print (filter zumkeller [1..5000]) Yes, I cheated by using a different algorithm. Cheers, Andrew Bromage ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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]) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] Zumkeller numbers
> From: Richard O'Keefe [mailto:o...@cs.otago.ac.nz] > > 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]) Thanks, I like this solution! Pure functional, easy to understand, no monads and fast :-) -- Frank Buss, f...@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
RE: [Haskell-cafe] Zumkeller numbers
> From: daniel.is.fisc...@web.de [mailto:daniel.is.fisc...@web.de] > > 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. Peter Luschny posted the link in a discussion in a German newsgroup: http://tinyurl.com/y9kfdpf Currently it is a conjecture and needs a proof before posting it to Sloane's integer sequences archive. -- Frank Buss, f...@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
Re: [Haskell-cafe] Zumkeller 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]) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
On Mon, 7 Dec 2009, 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. http://darcs.haskell.org/htam/src/Example/Zumkeller.hs ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Zumkeller numbers
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, f...@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 ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Zumkeller numbers
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, f...@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
