-1
\$\begingroup\$

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))
\$\endgroup\$

closed as off-topic by Mast, Graipher, Vogel612, Mathias Ettinger, t3chb0t Feb 9 '18 at 10:47

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Questions containing broken code or asking for advice about code not yet written are off-topic, as the code is not ready for review. After the question has been edited to contain working code, we will consider reopening it." – Mast, Graipher, Vogel612, Mathias Ettinger, t3chb0t
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 7
    \$\begingroup\$ Please post a valid Python program. This fails because of indentation errors. \$\endgroup\$ – Cristian Lupascu Feb 9 '18 at 9:01
2
\$\begingroup\$

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.

\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.