Proper divisors

The proper divisors of a positive integer N are those numbers, other than N itself, that divide N without remainder.
For N > 1 they will always include 1, but for N == 1 their are no proper divisors.

For example the proper divisors of 6 are 1, 2, and 3. The proper divisors of 100 are 1, 2, 4, 5, 10, 20, 25, and 50.

Task

Create a routine to generate all the proper divisors of a number.
use it to show the proper divisors of the numbers 1 to 10 inclusive.
Find a number in the range 1 to 20,000 with the most proper divisors. Show the number and just the count of how many proper divisors it has.

Show all output here.

Cf.

D

Translation of: Python

Currently the lambda of the filter allocates a closure on the GC-managed heap. <lang d>void main() /*@safe*/ {

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

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

   iota(1, 11).map!properDivs.writeln;
   iota(1, 20_001).map!(n => tuple(properDivs(n).count, n)).reduce!max.writeln;

}</lang>

Output:

[[], [1], [1], [1, 2], [1], [1, 2, 3], [1], [1, 2, 4], [1, 3], [1, 2, 5]]
Tuple!(uint, int)(79, 18480)

The Run-time is about 0.67 seconds with the ldc2 compiler.

J

The proper divisors of an integer are the Factors of an integer without the integer itself.

So, borrowing from the J implementation of that related task:

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

Proper divisors of numbers 1 through 10:

<lang J> (,&": ' -- ' ,&": properDivisors)&>1+i.10 1 -- 2 -- 1 3 -- 1 4 -- 1 2 5 -- 1 6 -- 1 2 3 7 -- 1 8 -- 1 2 4 9 -- 1 3 10 -- 1 2 5</lang>

Number(s) not exceeding 20000 with largest number of proper divisors (and the count of those divisors):

<lang J> (, #@properDivisors)&> 1+I.(= >./) #@properDivisors@> 1+i.20000 15120 79 18480 79</lang>

Note that it's more efficient to simply count factors here, when selecting the candidate numbers.

<lang J> (, #@properDivisors)&> 1+I.(= >./) #@factors@> 1+i.20000 15120 79 18480 79</lang>

We could also arbitrarily toss either 15120 or 18480, if that were important.

Java

Works with: Java version 1.5+

<lang java5>import java.util.Collections; import java.util.LinkedList; import java.util.List;

public class Proper{

   public static List<Integer> properDivs(int n){
       List<Integer> divs = new LinkedList<Integer>();
       if(n == 1) return divs;
       divs.add(1);
       for(int x = 2; x < n; x++){
           if(n % x == 0) divs.add(x);
       }
       
       Collections.sort(divs);
       
       return divs;
   }
   
   public static void main(String[] args){
       for(int x = 1; x <= 10; x++){
           System.out.println(x + ": " + properDivs(x));
       }
       
       int x = 0, count = 0;
       for(int n = 1; n <= 20000; n++){
           if(properDivs(n).size() > count){
               x = n;
               count = properDivs(n).size();
           }
       }
       System.out.println(x + ": " + count);
   }

}</lang>

Output:

1: []
2: [1]
3: [1]
4: [1, 2]
5: [1]
6: [1, 2, 3]
7: [1]
8: [1, 2, 4]
9: [1, 3]
10: [1, 2, 5]
15120: 79

Perl

Using a module for divisors

Library: ntheory

<lang perl>use ntheory qw/divisors/; sub proper_divisors {

 my $n = shift;
 # Like Pari/GP, divisors(0) = (0,1) and divisors(1) = ()
 return 1 if $n == 0;
 my @d = divisors($n);
 pop @d;  # divisors are in sorted order, so last entry is the input
 @d;

} say "$_: ", join " ", proper_divisors($_) for 1..10;

1. For the max, we can do a traditional loop.

my($max,$ind) = (0,0); for (1..20000) {

 my $nd = scalar proper_divisors($_);
($max,$ind) = ($nd,$_) if $nd > $max;

} say "$max $ind";

2. Or we can use List::Util's max with decoration (this exploits its implementation)

{

 use List::Util qw/max/;
 no warnings 'numeric';
 say max(map { scalar(proper_divisors($_)) . " $_" } 1..20000);

}</lang>

Output:

Note that the first code will choose the first max, while the second chooses the last.

PL/I

<lang pli>*process source xref;

(subrg):
cpd: 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);
Dcl hi      Bin Fixed(31) Init(0);
Dcl (xl(10),xi) Bin Fixed(31);
Dcl i       Bin Fixed(31);
Do x=1 To 10;
  Call proper_divisors(x,pd,npd);
  Put Edit(x,' -> ',(pd(i) Do i=1 To npd))(Skip,f(2),a,10(f(2)));
  End;
xi=0;
Do x=1 To 20000;
  Call proper_divisors(x,pd,npd);
  Select;
    When(npd>hi) Do;
      xi=1;
      xl(1)=x;
      hi=npd;
      End;
    When(npd=hi) Do;
      xi+=1;
      xl(xi)=x;
      End;
    Otherwise;
    End;
  End;
Put Edit(hi,' -> ',(xl(i) Do i=1 To xi))(Skip,f(3),a,10(f(6)));

x= 166320; Call proper_divisors(x,pd,npd);
Put Edit(x,' -> ',npd)(Skip,f(8),a,f(4));
x=1441440; Call proper_divisors(x,pd,npd);
Put Edit(x,' -> ',npd)(Skip,f(8),a,f(4));

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;

End;</lang>

Output:

 1 ->
 2 ->  1
 3 ->  1
 4 ->  1 2
 5 ->  1
 6 ->  1 2 3
 7 ->  1
 8 ->  1 2 4
 9 ->  1 3
10 ->  1 2 5
 79 ->  15120 18480
  166320 ->  159
 1441440 ->  287
 0.530 seconds elapsed

A very literal interpretation <lang python>>>> def proper_divs2(n): ... return {x for x in range(1, (n + 1) // 2 + 1) if n % x == 0 and n != x} ... >>> [proper_divs2(n) for n in range(1, 11)] [set(), {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}, {1, 3}, {1, 2, 5}] >>> >>> n, length = max(((n, len(proper_divs2(n))) for n in range(1, 20001)), key=lambda pd: pd[1]) >>> n 15120 >>> length 79 >>> </lang>

Python: From prime factors

I found a reference on how to generate factors from all the prime factors and the number of times each prime factor goes into N - its multiplicity.

For example, given N having prime factors P(i) with associated multiplicity M(i}) then the factors are given by:

for m[0] in range(M(0) + 1):
    for m[1] in range(M[1] + 1):
        ...
                for m[i - 1] in range(M[i - 1] + 1):
                    mult = 1
                    for j in range(i):
                        mult *= P[j] ** m[j]
                    yield mult

This version is over an order of magnitude faster for generating the proper divisors of the first 20,000 integers; at the expense of simplicity. <lang python>from math import sqrt from functools import lru_cache, reduce from collections import Counter from itertools import product

MUL = int.__mul__

def prime_factors(n):

   'Map prime factors to their multiplicity for n'
   d = _divs(n)
   d = [] if d == [n] else (d[:-1] if d[-1] == d else d)
   pf = Counter(d)
   return dict(pf)

@lru_cache(maxsize=None) def _divs(n):

   'Memoized recursive function returning prime factors of n as a list'
   for i in range(2, int(sqrt(n)+1)):
       d, m  = divmod(n, i)
       if not m:
           return [i] + _divs(d)
   return [n]

def proper_divs(n):

   Return the set of proper divisors of n.
   pf = prime_factors(n)
   pfactors, occurrences = pf.keys(), pf.values()
   multiplicities = product(*(range(oc + 1) for oc in occurrences))
   divs = {reduce(MUL, (pf**m for pf, m in zip(pfactors, multis)), 1)
           for multis in multiplicities}
   try:
       divs.remove(n)
   except KeyError:
       pass
   return divs or ({1} if n != 1 else set())

if __name__ == '__main__':

   rangemax = 20000
   
   print([proper_divs(n) for n in range(1, 11)])
   print(*max(((n, len(proper_divs(n))) for n in range(1, 20001)), key=lambda pd: pd[1]))</lang>

Output:

[set(), {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}, {1, 3}, {1, 2, 5}]
15120 79

Racket

Module main will only be executed when this file is executed. When used as a library, it will not be used. <lang racket>#lang racket/base (provide fold-divisors ; name as per "Abundant..."

        proper-divisors)

(define (fold-divisors v n k0 kons)

 (define n1 (add1 n))
 (cond
   [(>= n1 (vector-length v))
    (define rv (make-vector n1 k0))
    (for* ((n (in-range 1 n1)) (m (in-range (* 2 n) n1 n)))
      (vector-set! rv m (kons n (vector-ref rv m))))
    rv]
   [else v]))

(define proper-divisors

 (let ((p.d-v (vector)))
   (λ (n)
     (set! p.d-v (fold-divisors p.d-v n null cons))
     (vector-ref p.d-v n))))

(module+ main

 (for ((n (in-range 1 (add1 10))))
   (printf "proper divisors of: ~a\t~a~%" n (proper-divisors n)))
 
 (define count-proper-divisors
   (let ((p.d-v (vector)))
     (λ (n)
       (set! p.d-v (fold-divisors p.d-v n 0 (λ (d n) (add1 n))))
       (vector-ref p.d-v n))))
 
 (void (count-proper-divisors 20000))
 
 (define-values
   (C I)
   (for*/fold ((C 0) (I 1))
   ((i (in-range 1 (add1 20000)))
    (c (in-value (count-proper-divisors i)))
    #:when (> c C))
   (values c i)))
 (printf "~a has ~a proper divisors~%" C I))</lang>

Output:

proper divisors of: 1	()
proper divisors of: 2	(1)
proper divisors of: 3	(1)
proper divisors of: 4	(2 1)
proper divisors of: 5	(1)
proper divisors of: 6	(3 2 1)
proper divisors of: 7	(1)
proper divisors of: 8	(4 2 1)
proper divisors of: 9	(3 1)
proper divisors of: 10	(5 2 1)
79 has 15120 proper divisors

REXX

<lang rexx>Call time 'R' Do x=1 To 10

 Say x '->' proper_divisors(x)
 End

hi=1 Do x=1 To 20000

 /* If x//1000=0 Then Say x */
 npd=count_proper_divisors(x)
 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 hi '->' list.hi

Say ' 166320 ->' count_proper_divisors(166320) Say '1441440 ->' count_proper_divisors(1441440)

Say time('E') 'seconds elapsed' Exit

proper_divisors: Procedure Parse Arg n If n=1 Then Return pd= /* Optimization reduces 37 seconds to 28 seconds */ 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)

count_proper_divisors: Procedure Parse Arg n Return words(proper_divisors(n))</lang>

Output:

1 ->
2 -> 1
3 -> 1
4 -> 1 2
5 -> 1
6 -> 1 2 3
7 -> 1
8 -> 1 2 4
9 -> 1 3
10 -> 1 2 5
79 -> 15120 18480
 166320 -> 159
1441440 -> 287
28.342000 seconds elapsed

Ruby

<lang ruby> require "prime"

class Integer

 def proper_divisors
   return [] if self == 1
   res = [1]
   primes = prime_division.flat_map{|prime, freq| Array.new(freq, prime)}
   (1..primes.size-1).each do |n|
     primes.combination(n).map{|combi| res << combi.inject(:*)}
   end
   res.flatten.uniq
 end

end

p (1..10).map{|n| n.proper_divisors}

max = (1..20_000).max_by{|n| n.proper_divisors.size} puts "#{max} has #{max.proper_divisors.size} divisors" </lang>

Output:

[[], [1], [1], [1, 2], [1], [1, 2, 3], [1], [1, 2, 4], [1, 3], [1, 2, 5]]
15120 has 79 divisors

An Alternative Approach

Determine the integer within a range of integers that has the most proper divisors
Nigel Galloway: December 23rd., 2014

require "prime" n, g = 0 (1..20000).each{|i| e = i.prime_division().inject(1){|n,g| n*=g[1]+1}

                   n, g = e, i if e > n}

puts "#{g} has #{n-1} proper divisors" </lang>

Output:

In the range 1..200000

15120 has 79 proper divisors

and in the ranges 1..2000000 & 1..20000000

166320 has 159 proper divisors
1441440 has 287 proper divisors

Tcl

Note that if a number, $k$ , greater than 1 divides $n$ exactly, both $k$ and $n/k$ are proper divisors. (The raw answers are not sorted; the pretty-printer code sorts.) <lang tcl>proc properDivisors {n} {

   if {$n == 1} return
   set divs 1
   for {set i 2} {$i*$i <= $n} {incr i} {

if {!($n % $i)} { lappend divs $i if {$i*$i < $n} { lappend divs [expr {$n / $i}] } }

   }
   return $divs

}

for {set i 1} {$i <= 10} {incr i} {

   puts "$i => {[join [lsort -int [properDivisors $i]] ,]}"

} set maxI [set maxC 0] for {set i 1} {$i <= 20000} {incr i} {

   set c [llength [properDivisors $i]]
   if {$c > $maxC} {

set maxI $i set maxC $c

} puts "max: $maxI => (...$maxC…)"</lang>

Output:

1 => {}
2 => {1}
3 => {1}
4 => {1,2}
5 => {1}
6 => {1,2,3}
7 => {1}
8 => {1,2,4}
9 => {1,3}
10 => {1,2,5}
max: 15120 => (...79...)

zkl

Translation of: D

<lang zkl>fcn properDivs(n){ [1.. (n + 1)/2 + 1].filter('wrap(x){ n%x==0 and n!=x }) } [1..10].apply(properDivs).println(); [1..20_001].apply('wrap(n){ T(properDivs(n).len(),n) })

  .reduce(fcn([(a,_)]ab, [(c,_)]cd){ a>c and ab or cd },T(0,0))
  .println();</lang>

Output:

L(L(),L(1),L(1),L(1,2),L(1),L(1,2,3),L(1),L(1,2,4),L(1,3),L(1,2,5))
L(79,18480)

Using a module for divisors

Python: Literal

Python: From prime factors

An Alternative Approach