1
\$\begingroup\$

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. Here's my implementation in Python. I need your feedback on how this can be improved.

Note: I'm a beginner in programming.

from time import time


def get_divisors(n):
    """Yields divisors of n."""
    divisor = 2
    while divisor * divisor <= n:
        if n % divisor == 0 and n // divisor != divisor:
            yield divisor
            if n // divisor != divisor:
                yield n // divisor
        divisor += 1
    yield 1


def get_sum_amicable(n, divs={2:1}):
    """Yields amicables below n."""
    for number1 in range(n):
        for number2 in range(number1):
            try:
                if divs[number2] == number1 and divs[number1] == number2:
                    yield number1
                    yield number2
            except KeyError:
                divs[number1] = sum(get_divisors(number1))
                divs[number2] = sum(get_divisors(number2))
                if divs[number2] == number1 and divs[number1] == number2:
                    yield number1
                    yield number2


if __name__ == '__main__':
    start = time()
    print(sum(get_sum_amicable(10000)))
    print(f'Time: {time() - start} seconds.')
\$\endgroup\$
1
\$\begingroup\$

Readability / maintainability

def get_sum_amicable(n, divs={2:1}):
    """Yields amicables below n."""
    for number1 in range(n):
        for number2 in range(number1):
            try:
                if divs[number2] == number1 and divs[number1] == number2:
                    yield number1
                    yield number2
            except KeyError:
                divs[number1] = sum(get_divisors(number1))
                divs[number2] = sum(get_divisors(number2))
                if divs[number2] == number1 and divs[number1] == number2:
                    yield number1
                    yield number2

This is awful. It violates the rule "Don't Repeat Yourself"; it expects exceptions as part of non-exceptional flow; and it relies on an obscure language feature/mis-feature.

All you need to do is sum numbers x in range(n) (or, perhaps better, range(2, n), to avoid complications around 0 and 1) for which d(x) < n and d(d(x)) == x. (And given the way the question is phrased, you might assume that there will be no amicable pair which is split around n, so the first half of the test is probably unnecessary). That's a one-liner.

If you want to cache d, instead of using default values you can use functools.lru_cache. But...

Performance

Whenever you're doing divisibility checks on every number from 1 to n, you should think about using a sieve. Either build an array of one prime factor of each number, and work from that, or (where appropriate) inline the calculation into the sieve processing.

It's fairly easy to adapt the sieve of Eratosthenes to generate an array of d efficiently using the inline approach.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the feedback and any real examples you can provide will be greatly appreciated, it's a bit ambiguous what you explained maybe because i'm not that experienced in programming and i'm in the learning process I guess. \$\endgroup\$ – user203258 Jul 19 at 8:38
  • 1
    \$\begingroup\$ If you have specific questions relating to code, I can try to answer them. But I'm probably not going to write the code for you, or go into details on the maths, because (a) that misses the point of Project Euler; you'll learn more by doing than by reading; and (b) if you really want to miss the point of Project Euler, there are already resources out there with detailed explanations of the first hundred problems. \$\endgroup\$ – Peter Taylor Jul 19 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy