I whipped a reasonably fast brute-force perfect number finding function in Haskell, after seeing a similar thing in mathematica.It works in under 3 seconds when I search up to 1000, but 10000 is too much.isDivisor :: Integral a => a -> a -> BoolisDivisor n a = mod n a == 0sumDivisors :: Integral a => a -> asumDivisors a =   foldr (\n -> if isDivisor a n then (+ n) else id) 0 [1..(a `div` 2)]isPerfect :: Integral a => a -> BoolisPerfect n = n == sumDivisors n-- The main prime-finding function:upUntil :: Integral a => a -> [a]upUntil n = filter isPerfect [1..n]It certainly isn't the fastest, or the most elegant, but I'm unsure how I can improve it.I would like to concentrate on the isDivisor function in particular. Is there a more efficient way of checking for divisibility?
Brute-force perfect-number algorithm
haskell;mathematics
Based on this Wikipedia article, here's a function to calculate the first n perfect numbers:Import Data.Numbers.Primes(primes, isPrime) -- https://hackage.haskell.org/package/primes-0.2.1.0/docs/src/Data-Numbers-Primes.html-- A perfect number is a number of the form 2p1 (2p  1) -- where 2p  1 is a Mersenne prime (http://en.wikipedia.org/wiki/List_of_perfect_numbers)firstPerfectNumbers :: Int -> [Integer]firstPerfectNumbers n =     take n [2 ^ (x - 1) * (2 ^ x - 1) | x <- primes, isPrime(2 ^ x - 1)]This function returns the first 8 numbers in a second, but slows down after that.Your original upUntil function could be implemented like this:perfectNumbersUpTo :: Integer -> [Integer]perfectNumbersUpTo n =     takeWhile (< n) [2 ^ (x - 1) * (2 ^ x - 1) | x <- primes, isPrime(2 ^ x - 1)]But of course, seeing as there are only 35 perfect numbers with less than 1,000,000 digits and 48 known numbers, if I wanted to use a perfect number in a program I would probably use a precomputed table.Also, if you aren't using your upUntil function to try to find new perfect numbers, or if your program isn't critically dependent on a perfect number of humongous size, then your isPerfect function would probably benefit from this:isPerfect n | odd n = FalseBecause it's not known whether odd perfect numbers exist.