Calculate the first n perfect numbers

2

Write a program that calculates the first n perfect numbers. A perfect number is one where the sum of the factors is the original number. For example, 6 is a perfect number because 1+2+3=6. No non standard libraries.The standard loopholes are forbidden.

Lucas

Posted 2015-05-07T01:55:46.420

Reputation: 665

Question was closed 2015-05-07T13:18:45.520

2Please clarify: What is a non-standard library? Also, how should output be given? – isaacg – 2015-05-07T06:09:22.593

Related. – Martin Ender – 2015-05-07T07:25:03.837

Answers

2

Pyth - 27 25 bytes

Extremely super slow brute force approach.

K2W<ZQ~K1IqKsf!%KTr1KK~Z1

Trial division to factor, then while loop till length of perfect numbers is enough.

Try it here online.

Maltysen

Posted 2015-05-07T01:55:46.420

Reputation: 25 023

Does prime factorization using P speed anything up? – orlp – 2015-05-07T03:41:24.840

@orlp possibly, but we want all factors, not primes. – Maltysen – 2015-05-07T20:37:00.883

I'm aware, but you can compute the sigma function from the factorization. – orlp – 2015-05-08T03:54:59.263

2

Pyth, 25 bytes

J1W<lYQy=JI!tPKtyJaY*JK;Y

Tests whether Mersenne numbers are prime. If so, it generates the corresponding perfect number. Can find the first 8 perfect numbers in under a second.

Note: Only generates even perfect numbers. However, since it has been proven that any odd perfect number is greater than 10^1500, this algorithm is correct on inputs up to 14.

Demonstration.

isaacg

Posted 2015-05-07T01:55:46.420

Reputation: 39 268

1This answer will skip odd perfect numbers. – orlp – 2015-05-07T05:38:24.410

2

CJam, 24 bytes

1{{2*_(mp!}g__(*2/p}ri*;

Try it online.

Makes use of the Euclid–Euler theorem:

An even number P is perfect iff P = 2 ** (N - 1) * (2 ** N - 1) where 2 ** N - 1 is prime.

Disclaimer

If there are odd perfect numbers, this code will fail to generate them. However, there are no known odd perfect numbers.

How it works

1                        e# A := 1
 {                 }ri*  e# do int(input()) times: 
  {       }g             e#   do:
   2*                    e#     A *= 2
     _(                  e#     M := A - 1
       mp!               e#   while(prime(P))
            __(2/        e#   P := A * (A - 1) / 2
                 p       e#   print(P)
                       ; e# discard(A)

Dennis

Posted 2015-05-07T01:55:46.420

Reputation: 196 637