Proper divisors: Difference between revisions
+Java |
→{{header|Python}}: Add prime factor based version. |
||
Line 56: | Line 56: | ||
15120: 79</pre> |
15120: 79</pre> |
||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Python: Literal=== |
|||
A very literal interpretation |
A very literal interpretation |
||
<lang python>>>> def proper_divs2(n): |
<lang python>>>> def proper_divs2(n): |
||
Line 69: | Line 70: | ||
79 |
79 |
||
>>> </lang> |
>>> </lang> |
||
===Python: From prime factors=== |
|||
I found [http://stackoverflow.com/a/171784/10562 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: |
|||
<pre> |
|||
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</pre> |
|||
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> |
|||
{{out}} |
|||
<pre>[{1}, {1}, {1}, {1, 2}, {1}, {1, 2, 3}, {1}, {1, 2, 4}, {1, 3}, {1, 2, 5}] |
|||
15120 79</pre> |
Revision as of 06:02, 16 December 2014
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.
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