DEV Community

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

View post
Collapse
 
shiling profile image
Shi Ling • • Edited

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 digits long is 2.6 seconds.
Still waiting for my results for the 9th number...

function isPerfect(num){
    let sum = 1 
    let max = num / 2
    for(var i = 2; i < max; i++){
        if(num % i === 0){
            sum += i // add lower divisor
            max = Math.floor(num / i)
            sum += max //add higher divisor
        }
    }
    return sum === num;
}

function getPerfectSeries(n = 5){ 

    let series = []

    // Create number in binary string
    let l = 1
    while(series.length < n){
        let s = "1"
        for(let i=0; i < l; i++){
            s += "1"
        }
        for(let i=0; i < l; i++){
            s += "0"
        }
        let num = parseInt(s,2) // convert to base10
        if(isPerfect(num)){
            series.push(num)
        }
        l++
    }

    console.log(series)

}

function timer(fn){
    let start = new Date();
    fn()
    let time = new Date().getTime() - start.getTime()
    console.log("Time taken: " + time + "ms")
}

timer(()=>{getPerfectSeries(1)}) // < 1ms
timer(()=>{getPerfectSeries(2)}) // < 1ms
timer(()=>{getPerfectSeries(3)}) // < 1ms
timer(()=>{getPerfectSeries(4)}) // < 1ms
timer(()=>{getPerfectSeries(5)}) // < 1ms
timer(()=>{getPerfectSeries(6)}) // 4ms
timer(()=>{getPerfectSeries(7)}) // 8ms
timer(()=>{getPerfectSeries(8)}) // 26.9 seconds

Anyway, this solution is inspired by @nektro 's observation of the perfect numbers - Had a suspicion that there's a geometric pattern to this which is obvious when you look like the perfect numbers is Base2.

nektro profile image Meghan 🌺
Nov 13 
const perfect = [6, 28, 496, 8128, 33550336, 8589869056, 137438691328, 
2305843008139952128];

perfect.map(v => v.toString(2));
/*
[ "110",
  "11100",
  "111110000",
  "1111111000000",
  "1111111111111000000000000",
  "111111111111111110000000000000000",
  "1111111111111111111000000000000000000",
  "1111111111111111111111111111111000000000000000000000000000000" ] */

perfect.map(v => v.toString(3));
/*
[ "20",
  "1001",
  "200101",
  "102011001",
  "2100010112102001",
  "211011122100120010101",
  "111010202100010220210001",
  "120100210022221112202020222210100212001" ] */

perfect.map(v => v.toString(4));
/*
[ "12",
  "130",
  "13300",
  "1333000",
  "1333333000000",
  "13333333300000000",
  "1333333333000000000",
  "1333333333333333000000000000000" ] */

I find base 2 and 4 particularly interesting because for each perfect number, the amount of 1s/3s and 0s is the same.

edit: fixed my sequence because 8138 is not perfect, its 8128.

Perfect numbers in binary always start with "1" followed by an equal number of "1" and "0"s.

I first generate plausible perfect numbers from binary strings first using this pattern, then converted them to Base10, before testing if it is a perfect number.

The isPerfect function can be optimised by reducing the loop to find the divisors by 1) adding both the lower and the higher divisor and 2) also setting the higher divisor as a limiter for iteration.

Collapse
 
shiling profile image
Shi Ling • • Edited

Results

Still waiting.

@picocreator - Wanna use GPU.js to speed this up?

Collapse
 
gmartigny profile image
Guillaume Martigny •
gmartigny profile image Guillaume Martigny
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 2n+1 - 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)