Personal tools

Haskell Quiz/Weird Numbers/Solution Bailey

From HaskellWiki

< Haskell Quiz | Weird Numbers(Difference between revisions)
Jump to: navigation, search
(sharpen cat)
m
 
Line 1: Line 1:
 
[[Category:Haskell Quiz solutions|Weird Numbers]]
 
[[Category:Haskell Quiz solutions|Weird Numbers]]
   
The implementation below isn't very effecient, apparently (the thread referred to in the comments talks about why not), or particulary fast, but it does work.
+
The implementation below isn't very efficient, apparently (the thread referred to in the comments talks about why not), or particularly fast, but it does work.
   
 
The heart of the solution is the ''is_weird'' function. It takes a number and determines if its weird. The first weird number is 70, so all numbers below that are thrown out.
 
The heart of the solution is the ''is_weird'' function. It takes a number and determines if its weird. The first weird number is 70, so all numbers below that are thrown out.
Line 24: Line 24:
 
is_weird n | n < 70 = False
 
is_weird n | n < 70 = False
 
is_weird n =
 
is_weird n =
let divisors = [div | div <- [1..(floor ((fromInteger n / 2)))], n `mod` div == 0]
+
let divisors = [d | d <- [1..(n `div` 2)], n `mod` d == 0]
 
divisor_subsets = powerSet divisors
 
divisor_subsets = powerSet divisors
 
in
 
in
(foldr (+) 0 divisors) > n && not (any (\subset -> (foldr (+) 0 subset) == n) divisor_subsets)
+
sum divisors > n && not (any (\subset -> sum subset == n) divisor_subsets)
   
 
find_weird n = take n [w | w <- [70..], is_weird w]
 
find_weird n = take n [w | w <- [70..], is_weird w]

Latest revision as of 07:25, 11 February 2010


The implementation below isn't very efficient, apparently (the thread referred to in the comments talks about why not), or particularly fast, but it does work.

The heart of the solution is the is_weird function. It takes a number and determines if its weird. The first weird number is 70, so all numbers below that are thrown out.

If the number is greater than 70, I first find all the divisors up to n / 2 for that number. Using powerSet, I then find all possible subsets of those divisors.

Finally, the function first ensures the sum of all the divisors is greater than n. Next, it searches all the subsets and determines if any of them sum to the value of n. If not, the number is weird!

Optimizations might include generating the powerset such that the longest lists come first, to find numbers that aren't weird sooner.

A bonus function, find_weird, takes an argument and finds the first n weird numbers.

-- powerSet found courtesy of http://haskell.org/hawiki/PreludeExts
-- originally from  http://www.haskell.org/pipermail/haskell-cafe/2003-June/004484.html
powerSet :: [a] -> [[a]]
powerSet [] = [[]]
powerSet (x:xs) = xss ++ map (x:) xss
                where xss = powerSet xs
 
-- Only positive numbers. 70 is first weird number, so exclude all below 69.
is_weird n | n < 70 = False
is_weird n =
    let divisors = [d | d <- [1..(n `div` 2)], n `mod` d == 0]
        divisor_subsets = powerSet divisors
  in
    sum divisors > n && not (any (\subset -> sum subset == n) divisor_subsets)
 
find_weird n = take n [w | w <- [70..], is_weird w]