2
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Please clarify: What is a non-standard library? Also, how should output be given? \$\endgroup\$
    – isaacg
    Commented May 7, 2015 at 6:09
  • \$\begingroup\$ Related. \$\endgroup\$
    – Martin Ender
    Commented May 7, 2015 at 7:25

3 Answers 3

Reset to default
2
\$\begingroup\$

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)
Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ This answer will skip odd perfect numbers. \$\endgroup\$
    – orlp
    Commented May 7, 2015 at 5:38
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Does prime factorization using P speed anything up? \$\endgroup\$
    – orlp
    Commented May 7, 2015 at 3:41
  • \$\begingroup\$ @orlp possibly, but we want all factors, not primes. \$\endgroup\$
    – Maltysen
    Commented May 7, 2015 at 20:37
  • \$\begingroup\$ I'm aware, but you can compute the sigma function from the factorization. \$\endgroup\$
    – orlp
    Commented May 8, 2015 at 3:54

Not the answer you're looking for? Browse other questions tagged or ask your own question.