Project Euler 21: Sum of amicable numbers optimisation

Question

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.

I have the following code which I know works, but is very slow for large numbers.

import time
start = time.time()
n = int(input("Enter a number"))
def factor(c):
 factors = []
 for d in range(1, int(c / 2) + 1):
 if c % d == 0:
 factors.append(d)
 return sum(factors)
def sum_ammicable(x):
 ammicable = set()
 for a in range(1, x):
 for b in range(1, x):
 if a != b:
 if factor(a) == b and factor(b) == a:
 ammicable.update([a,b])
 return sum(ammicable)
print(sum_ammicable(n))
end = time.time()
print(end -start)

How can I optimise this code

• AJNeufeld: Have you solved the problem? If so, the Project Euler site has an overview you can read with lots of speed improvement tips.

Answer 1

Integer Division

Python comes with a built-in integer division operator. So instead of writing int(c / 2) + 1, you could simply write c // 2 + 1. It is slightly faster.

Unnecessary List Creation

Creating a list of factors just to sum(factors) afterwards is unnecessary busy work, which takes time. Simply add up the factors as you find them:

def factor(c):
 total = 0
 for d in range(1, c // 2 + 1):
 if c % d == 0:
 total += d
 return total

Or, use a generator expression with sum():

def factor(c):
 return sum(d for d in range(1, c // 2 + 1) if c % d == 0)

There is no need to store the factors you found.

Move Invariants out of Loops

Consider:

def sum_ammicable(x):
 ...
 for a in range(1, x):
 for b in range(1, x):
 if a != b:
 if factor(a) == b and ...:
 ...
 ...

How many times is factor(a) computed when a==1? If x == 10000, it gets computed 10000 times ... once for each b value. How many times when a==2? It'll get computed 10000 times as well. But does factor(a) depend on the value of b? No. Each time you compute factor(a), for the same value of a, the same result is produced.

Can you calculate this value once per a loop? Sure! Move it out of the b loop!

def sum_ammicable(x):
 ...
 for a in range(1, x):
 factor_a = factor(a)
 for b in range(1, x):
 if a != b:
 if factor_a == b and ...:
 ...
 ...

Instead of computing factor(a) 100,000,000 times, you now only compute it 10,000 times, which should be a significant improvement in speed.

Finally, considering that:

 for b in range(1, x):
 ...
 if factor_a == b and ...:
 ...

will only execute the rest of the if statement (and perhaps the body of the if) for exactly one value of b, do you really need to loop over all 10,000 possible b values? With a little thought, and a little reworking of the code, you can remove the b loop altogether!

Group Related Code Together

You start with

start = time.time()
n = int(input("Enter a number"))

then 2 function definitions, and then you continue with mainline code:

print(sum_ammicable(n))
end = time.time()
print(end -start)

Move the code together, after the function declarations. Even better, place it inside a if __name__ == '__main__': guard, so you can import factor(c) and sum_ammicable(x) functions into other code:

if __name__ == '__main__':
 start = time.time()
 n = int(input("Enter a number"))
 print(sum_ammicable(n))
 end = time.time()
 print(end - start)

Now that this code isn't separated by 2 functions, it becomes apparent you are timing how long the user takes to "Enter a number" in addition to the time it takes to compute sum_ammicable(n). Is the user's reaction & typing speed really being profiled here? Perhaps you want to move start = time.time() after the input statement.

Pro tip: use time.perf_counter() instead of time.time() for higher accuracy profiling.

---

Algorithmic improvements are covered on the Project Euler site itself. Read the problem overview after successfully completing the problem for some additional dramatic improvements. There is no need to reproduce their analysis here.

• J. Cricks: Yeh I just realised how stupid it waste start timing before the user enters the number. I also figured out that the for loop for b wasn't required as well. Thanks

Answer 2

One other major and easy improvement is to notice that factors come in pairs: if a%n==0, then (n/a)%n==0.

Thus you only need to look for factors less that n**.5+1. Here's how the factor sum code looks now:

def factor(c):
 total = 1
 for d in range(2, int(c**.5 + 1)):
 if c % d == 0:
 total += d
 if c//d > d:
 total += (c//d)
 return total

Note that by n=10_000, this loop only has 100 iteration, compared to 5000 before. That's a roughly 50x speedup. For another factor of 2 speedup, notice that a,b is amicable if and only if b,a is amicable, so you can start the b loop at the value of a+1

Answer 3

The following is an updated version of my code:

import time
import math
# finds the sum of the proper divisors of a number c
def factor(c):
 sum_of_factors = 1
 if type(math.sqrt(c)) is int:
 sum_of_factors += math.sqrt(c)
 for d in range(2, int(math.sqrt(c)) + 1):
 if c % d == 0:
 sum_of_factors += d + (c / d)
 return sum_of_factors
# finds sum of amicable numbers
def sum_amicable(x):
 amicable = 0
 for a in range(1, x):
 b = factor(a)
 if a != b and factor(a) == b and factor(b) == a:
 amicable += (a + b) / 2
 return amicable
n = int(input("Enter a number"))
start = time.time()
print(sum_amicable(n))
end = time.time()
print(end - start)

I found the answer in 0.16054987907409668 seconds

• AJNeufeld: type(math.sqrt(4)) is int results in False instead of True. And factor(4) results in 5.0 instead of 3. While you might end up getting the correct answer, this code is broken; the original code was correct, but slower, and correctness matters more than speed.
• AJNeufeld: This is not a proper answer on Code Review. Answers must critic the original code, and explain why code should be changed from the original and why the change is an improvement. Simply posting updated code based on feedback in other answers does not constitute a review.