Python Implementation of Problem 21
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 21
I had to approach this by modifying the factors function from p0003, but it seemed to work fairly well.
Revision 1:
Rewrote the proper_divisors function to be significantly faster by leveraging the prime_factors object.
Problem:
Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.
For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.
Evaluate the sum of all the amicable numbers under 10000.
1"""
2Project Euler Problem 21
3
4I had to approach this by modifying the factors function from p0003, but it
5seemed to work fairly well.
6
7Revision 1:
8
9Rewrote the proper_divisors function to be significantly faster by leveraging
10the prime_factors object.
11
12Problem:
13
14Let d(n) be defined as the sum of proper divisors of n (numbers less than n
15which divide evenly into n). If d(a) = b and d(b) = a, where a ≠ b, then a and
16b are an amicable pair and each of a and b are called amicable numbers.
17
18For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55
19and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and
20142; so d(284) = 220.
21
22Evaluate the sum of all the amicable numbers under 10000.
23"""
24from itertools import filterfalse
25from typing import Set
26
27from .lib.factors import proper_divisors
28
29
30def d(n: int) -> int:
31 return sum(proper_divisors(n))
32
33
34def main() -> int:
35 ret = 0
36 skip: Set[int] = set()
37 for a in filterfalse(skip.__contains__, range(10000)):
38 b = d(a)
39 if a != b and d(b) == a:
40 ret += a + b
41 skip.add(b)
42 return ret