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.
- Amicable pairs
- Abundant, deficient and perfect number classifications
- Aliquot sequence classifications
- Factors of an integer
- Prime decomposition
AWK
<lang AWK>
- syntax: GAWK -f PROPER_DIVISORS.AWK
BEGIN {
show = 0 # show divisors: 0=no, 1=yes
print(" N cnt DIVISORS")
for (i=1; i<=20000; i++) {
divisors(i)
if (i <= 10 || i == 100) { # including 100 as it was an example in task description
printf("%5d %3d %s\n",i,Dcnt,Dstr)
}
if (Dcnt < max_cnt) {
continue
}
if (Dcnt > max_cnt) {
rec = ""
max_cnt = Dcnt
}
rec = sprintf("%s%5d %3d %s\n",rec,i,Dcnt,show?Dstr:"divisors not shown")
}
printf("%s",rec)
exit(0)
} function divisors(n, i) {
if (n == 1) {
Dcnt = 0
Dstr = ""
return
}
Dcnt = Dstr = 1
for (i=2; i<n; i++) {
if (n % i == 0) {
Dcnt++
Dstr = sprintf("%s %s",Dstr,i)
}
}
return
} </lang>
output:
N cnt DIVISORS
1 0
2 1 1
3 1 1
4 2 1 2
5 1 1
6 3 1 2 3
7 1 1
8 3 1 2 4
9 2 1 3
10 3 1 2 5
100 8 1 2 4 5 10 20 25 50
15120 79 divisors not shown
18480 79 divisors not shown
D
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.
Haskell
<lang Haskell>import Data.Ord import Data.List
divisors :: (Integral a) => a -> [a] divisors n = filter ((0 ==) . (n `mod`)) [1 .. (n `div` 2)]
main :: IO () main = do
putStrLn "divisors of 1 to 10:" mapM_ (print . divisors) [1 .. 10] putStrLn "a number with the most divisors within 1 to 20000 (number, count):" print $ maximumBy (comparing snd) [(n, length $ divisors n) | n <- [1 .. 20000]]</lang>
- Output:
divisors of 1 to 10: [] [1] [1] [1,2] [1] [1,2,3] [1] [1,2,4] [1,3] [1,2,5] a number with the most divisors within 1 to 20000 (number, count): (18480,79)
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
<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
jq
In the following, proper_divisors returns a stream. In order to count the number of items in the stream economically, we first define "count(stream)": <lang jq>def count(stream): reduce stream as $i (0; . + 1);
- unordered
def proper_divisors:
. as $n
| if $n > 1 then 1,
| range(2; 1 + (sqrt|floor)) as $i
| if ($n % $i) == 0 then $i,
(($n / $i) | if . == $i then empty else . end)
else empty end)
else empty end;
- The first integer in 1 .. n inclusive
- with the maximal number of proper divisors in that range:
def most_proper_divisors(n):
reduce range(1; n+1) as $i
( [null, 0];
count( $i | proper_divisors ) as $count
| if $count > .[1] then [$i, $count] else . end);</lang>
The tasks: <lang jq>"The proper divisors of the numbers 1 to 10 inclusive are:", (range(1;11) as $i | "\($i): \( [ $i | proper_divisors] )"), "", "The pair consisting of the least number in the range 1 to 20,000 with", "the maximal number proper divisors together with the corresponding", "count of proper divisors is:", most_proper_divisors(20000) </lang>
- Output:
<lang sh>$ jq -n -c -r -f /Users/peter/jq/proper_divisors.jq The proper divisors of the numbers 1 to 10 inclusive are: 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]
The pair consisting of the least number in the range 1 to 20,000 with the maximal number proper divisors together with the corresponding count of proper divisors is: [15120,79]</lang>
Perl
Mathematica / Wolfram Language
Proper divisors of n from 1 to 10 <lang Mathematica>Join[{{1, {}}}, Table[{n, Most@Divisors@n}, {n, 2, 10}]] // Grid</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}
Five numbers <=20000 with the most proper divisors <lang Mathematica>Join[[[:Template:N, count]], {#, Length@Most@Divisors@#} & /@
Ordering[Table[Length@Most@Divisors[n], {n, 20000}], -5]] // Grid</lang>
- Output:
n count 18720 71 18900 71 19800 71 15120 79 18480 79
Using a module for divisors
<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:
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.
Perl 6
<lang perl6>sub propdiv (\x) {
(1 if x > 1), gather for 2 .. x.sqrt.floor -> \d {
my \y = x div d;
if y * d == x { take d; take y unless y == d }
}
}
say "$_ ", propdiv($_) for 1..10;
my $max = 0; my @candidates; for 1..20000 {
my @pd = propdiv($_);
my $pd = @pd.elems;
if $pd > $max {
@candidates = ();
$max = $pd;
}
push @candidates, $_ if $pd == $max;
} say "max = $max, candidates = @candidates[]";</lang>
- Output:
1 Nil 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 = 79, candidates = 15120 18480
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
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
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
primes = prime_division.flat_map{|prime, freq| [prime] * freq}
(1...primes.size).each_with_object([1]) do |n, res|
primes.combination(n).map{|combi| res << combi.inject(:*)}
end.flatten.uniq
end
end
(1..10).map{|n| puts "#{n}: #{n.proper_divisors}"}
max = (1..20_000).group_by{|n| n.proper_divisors.size}.max.last max.each do |n|
puts "#{n} has #{n.proper_divisors.size} divisors"
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] 15120 has 79 divisors 18480 has 79 divisors
An Alternative Approach
<lang ruby>#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
Swift
Simple function: <lang Swift>func properDivs1(n: Int) -> [Int] {
return filter (1 ..< n) { n % $0 == 0 }
}</lang> More efficient function: <lang Swift>import func Darwin.sqrt
func sqrt(x:Int) -> Int { return Int(sqrt(Double(x))) }
func properDivs(n: Int) -> [Int] {
if n == 1 { return [] }
var result = [Int]()
for div in (filter(1 ... sqrt(n)) { n % $0 == 0 }) {
result.append(div)
if n/div != div && n/div != n { result.append(n/div) }
}
return sorted(result)
}</lang> Rest of the task: <lang Swift>for i in 1...10 {
println("\(i): \(properDivs(i))")
}
var (num, max) = (0,0)
for i in 1...20_000 {
let count = properDivs(i).count
if (count > max) { (num, max) = (i, count) }
}
println("\(num): \(max)")</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
Tcl
Note that if a number, , greater than 1 divides exactly, both and 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
<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)