Perfect numbers: Difference between revisions
m →[[Perfect Numbers#ALGOL 68]]: (2ⁿ-1) × 2ⁿ ÷ 2 |
m Fixed up LL method formula |
||
Line 3: | Line 3: | ||
A number is perfect if the sum of its factors is equal to twice the number. An equivalent condition is that <tt>n</tt> is perfect if the sum of <tt>n</tt>'s factors that are less than <tt>n</tt> is equal to <tt>n</tt>. |
A number is perfect if the sum of its factors is equal to twice the number. An equivalent condition is that <tt>n</tt> is perfect if the sum of <tt>n</tt>'s factors that are less than <tt>n</tt> is equal to <tt>n</tt>. |
||
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 |
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 (2<sup>n</sup> - 1) × 2<sup>n - 1</sup>. It is not known if there are any odd perfect numbers. |
||
=={{header|Ada}}== |
=={{header|Ada}}== |
Revision as of 16:36, 24 August 2008
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
<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; </Ada>
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
<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</qbasic>
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
<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; }</java> Or for arbitrary precision: <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; }</java>
Python
<python>def perf(n):
sum = 0 for i in xrange(1,n): if n % i == 0: sum += i return sum == n</python>
Using functional form <python>def perf(n):
return n == sum( i for i in xrange(1,n) if n % i == 0)</python>