Abundant, deficient and perfect number classifications: Difference between revisions

Content added Content deleted

Inline

Revision as of 18:46, 10 February 2015

These define three classifications of positive integers based on their proper divisors.

Let P(n) be the sum of the proper divisors of n, where the proper divisors of n are all positive divisors of n other than n itself.

if P(n) < n then n is classed as deficient (OEIS A005100).
if P(n) == n then n is classed as perfect (OEIS A000396).
if P(n) > n then n is classed as abundant (OEIS A005101).

Example: 6 has proper divisors 1, 2, and 3. 1 + 2 + 3 = 6 so 6 is classed as a perfect number.

Task

Calculate how many of the integers 1 to 20,000 inclusive are in each of the three classes and show the result here.

Cf.

Aliquot sequence classifications. (The whole series from which this task is a subset).
Proper divisors
Amicable pairs
Numbers and Mysticism

AutoHotkey

<lang autohotkey>Loop {

   m := A_index
   ; getting factors=====================
   loop % floor(sqrt(m))
   {
       if ( mod(m, A_index) == "0" )
       {
           if ( A_index ** 2 == m )
           {
               list .= A_index . ":"
               sum := sum + A_index
               continue
           }
           if ( A_index != 1 )
           {
               list .= A_index . ":" . m//A_index . ":"
               sum := sum + A_index + m//A_index
           }
           if ( A_index == "1" )
           {
               list .= A_index . ":"
               sum := sum + A_index
           }
       }
   }
   ; Factors obtained above===============
   if ( sum == m ) && ( sum != 1 )
   {
       result := "perfect"
       perfect++
   }
   if ( sum > m )
   {
       result := "Abundant"
       Abundant++
   }
   if ( sum < m ) or ( m == "1" )
   {
       result := "Deficient"
       Deficient++
   }
   if ( m == 20000 )	
   {
       MsgBox % "number: " . m . "`nFactors:`n" . list . "`nSum of Factors: " . Sum . "`nResult: " . result . "`n_______________________`nTotals up to: " . m . "`nPerfect: " . perfect . "`nAbundant: " . Abundant . "`nDeficient: " . Deficient 
       ExitApp
   }
   list := ""
   sum := 0

}

esc::ExitApp </lang>

Output:

number: 20000
Factors:
1:2:10000:4:5000:5:4000:8:2500:10:2000:16:1250:20:1000:25:800:32:625:40:500:50:400:80:250:100:200:125:160:
Sum of Factors: 29203
Result: Abundant
_______________________
Totals up to: 20000
Perfect: 4
Abundant: 4953
Deficient: 15043

D

<lang d>void main() /*@safe*/ {

   import std.stdio, std.algorithm, std.range;

   static immutable properDivs = (in uint n) pure nothrow @safe /*@nogc*/ =>
       iota(1, (n + 1) / 2 + 1).filter!(x => n % x == 0 && n != x);

   enum Class { deficient, perfect, abundant }

   static Class classify(in uint n) pure nothrow @safe /*@nogc*/ {
       immutable p = properDivs(n).sum;
       with (Class)
           return (p < n) ? deficient : ((p == n) ? perfect : abundant);
   }

   enum rangeMax = 20_000;
   //iota(1, 1 + rangeMax).map!classify.hashGroup.writeln;
   iota(1, 1 + rangeMax).map!classify.array.sort().group.writeln;

}</lang>

Output:

[Tuple!(Class, uint)(deficient, 15043), Tuple!(Class, uint)(perfect, 4), Tuple!(Class, uint)(abundant, 4953)]

J

Supporting implementation:

<lang J>factors=: [: /:~@, */&>@{@((^ i.@>:)&.>/)@q:~&__ properDivisors=: factors -. ]</lang>

We can subtract the sum of a number's proper divisors from itself to classify the number:

<lang J> (- +/@properDivisors&>) 1+i.10 1 1 2 1 4 0 6 1 5 2</lang>

Except, we are only concerned with the sign of this difference:

<lang J> *(- +/@properDivisors&>) 1+i.30 1 1 1 1 1 0 1 1 1 1 1 _1 1 1 1 1 1 _1 1 _1 1 1 1 _1 1 1 1 0 1 _1</lang>

Also, we do not care about the individual classification but only about how many numbers fall in each category:

<lang J> #/.~ *(- +/@properDivisors&>) 1+i.20000 15043 4 4953</lang>

So: 15043 deficient, 4 perfect and 4953 abundant numbers in this range.

How do we know which is which? We look at the unique values (which are arranged by their first appearance, scanning the list left to right):

<lang J> ~. *(- +/@properDivisors&>) 1+i.20000 1 0 _1</lang>

The sign of the difference is negative for the abundant case - where the sum is greater than the number. And we rely on order being preserved in sequences (this happens to be a fundamental property of computer memory, also).

Perl

Using a module

Library: ntheory

We can use the <=> operator to return a comparison of -1, 0, or 1, which classifies the results. Let's look at the values from 1 to 30: <lang perl>use ntheory qw/divisor_sum/; say join " ", map { divisor_sum($_)-$_ <=> $_ } 1..30;</lang>

Output:

-1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 1 -1 -1 -1 -1 -1 1 -1 1 -1 -1 -1 1 -1 -1 -1 0 -1 1

We can see 6 is the first perfect number, 12 is the first abundant number, and 1 is classified as a deficient number.

Showing the totals for the first 20k numbers: <lang perl>use ntheory qw/divisor_sum/; my %h; $h{divisor_sum($_)-$_ <=> $_}++ for 1..20000; say "Perfect: $h{0} Deficient: $h{-1} Abundant: $h{1}";</lang>

Output:

Perfect: 4    Deficient: 15043    Abundant: 4953

PL/I

<lang pli>*process source xref;

apd: Proc Options(main);
p9a=time();
Dcl (p9a,p9b) Pic'(9)9';
Dcl cnt(3) Bin Fixed(31) Init((3)0);
Dcl x Bin Fixed(31);
Dcl pd(300) Bin Fixed(31);
Dcl sumpd   Bin Fixed(31);
Dcl npd     Bin Fixed(31);
Do x=1 To 20000;
  Call proper_divisors(x,pd,npd);
  sumpd=sum(pd,npd);
  Select;
    When(x<sumpd) cnt(1)+=1; /* abundant  */
    When(x=sumpd) cnt(2)+=1; /* perfect   */
    Otherwise     cnt(3)+=1; /* deficient */
    End;
  End;

Put Edit('In the range 1 - 20000')(Skip,a);
Put Edit(cnt(1),' numbers are abundant ')(Skip,f(5),a);
Put Edit(cnt(2),' numbers are perfect  ')(Skip,f(5),a);
Put Edit(cnt(3),' numbers are deficient')(Skip,f(5),a);
p9b=time();
Put Edit((p9b-p9a)/1000,' seconds elapsed')(Skip,f(6,3),a);
Return;

proper_divisors: Proc(n,pd,npd);
Dcl (n,pd(300),npd) Bin Fixed(31);
Dcl (d,delta)       Bin Fixed(31);
npd=0;
If n>1 Then Do;
  If mod(n,2)=1 Then  /* odd number  */
    delta=2;
  Else                /* even number */
    delta=1;
  Do d=1 To n/2 By delta;
    If mod(n,d)=0 Then Do;
      npd+=1;
      pd(npd)=d;
      End;
    End;
  End;
End;

sum: Proc(pd,npd) Returns(Bin Fixed(31));
Dcl (pd(300),npd) Bin Fixed(31);
Dcl sum Bin Fixed(31) Init(0);
Dcl i   Bin Fixed(31);
Do i=1 To npd;
  sum+=pd(i);
  End;
Return(sum);
End;

End;</lang>

Output:

In the range 1 - 20000
 4953 numbers are abundant
    4 numbers are perfect
15043 numbers are deficient
 0.560 seconds elapsed

Python

Importing Proper divisors from prime factors: <lang python>>>> from proper_divisors import proper_divs >>> from collections import Counter >>> >>> rangemax = 20000 >>> >>> def pdsum(n): ... return sum(proper_divs(n)) ... >>> def classify(n, p): ... return 'perfect' if n == p else 'abundant' if p > n else 'deficient' ... >>> classes = Counter(classify(n, pdsum(n)) for n in range(1, 1 + rangemax)) >>> classes.most_common() [('deficient', 15043), ('abundant', 4953), ('perfect', 4)] >>> </lang>

Racket

Since we need P from "sum-of-divisors.rkt" both here and in Amicable pairs, this is a common file.

<lang racket>;; Common code to "Amicable Pairs" and "Abundant, deficient and perfect number classifications"

lang racket/base

(provide P ; name as per "Abundant..."

        proper-divisors)

(require racket/fixnum

        (only-in math/number-theory divisors)
        (only-in racket/list drop-right))

(define v (fxvector))

(define (calc-n! n)

 (define n1 (add1 n))
 (when (>= n1 (fxvector-length v))
   (set! v (make-fxvector n1 0))
   (for* ((n (in-range 1 n1)) (m (in-range (* 2 n) n1 n)))
     (fxvector-set! v m (+ (fxvector-ref v m) n)))))

returns and memoises the sum of the divisors of n

(define P

 (λ (n)
   (when (>= n (fxvector-length v)) (calc-n! n))
   (fxvector-ref v n)))

divisors returns n as its last element, drop that for "proper"

(define (proper-divisors n)

 (drop-right (divisors n) 1))</lang>

Now we use import that file for our purposes: <lang racket>#lang racket (require "sum-of-divisors.rkt") (define SCOPE 20000) (define-values

 (a d p)
 (for/fold ((a 0) (d 0) (p 0))
           ((n (in-range SCOPE 0 -1))) ; doing this backwards initialises the memo
   (match (- (P n) n)
     [0             (values a d (add1 p))]    ; perfect
     [(? negative?) (values a (add1 d) p)]    ; deficient
     [(? positive?) (values (add1 a) d p)]))) ; abundant

(printf #<<EOS Between 1 and ~s:

 ~a abundant numbers
 ~a deficient numbers
 ~a perfect numbers

EOS

       SCOPE a d p)</lang>

Output:

Between 1 and 20000:
  4953 abundant numbers
  15043 deficient numbers
  4 perfect numbers

REXX

<lang rexx>Call time 'R' cnt.=0 Do x=1 To 20000

 pd=proper_divisors(x)
 sumpd=sum(pd)
 Select
   When x<sumpd Then cnt.abundant =cnt.abundant +1
   When x=sumpd Then cnt.perfect  =cnt.perfect  +1
   Otherwise         cnt.deficient=cnt.deficient+1
   End
 Select
   When npd>hi Then Do
     list.npd=x
     hi=npd
     End
   When npd=hi Then
     list.hi=list.hi x
   Otherwise
     Nop
   End
 End

Say 'In the range 1 - 20000' Say format(cnt.abundant ,5) 'numbers are abundant ' Say format(cnt.perfect ,5) 'numbers are perfect ' Say format(cnt.deficient,5) 'numbers are deficient ' Say time('E') 'seconds elapsed' Exit

proper_divisors: Procedure Parse Arg n Pd= If n=1 Then Return If n//2=1 Then /* odd number */

 delta=2

Else /* even number */

 delta=1

Do d=1 To n%2 By delta

 If n//d=0 Then
   pd=pd d
 End

Return space(pd)

sum: Procedure Parse Arg list sum=0 Do i=1 To words(list)

 sum=sum+word(list,i)
 End

Return sum</lang>

Output:

In the range 1 - 20000
 4953 numbers are abundant
    4 numbers are perfect
15043 numbers are deficient
28.392000 seconds elapsed

Ruby

With proper_divisors#Ruby in place: <lang ruby>res = Hash.new(0) (1 .. 20_000).each{|n| res[n.proper_divisors.inject(0, :+) <=> n] += 1} puts "Deficient: #{res[-1]} Perfect: #{res[0]} Abundant: #{res[1]}" </lang>

Output:

Deficient: 15043 Perfect: 4 Abundant: 4953

Scala

<lang Scala>def properDivisors(n: Int) = (1 to n/2).filter(i => n % i == 0) def classifier(i: Int) = properDivisors(i).sum compare i val groups = (1 to 20000).groupBy( classifier ) println("Deficient: " + groups(-1).length) println("Abundant: " + groups(1).length) println("Perfect: " + groups(0).length + " (" + groups(0).mkString(",") + ")")</lang>

Output:

Deficient: 15043
Abundant: 4953
Perfect: 4 (6,28,496,8128)

VBScript

<lang VBScript>Deficient = 0 Perfect = 0 Abundant = 0 For i = 1 To 20000 sum = 0 For n = 1 To 20000 If n < i Then If i Mod n = 0 Then sum = sum + n End If End If Next If sum < i Then Deficient = Deficient + 1 ElseIf sum = i Then Perfect = Perfect + 1 ElseIf sum > i Then Abundant = Abundant + 1 End If Next WScript.Echo "Deficient = " & Deficient & vbCrLf &_ "Perfect = " & Perfect & vbCrLf &_ "Abundant = " & Abundant</lang>

Output:

Deficient = 15043
Perfect = 4
Abundant = 4953

zkl

Translation of: D

<lang zkl>fcn properDivs(n){ [1.. (n + 1)/2 + 1].filter('wrap(x){ n%x==0 and n!=x }) }

fcn classify(n){

  p:=properDivs(n).sum();
  return(if(p<n) -1 else if(p==n) 0 else 1);

}

const rangeMax=20_000; classified:=[1..rangeMax].apply(classify); perfect :=classified.filter('==(0)).len(); abundant :=classified.filter('==(1)).len(); println("Deficient=%d, perfect=%d, abundant=%d".fmt(

  classified.len()-perfect-abundant, perfect, abundant));</lang>

Output:

Deficient=15043, perfect=4, abundant=4953