trjhtr

Project Euler Problem 23

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of $28$ would be $1 + 2 + 4 + 7 + 14 = 28$, which means that $28$ is a perfect number.

A number $n$ is called deficient if the sum of its proper divisors is less than $n$ and it is called abundant if this sum exceeds $n$.

As $12$ is the smallest abundant number, $1 + 2 + 3 + 4 + 6 = 16$, the smallest number that can be written as the sum of two abundant numbers is $24$. By mathematical analysis, it can be shown that all integers greater than $28123$ can be written as the sum of two abundant numbers.

However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

I do not have a programming background. The code I have written is testing my patience and is not giving any solution. Kindly, provide the suggestions for the optimization.

array = 
array1 = 
for i in range(12, 28123):
add = 0
for j in range(1, i//2 + 1):
 if i%j ==0:
 add += j
 if add > i:
 array.append(i)
 break
total_num = list(range(1,28124))

for k in range(len(array)):
 for l in range(k, len(array)):
 add = 0
 add = array[k] + array[l]
 if add not in array1 and add in total_num:
 array1.append(add)
 else:
 continue

print(sum(total_num)-sum(array1))

I assume your original program is the following (as it is not properly indented in the question):

array = 
array1 =
for i in range(12, 28123):
 add = 0
 for j in range(1, i//2 + 1):
 if i%j ==0:
 add += j
 if add > i:
 array.append(i)
 break
total_num = list(range(1,28124))

for k in range(len(array)):
 for l in range(k, len(array)):
 add = 0
 add = array[k] + array[l]
 if add not in array1 and add in total_num:
 array1.append(add)
 else:
 continue

print(sum(total_num)-sum(array1))

First of all, great job! I don't see any logical issues with your implementation.

Minor nitpick

Generally, it's best to avoid names like array and array1. This has nothing to do with performance, but helps a lot for program readability. Better names in this case for array and array1 would be abundants and abundant_sums.

Performance

At a first glance, two big performance problems that can be easily addressed can be found on the line:

if add not in abundant_sums and add in total_num

These are two array lookups which take linear time (O(n)) and are executed for every possible pair of abundant numbers (which turns out to be a little over 48 million times!).

Let's takle both issues separately:

• 
  add not in abundants - the way to remove this altogether is to make abundant_sums a set, rather than an array. This way, you can just say abundant_sums.add(add) without first checking if it's already there (OK, perhaps add should be called sum to avoid this :) )


• 
  add in total_num - this is basically just a range check. And actually, just an upper bound check, since the numbers you deal with could never yield a sum less than 24. So, instead of add in total_num which traverses an array of 28+K items, you can just say add <= 28123. That's it.

By just applying these two optimizations, I get a program that produces the correct result in a little over 30s:

abundants = 
abundant_sums = set()
for i in range(12, 28123):
 add = 0
 for j in range(1, i//2 + 1):
 if i%j ==0:
 add += j
 if add > i:
 abundants.append(i)
 break
print len(abundants)
total_num = list(range(1,28124))

for k in range(len(abundants)):
 for l in range(k, len(abundants)):
 add = 0
 add = abundants[k] + abundants[l]
 if add <= 28123:
 abundant_sums.add(add)
print(sum(total_num)-sum(abundant_sums))

Another slight optimization that you could perform is to not compute the sum of total_num, but just use the formula max * (max+1) / 2. This is unlikely, however, to provide a major benefit in your case, since this calculation takes place only once. Anyway, I believe it's good to know this trick.