I'm trying to write a function that computes all the weird numbers up to a given integer. To determine if a number n is pseudoperfect, I was trying to come up with a better solution than naively computing the sum of every combination of divisors until I either exhaust all the combinations or find a solution. I ended up with the idea that you can recursively reduce the problem by definitely proving inclusion of certain divisors in the sum. Take 12 for example: you know that 6 must be included in the final sum because the total of all other divisors is less than 12. Then the problem is reduced to summing to the rest of 12 (ie 12 - 6, ie 6) from the remaining divisors, and so forth. If you reach 0, then the number is pseudoperfect. If you exhaust all the divisors then it's not pseudoperfect.
Here's my code so far:
(The functions powerset and divisors do the expected: return a list of all sublists, and a list of divisors respectively. Obviously RETURN is just a placeholder for I want to do.)
pseudoperfect _ 0 = RETURN True
pseudoperfect d n =
let g = zipWith (\x y -> x) d (filter (< 0) (map (subtract n) (scanl1 (+) d))) in
map (\x -> pseudoperfect g (n - (sum x))) (filter (not . null) (powerset(d \\ g)))
-- Determine if n is weird, ie, abundant and not pseudoperfect.
weird n = ((sum . divisors) (n) > n) && not (pseudoperfect (divisors n) n)
-- Find weird numbers up to given n.
weirds n = filter (weird) [1..n]
I tried working through a couple examples on paper and I got the correct result. My problem is that I want to just break out of the recursion and return True when I reach that base case of n = 0. Is there a way to do this in Haskell, or do I need to restructure the function somehow so that I'm passing returned value at the base case value back up through the stack?