Proper divisors

Proper divisors is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

1. Create a routine to generate all the proper divisors of a number.
2. use it to show the proper divisors of the numbers 1 to 10 inclusive.
3. 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.

• Amicable pairs
• Abundant, deficient and perfect number classifications

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 -. 1:</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. 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";

1. 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:

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
79 18480

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

Python

Python: Literal

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