Perfect numbers

From Rosetta Code
Revision as of 18:57, 14 March 2009 by rosettacode>Spoon! (added ocaml)
Task
Perfect numbers
You are encouraged to solve this task according to the task description, using any language you may know.
Write a function which says whether a number is perfect.

A number is perfect if the sum of its factors is equal to twice the number. An equivalent condition is that n is perfect if the sum of n's factors that are less than n is equal to n.

Note: The faster Lucas-Lehmer_test is used to find primes of the form 2ⁿ-1, all known perfect numbers can derived from these primes using the formula (2n - 1) × 2n - 1. It is not known if there are any odd perfect numbers.

Ada

<lang ada> function Is_Perfect(N : Positive) return Boolean is

  Sum : Natural := 0;

begin

  for I in 1..N - 1 loop
     if N mod I = 0 then
        Sum := Sum + I;
     end if;
  end loop;
  return Sum = N;

end Is_Perfect; </lang>

ALGOL 68

PROC is perfect = (INT candidate)BOOL: (
  INT sum :=1;
  FOR f1 FROM 2 TO ENTIER ( sqrt(candidate)*(1+2*small real) ) WHILE
    IF candidate MOD f1 = 0 THEN
      sum +:= f1;
      INT f2 = candidate OVER f1;
      IF f2 > f1 THEN
        sum +:= f2
      FI
    FI;
# WHILE # sum <= candidate DO 
    SKIP 
  OD;
  sum=candidate
);
# test #
FOR i FROM 2 TO 33550336 DO
  IF is perfect(i) THEN print((i, new line)) FI
OD

Output:

        +6
       +28
      +496
     +8128
 +33550336

BASIC

Works with: QuickBasic version 4.5

<lang qbasic>FUNCTION perf(n) sum = 0 for i = 1 to n - 1 IF n MOD i = 0 THEN sum = sum + i END IF NEXT i IF sum = n THEN perf = 1 ELSE perf = 0 END IF END FUNCTION</lang>

C

Based on the D version, for GCC: <lang c>

  1. include "stdio.h"
  2. include "math.h"

int perfect(int n) {

   int max = (int)sqrt((double)n) + 1;
   int tot = 1;
   int i;
   for (i = 2; i < max; i++)
       if (__builtin_expect((n % i) == 0, 1)) {
           tot += i;
           int q = n / i;
           if (q > i)
               tot += q;
       }
   return tot == n;

}

int main() {

   int n;
   for (n = 2; n < 33550337; n++)
       if (perfect(n))
           printf("%d\n", n);
   return 0;

} </lang>

D

Based on the Algol version: <lang d> import std.math: sqrt;

bool perfect(int n) {

   if (n < 2)
       return false;
   int max = cast(int)sqrt(cast(real)n) + 1;
   int tot = 1;
   for (int i = 2; i < max; i++)
       if (n % i == 0) {
           tot += i;
           int q = n / i;
           if (q > i)
               tot += q;
       }
   return tot == n;

}

void main() {

   for (int n; n < 33_550_337; n++)
       if (perfect(n))
           printf("%d\n", n);

} </lang>

Forth

: perfect? ( n -- ? )
  1
  over 2/ 1+ 2 ?do
    over i mod 0= if i + then
  loop
  = ;

Fortran

Works with: Fortran version 90 and later
FUNCTION isPerfect(n)
  LOGICAL :: isPerfect
  INTEGER, INTENT(IN) :: n
  INTEGER :: i, factorsum

  isPerfect = .FALSE.
  factorsum = 1
  DO i = 2, INT(SQRT(REAL(n)))
     IF(MOD(n, i) == 0) factorsum = factorsum + i + (n / i)
  END DO
  IF (factorsum == n) isPerfect = .TRUE.
END FUNCTION isPerfect

Haskell

perf n = n == sum [i | i <- [1..n-1], n `mod` i == 0]

J

is_perfect=: = [: +/ ((0=]|[)i.) # i.

The program defined above, like programs found here in other languages, assumes that the input will be a scalar positive integer.

Examples of use, including extensions beyond those assumptions:

   is_perfect 33550336
1
   }.I. is_perfect"0 i. 10000
6 28 496 8128

   ] zero_through_twentynine =. i. 3 10
 0  1  2  3  4  5  6  7  8  9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
   is_pos_int=: 0&< *. ]=>.
   (is_perfect"0 *. is_pos_int) zero_through_twentynine
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0

Java

<lang java>public static boolean perf(int n){ int sum= 0; for(int i= 1;i < n;i++){ if(n % i == 0){ sum+= i; } } return sum == n; }</lang> Or for arbitrary precision: <lang java>import java.math.BigInteger;

public static boolean perf(BigInteger n){ BigInteger sum= BigInteger.ZERO; for(BigInteger i= BigInteger.ONE; i.compareTo(n) < 0;i=i.add(BigInteger.ONE)){ if(n.mod(i).compareTo(BigInteger.ZERO) == 0){ sum= sum.add(i); } } return sum.compareTo(n) == 0; }</lang>

MAXScript

fn isPerfect n =
(
    local sum = 0
    for i in 1 to (n-1) do
    (
        if mod n i == 0 then
        (
            sum += i
        )
    )
    sum == n
)

OCaml

<lang ocaml>let perf n =

 let sum = ref 0 in
   for i = 1 to n-1 do
     if n mod i = 0 then
       sum := !sum + i
   done;
   !sum = n</lang>

Functional style: <lang ocaml>(* range operator *) let rec (--) a b =

 if a > b then
   []
 else
   a :: (a+1) -- b

let perf n = n = List.fold_left (+) 0 (List.filter (fun i -> n mod i = 0) (1 -- (n-1)))</lang>

Perl

<lang perl>sub perf {

   my $n = shift;
   my $sum = 0;
   foreach my $i (1..$n-1) {
       if ($n % $i == 0) {
           $sum += $i;
       }
   }
   return $sum == $n;

}</lang> Functional style: <lang perl>use List::Util qw(sum);

sub perf {

   my $n = shift;
   $n == sum(grep {$n % $_ == 0} 1..$n-1);

}</lang>

Python

<lang python>def perf(n):

   sum = 0
   for i in xrange(1, n):
       if n % i == 0:
           sum += i
   return sum == n</lang>

Functional style: <lang python>perf = lambda n: n == sum(i for i in xrange(1, n) if n % i == 0)</lang>

Ruby

<lang ruby>def perf(n)

   sum = 0
   for i in 1...n
       if n % i == 0
           sum += i
       end
   end
   return sum == n

end</lang> Functional style: <lang ruby>def perf(n)

   n == (1...n).select {|i| n % i == 0}.inject(0) {|sum, i| sum + i}

end</lang>

Scheme

<lang scheme>(define (perf n)

 (let loop ((i 1)
            (sum 0))
   (cond ((= i n)
          (= sum n))
         ((= 0 (modulo n i))
          (loop (+ i 1) (+ sum i)))
         (else
          (loop (+ i 1) sum)))))</lang>