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

View post

Replies for: My solution in javascript. Time taken to get the 7th number which is 8 digits long is 8 milliseconds. Time taken to get the 8th number which is 19...

Nov 15

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)