Inspired by this tweet:

Write a script to find "Perfect Numbers." Here's the list of numbers up to 19 digits 😈:

6, 28, 496, 8138, 33550336, 8589869056, 137438691328, 2305843008139952128

Look forward to seeing everyone's solutions!

Inspired by this tweet:

Write a script to find "Perfect Numbers." Here's the list of numbers up to 19 digits 😈:

6, 28, 496, 8138, 33550336, 8589869056, 137438691328, 2305843008139952128

Look forward to seeing everyone's solutions!

For further actions, you may consider blocking this person and/or reporting abuse

Dulanjana Lakmal -

Techelopment -

NAVODYA BUDDHIKA -

Joan Peramás Ceras -

## Top comments (39)

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.

Yeah, I had a suspicion that there's a geometric solution to finding perfect numbers and was trying to formulate it in my head. Putting it in base2 makes it quite clear. Hm... 🤔

Another interesting observation. In the binary form of each perfect number, the count of leading 1s is a prime number. In fact, they are all Mersenne Exponents.

I wrote this script 3 years ago.

Translate yours in Ruby.

In JS, not so good cause I'm new to JS. If any good writing comment please.

Do you have a better version for Go?

How efficient do you remember this article being?

F#

Usage

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.

How much time did this script took to run ? You approach is really nice, but I'm worried by

`|> Seq.filter isPerfect`

perf.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.

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

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

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.

First dumb "look at every integer" solution:

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.So I looked up this sequence on EOIS and luckily it found a match: "Numbers n such that 2

^{n+1}- 1 is prime".Which lead to this

way morepowerful script: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)

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. 😉

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

Thanks a lot !

👏👏👏👏👏👏

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

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.

Inspired from programming-algorithms.net/article...

Takes less than 1sec to get to 137438691328 but can't find easily 2305843008139952128

site is great for algo, thanks.

Here's my solution in C

I think you can reduce the number of iterations by using “ while (i <=n/2)”.

You can reduce it even further by using "while (i <= sqrt(n))" and noticing that divisors come in pairs, for example: if 16 / 2 = 8, both 2 and 8 are divisors of 16. There is no need to go up to 8 and check all integers up until that point, you only need to perform the division.

A (lazy but slow) Python solution which hasn't even yielded 33550336 in 5 minutes, despite a subtle optimization allowing to find divisors in

`O(√n)`

… Probably could use some optimization to prevent trying all possible integers. :-)Working on getting better at Clojure so thought I'd give it a shot.

F#, ridiculously short/fast solution

Usage

This runs in 0.35ms or ~3500 ticks in Release mode (after a JIT prerun). It basically turns the problem around to be just a matter of inputting Mersenne Exponents. Not many are needed before overflowing traditional memory structures like

`int64`

.