|
1
|
|
|
""" |
|
2
|
|
|
Project Euler Problem 21: Amicable Numbers |
|
3
|
|
|
========================================== |
|
4
|
|
|
|
|
5
|
|
|
.. module:: solutions.problem21 |
|
6
|
|
|
:synopsis: My solution to problem #21. |
|
7
|
|
|
|
|
8
|
|
|
The source code for this problem can be |
|
9
|
|
|
`found here <https://bitbucket.org/nekedome/project-euler/src/master/solutions/problem21.py>`_. |
|
10
|
|
|
|
|
11
|
|
|
Problem Statement |
|
12
|
|
|
################# |
|
13
|
|
|
|
|
14
|
|
|
Let :math:`d(n)` be defined as the sum of proper divisors of :math:`n` (numbers less than :math:`n` which divide evenly |
|
|
|
|
|
|
15
|
|
|
into :math:`n`). |
|
16
|
|
|
|
|
17
|
|
|
If :math:`d(a) = b` and :math:`d(b) = a`, where :math:`a \\neq b`, then :math:`a` and :math:`b` are an amicable pair and |
|
|
|
|
|
|
18
|
|
|
each of :math:`a` and :math:`b` are called amicable numbers. |
|
19
|
|
|
|
|
20
|
|
|
For example, the proper divisors of :math:`220` are :math:`1, 2, 4, 5, 10, 11, 20, 22, 44, 55` and :math:`110`; |
|
|
|
|
|
|
21
|
|
|
therefore :math:`d(220) = 284`. The proper divisors of :math:`284` are :math:`1, 2, 4, 71` and :math:`142`; so |
|
|
|
|
|
|
22
|
|
|
:math:`d(284) = 220`. |
|
23
|
|
|
|
|
24
|
|
|
Evaluate the sum of all the amicable numbers under :math:`10000`. |
|
25
|
|
|
|
|
26
|
|
|
Solution Discussion |
|
27
|
|
|
################### |
|
28
|
|
|
|
|
29
|
|
|
Pre-compute :math:`d(n)` for all :math:`n` in our search space and then iterate over :math:`n` searching for |
|
|
|
|
|
|
30
|
|
|
:math:`d(n) = m` and :math:`d(m) = n` where :math:`n \\neq m`. Compute the sum of all such :math:`(n, m)`. |
|
|
|
|
|
|
31
|
|
|
|
|
32
|
|
|
.. note:: the pre-computation of :math:`d(n)` for an increasing :math:`n` can be drastically sped up by using sieving |
|
|
|
|
|
|
33
|
|
|
techniques. An alternative, but inferior, method would be to find the divisors of increasing values of |
|
|
|
|
|
|
34
|
|
|
:math:`n` via factorisation. |
|
35
|
|
|
|
|
36
|
|
|
Solution Implementation |
|
37
|
|
|
####################### |
|
38
|
|
|
|
|
39
|
|
|
.. literalinclude:: ../../solutions/problem21.py |
|
40
|
|
|
:language: python |
|
41
|
|
|
:lines: 44- |
|
42
|
|
|
""" |
|
43
|
|
|
|
|
44
|
|
|
from lib.numbertheory.sieve import divisors_sieve |
|
45
|
|
|
|
|
46
|
|
|
|
|
47
|
|
|
def solve(): |
|
48
|
|
|
""" Compute the answer to Project Euler's problem #21 """ |
|
49
|
|
|
|
|
50
|
|
|
# Pre-compute d(n) for all n in [2, 9999] |
|
51
|
|
|
target = 10000 |
|
52
|
|
|
divisor_counts = divisors_sieve(target - 1, proper=True, aggregate="sum") |
|
53
|
|
|
d_vals = {n + 1: div_count for n, div_count in enumerate(divisor_counts)} |
|
54
|
|
|
del d_vals[1] # divisors_sieve covers the closed interval [1, target - 1], remove d(1) |
|
55
|
|
|
|
|
56
|
|
|
# Identify amicable numbers |
|
57
|
|
|
amicable_numbers = set() |
|
58
|
|
|
for n, d_n in d_vals.items(): |
|
|
|
|
|
|
59
|
|
|
if d_n in d_vals and d_vals[d_n] == n and n != d_n: |
|
60
|
|
|
amicable_numbers.add(n) |
|
61
|
|
|
amicable_numbers.add(d_n) |
|
62
|
|
|
|
|
63
|
|
|
# Sum all amicable numbers |
|
64
|
|
|
answer = sum(amicable_numbers) |
|
65
|
|
|
return answer |
|
66
|
|
|
|
|
67
|
|
|
|
|
68
|
|
|
expected_answer = 31626 |
|
|
|
|
|
|
69
|
|
|
|
Loading history...
This check looks for lines that are too long. You can specify the maximum line length.