# Write a script to find "Perfect Numbers"

### Peter Kim Frank Nov 13 '18 ใป1 min read

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!

Classic DEV Post from Jan 16

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.

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.

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... ๐ค

I wrote this script 3 years ago.

Translate yours in Ruby.

What do you do with a holy lot of time you saved by writing

`resu`

instead of`result`

?:)

Local can be short, may be r is better.

Clear and ASAP.

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?

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

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.

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.

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.

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.

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.

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. :-)Well, here goes my Haskell version. Enjoy!

A very minor tweak. i-1 doesn't require parentheses in this case.

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`

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

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.

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.Still waiting.

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

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)

I

kind ofgot crazy with this challenge. After a day at refining my solution, I end up with a pretty efficient solution. The script is able to find the 18th perfect number under 14s on my computer.Since the solution is a bit long and require some explanations, I wrote everything on a gist.

If anyone found a way to reduce computations, I would greatly appreciate.

This is incredible. You should consider converting your gist into a DEV article!

Yes, I'm so proud of the result. But in the end, this is nothing more than small bits gathered from the Internet. I don't see an article out of this.

If you (or any one else reading this) want to use this resource for an article, feel free to do so. ;)

You're...

notexpecting fast implementations, are you? ๐คจUnless you consider scraping a web page to get them. There are just 50 known perfect numbers...

Going beyond the set of currently known perfect numbers is extra credit. But no - any old method will do, fast or slow or limited to just the first few in the list. :)

It will be interesting to see what approach is most efficient for grabbing the first few.