Amicable pairs: Difference between revisions

Content added Content deleted

Inline

Revision as of 06:09, 16 December 2014

Two integers N and M are said to be amicable pairs if N != M and the sum of the proper divisors of N == M as well as the sum of the proper divisors of M == N.

For example 1184 and 1210 are an amicable pair (with proper divisors 1, 2, 4, 8, 16, 32, 37, 74, 148, 296, 592 and 1, 2, 5, 10, 11, 22, 55, 110, 121, 242, 605 respectively).

Task

Calculate and show here the Amicable pairs below 20,000; (there are eight).

Python

Importing Proper divisors from prime factors: <lang python>from proper_divisors import proper_divs

def amicable(rangemax=20000):

   n2divsum = {n: sum(proper_divs(n)) for n in range(1, rangemax + 1)}
   for num, divsum in n2divsum.items():
       if num < divsum and divsum <= rangemax and n2divsum[divsum] == num:
           yield num, divsum

if __name__ == '__main__':

   for num, divsum in amicable():
       print('Amicable pair: %i and %i With proper divisors:\n    %r\n    %r'
             % (num, divsum, sorted(proper_divs(num)), sorted(proper_divs(divsum))))</lang>

Output:

Amicable pair: 220 and 284 With proper divisors:
    [1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110]
    [1, 2, 4, 71, 142]
Amicable pair: 1184 and 1210 With proper divisors:
    [1, 2, 4, 8, 16, 32, 37, 74, 148, 296, 592]
    [1, 2, 5, 10, 11, 22, 55, 110, 121, 242, 605]
Amicable pair: 2620 and 2924 With proper divisors:
    [1, 2, 4, 5, 10, 20, 131, 262, 524, 655, 1310]
    [1, 2, 4, 17, 34, 43, 68, 86, 172, 731, 1462]
Amicable pair: 5020 and 5564 With proper divisors:
    [1, 2, 4, 5, 10, 20, 251, 502, 1004, 1255, 2510]
    [1, 2, 4, 13, 26, 52, 107, 214, 428, 1391, 2782]
Amicable pair: 6232 and 6368 With proper divisors:
    [1, 2, 4, 8, 19, 38, 41, 76, 82, 152, 164, 328, 779, 1558, 3116]
    [1, 2, 4, 8, 16, 32, 199, 398, 796, 1592, 3184]
Amicable pair: 10744 and 10856 With proper divisors:
    [1, 2, 4, 8, 17, 34, 68, 79, 136, 158, 316, 632, 1343, 2686, 5372]
    [1, 2, 4, 8, 23, 46, 59, 92, 118, 184, 236, 472, 1357, 2714, 5428]
Amicable pair: 12285 and 14595 With proper divisors:
    [1, 3, 5, 7, 9, 13, 15, 21, 27, 35, 39, 45, 63, 65, 91, 105, 117, 135, 189, 195, 273, 315, 351, 455, 585, 819, 945, 1365, 1755, 2457, 4095]
    [1, 3, 5, 7, 15, 21, 35, 105, 139, 417, 695, 973, 2085, 2919, 4865]
Amicable pair: 17296 and 18416 With proper divisors:
    [1, 2, 4, 8, 16, 23, 46, 47, 92, 94, 184, 188, 368, 376, 752, 1081, 2162, 4324, 8648]
    [1, 2, 4, 8, 16, 1151, 2302, 4604, 9208]

@@ Line 9: / Line 9: @@
 =={{header|Python}}==
+Importing [[Proper_divisors#Python:_From_prime_factors|Proper divisors from prime factors]]:
-<lang python>from math import sqrt
-from functools import lru_cache, reduce
+<lang python>from proper_divisors import proper_divs
-from collections import Counter
-from itertools import product
+def amicable(rangemax=20000):
+    n2divsum = {n: sum(proper_divs(n)) for n in range(1, rangemax + 1)}
+    for num, divsum in n2divsum.items():
+        if num < divsum and divsum <= rangemax and n2divsum[divsum] == num:
+            yield num, divsum
+if __name__ == '__main__':
-MUL = int.__mul__
+    for num, divsum in amicable():
-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):
-    '''
-    Using idea from: http://stackoverflow.com/a/171784/10562
-        In essence, this algorithm is doing the following:
-        factors = prime1 ^ 0 * prime2 ^ 0 * ... primeN ^ 0;
-                  prime1 ^ 0 * prime2 ^ 0 * ... primeN ^ 1;
-                    ...          ...        ...   ...     ;
-                  prime2 ^ i * prime2 ^ j * ... primeN ^ k;
-        Where `i`, `j`, and `k` are the multiplicity of the prime factor.
-    '''
-    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}
-def proper_divs2(n):
-    'Straight forward calculator is an order of magnitude slower than proper_divs function for n = 1..20000'
-    return {x for x in range(1, (n + 1) // 2 + 1) if n % x == 0}# or {1}
-rangemax = 20000
-n2divsum = {n: sum(proper_divs(n)) for n in range(1, rangemax + 1)}
-for num, divsum in n2divsum.items():
-    if num < divsum and divsum <= rangemax and n2divsum[divsum] == num:
         print('Amicable pair: %i and %i With proper divisors:\n    %r\n    %r'
               % (num, divsum, sorted(proper_divs(num)), sorted(proper_divs(divsum))))</lang>