def divisors(n):
"""
Returns all nontrivial divisors of an integer, but makes no guarantees on the order.
"""
for# i"1" inis rangealways a divisor (2,at least for our purposes)
yield 1 + largest = int(math.sqrt(n))
# special-case square numbers to avoid yielding the same divisor twice
if largest * largest == n:
yield largest
else:
largest += 1
# all other divisors
for i in range(2, largest):
if n % i == 0:
yield i
yield n / i
Plus of course 1. We can now rewrite our is_abundant to the simpler:
def is_abundant(n):
if n < 12:
return 1False
+ return sum(divisors(n)) > n
def divisors(n):
"""
Returns all nontrivial divisors of an integer, but makes no guarantees on the order.
"""
for i in range(2, 1 + int(math.sqrt(n))):
if n % i == 0:
yield i
yield n / i
Plus of course 1. We can now rewrite our is_abundant to the simpler:
def is_abundant(n):
return 1 + sum(divisors(n)) > n
def divisors(n):
"""
Returns all nontrivial divisors of an integer, but makes no guarantees on the order.
"""
# "1" is always a divisor (at least for our purposes)
yield 1 largest = int(math.sqrt(n))
# special-case square numbers to avoid yielding the same divisor twice
if largest * largest == n:
yield largest
else:
largest += 1
# all other divisors
for i in range(2, largest):
if n % i == 0:
yield i
yield n / i
We can now rewrite our is_abundant to the simpler:
def is_abundant(n):
if n < 12:
return False
return sum(divisors(n)) > n
Your first problem is that you're trying to cram too much information onto one line. As a result, you loose the overview. Here is a simple refactoring:
def is_abundant(n):
max_divisor = int(n / 2) + 1
sum = 0
for x in range(1, max_divisor):
if n % x == 0:
sum += x
return sum > n
abundants = list(x for x in range(1, 28123) if is_abundant(x))
sums = 0
for i in range(12, 28123):
for abundant in abundants:
if abundant >= i and is_abundant(i + abundant):
sums += i
print(sums)
- The
== Truetests are unecessary and were removed. - Naming was improved:
isabundant→is_abundant. - The long statement in
is_abundantwas split up.
Now we can think about how this could be optimized.
One subproblem is calculating all divisors of a number. We could put the relevant code into its own function. We can furthermore exploit that if n % i == 0, then there must be another integer k so that n == i * k. This means that we only have to look at a lot less numbers: only the range(2, 1 + int(sqrt(n))) is interesting.
def divisors(n):
"""
Returns all nontrivial divisors of an integer, but makes no guarantees on the order.
"""
for i in range(2, 1 + int(math.sqrt(n))):
if n % i == 0:
yield i
yield n / i
Plus of course 1. We can now rewrite our is_abundant to the simpler:
def is_abundant(n):
return 1 + sum(divisors(n)) > n
Later, in your main loop, you are doing a rather weird calculation. What were we supposed to do?
Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
We furthermore know that all integers above 28123 can be written as such a sum. Thus we have to look at the range(1, 28123 + 1)! How can we decide if a number n can be written as a sum of abundant numbers i and k? There exists any abundant number i with the constraint i < n, and another abundant number with the constraints k < n and n - i == k. Here is one clever way to write this:
def is_abundant_sum(n):
for i in abundants_smaller_than_n:
if (n - i) in abundants_smaller_than_n:
return True
return False
Because we don't want to calculate the abundants_smaller_than_n each time, we just take all possible abundants and bail out if we get larger than n:
def is_abundant_sum(n):
for i in abundants:
if i > n: # assume "abundants" is ordered
return False
if (n - i) in abundants:
return True
return False
where abundants = [x for x in range(1, 28123 + 1) if is_abundant(x)].
Now, all that is left to do is to sum those numbers where this condition does not hold true:
sum_of_non_abundants = sum(x for x in range(1, 28123 + 1) if not is_abundant_sum(x))
We could perform one optimization: abundants is a list, which is an ordered data structure. If we search for an element that is not contained in the list, all elements would have to be searched. The set() data structure is faster, so:
abundants_set = set(abundants)
def is_abundant_sum(n):
for i in abundants:
if i > n: # assume "abundants" is ordered
return False
if (n - i) in abundants_set:
return True
return False