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
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.
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
Perl
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.
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
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
<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
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)