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!

loading...

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!

Sai gowtham -

Davide Santangelo -

Geoff Davis -

Ben Halpern -

## Discussion

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`

.Well, here goes my Haskell version. Enjoy!

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

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

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)

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.

Local can be short, may be r is better.

Clear and ASAP.