Discussion on: Write a script to find "Perfect Numbers"

[Kasey Speakman]

F#

let getDivisors n =
    let limit = int64 (sqrt (float n))
    [
        for i = 1L to limit do
            if n % i = 0L then
                yield i
                let result = n / i
                if result <> i && result <> n then
                    yield result
    ]


let isPerfect n =
    n = (n |> getDivisors |> List.sum)

Usage

(*
   per @nektro's observation on perfect numbers in binary
   * perfect numbers have an odd number of bits
   * the first half (rounded up) are 1s
   * the second half (rounded down) are 0s
*)

// Creates a perfect number candidate of the given bit length.
// Not all candidates are perfect numbers.
// Example: createCandidate 3 returns 110b or 6
//          createCandidate 5 returns 11100b or 28
let createCandidate bitLength =
    let zeroStart = bitLength / 2 + 1
    let update num i =
        let shifted = num * 2L
        if i < zeroStart then shifted + 1L
        else                  shifted
    List.init bitLength id |> List.fold update 0L

let oddBitLengths = // 1, 3, 5, 7, 9, ... , 61
    Seq.init 31 (fun i -> i * 2 + 1)
    // should be 32, but last one overflows on sum step

oddBitLengths
|> Seq.map createCandidate
|> Seq.filter isPerfect
|> Seq.iter (fun i ->
    printfn "%20i %s" i (Convert.ToString(i, 2))
)
//                   1 1
//                   6 110
//                  28 11100
//                 496 111110000
//                8128 1111111000000
//            33550336 1111111111111000000000000
//          8589869056 111111111111111110000000000000000
//        137438691328 1111111111111111111000000000000000000
// 2305843008139952128 1111111111111111111111111111111000000000000000000000000000000

To filter the numbers down to just likely candidates, I am using @nektro 's observation. I first generate a limited list of possible candidates that fit in a 64 bit integer, then filter down to only perfect ones. It takes 40s or so to run, but all of that time is spent between the last and next-to-last result.

[Guillaume Martigny]

How much time did this script took to run ? You approach is really nice, but I'm worried by |> Seq.filter isPerfect perf.

[Kasey Speakman]

Runtime is about 40 seconds in Release mode. The largest cost is finding divisors. I used the least expensive algorithm I could find. But it is still expensive. So to get the runtime down that low, I optimize down the number of inputs using nektro’s observation.

[Guillaume Martigny]

You could gain a little by only generating prime numbers for your candidates. Eratosthenes' sieve is not that hard to implement.

[Kasey Speakman]

I will post another solution using primes. Thanks for the tip!

[Kasey Speakman]

I posted the prime-based solution here. The actual perfect number calculation time is now negligible, and the code can be a one-liner. But it requires being fed Mersenne Exponents. Fortunately, very few/small Mersenne Exponents quickly turn into perfect numbers which are too large for traditional memory structures.