Proper divisors
The proper divisors of a positive integer N are those numbers, other than N itself, that divide N without remainder, and always include 1.
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
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);
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], [1, 2], [1], [1, 2, 3], [1], [1, 2, 4], [1, 3], [1, 2, 5]] Tuple!(uint, int)(79, 18480)
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>(); 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: [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
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} ... >>> [proper_divs2(n) for n in range(1, 11)] [{1}, {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 __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:
[{1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}, {1, 3}, {1, 2, 5}] 15120 79