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

[Guillaume Martigny]

First dumb "look at every integer" solution:

const range = n => (new Array(+n)).fill().map((_, i) => i + 1);
return range(limit).filter((n) => {
    return range(Math.ceil(n ** 0.5))
        .filter(d => n % d === 0)
        .reduce((acc, val) => acc + val + (n / val), 0) / 2 === n;
});

This algo has trouble going further than 1e6.

Then, I dig your hypothesis that all Perfect number are in the form (n+1)"1"..(n)"0" in base 2. I needed to find the logical sequence of valid n.

[6, 28, 496, 8128, 33550336, 8589869056, 137438691328].map(n => n.toString(2).match(/0/g).length);
// => [1, 2, 4, 6, 12, 16, 18]

So I looked up this sequence on EOIS and luckily it found a match: "Numbers n such that 2ⁿ⁺¹ - 1 is prime".

Which lead to this way more powerful script:

const range = n => (new Array(+n)).fill().map((_, i) => i + 1);
const isPrime = (n) => {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;
    for (let i = 5, l = n ** 0.5; i <= l; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }
    return true;
};
return range(limit).filter(n => isPrime(2 ** (n + 1) - 1)).map((n) => {
    return parseInt("1".repeat(n + 1) + "0".repeat(n), 2);
});

This time, it can't go any higher than 1e3 before crashing, but yield more results. (However, JS precision let me down on the last result)

[Shi Ling]

Came to a same thesis and worked out a similar solution. Also ran into the limits at the 9th perfect number. But JavaScript now supports native BigInt (only in Chrome and I believe newer versions of NodeJs though!). Now we just need a way to generate large prime numbers fast to generate perfect numbers. 😉

[Guillaume Martigny]

Yeah, I liked that we came with two solution from the same hypothesis.

I'm looking into BigInt (thanks a lot I didn't know !) and it looks promising.

[Guillaume Martigny]

Thanks to your input on BigInt, I made a new solution.
Thanks a lot !

[Shi Ling]

👏👏👏👏👏👏

I feel a heart is not enough. I'm so happy to see the new version.