Click here to Skip to main content
14,298,065 members
Rate this:
Please Sign up or sign in to vote.
See more:
Non-abundant sums (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 just started learning how to program a few days ago and I've been stuck for a while with this one. I really don't know what am I doing wrong, maybe I am not understanding the question, or I'm not sure. Could you help me make it work? and if you know how to optimize it, it would be great as well if you could tell me. Thanks!

What I have tried:

import time
start = time.time()

lst = []
for i in range(1,28124):
    b = 0
    for n in range(1, int(i**.5 + 1)):
        if i % n == 0:
            if n == int(i / n) or n == 1:
                b += n
            else:
                b += n + int(i / n)
        if b > i:
            lst.append(i)
            break

lst2 = list(range(1,28124))
lst3 = []
for i in lst:
    for n in lst:
        if n > i:
            break
        c = i + n
        if c > 28123:
            break
        if c in lst3:
            break
        lst3.append(c)
        lst2.remove(c)


sum1 = 0
for i in lst2:
    sum1 += i

print(sum1)

end = time.time()
print(end - start)
Posted
Updated 2-Aug-19 21:31pm
Rate this:
Please Sign up or sign in to vote.

Solution 1

Quote:
As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16

Check when your code should stop to habe all possible factor of number.
Quote:
I really don't know what am I doing wrong

May be it is time to learn the debugger, it is a great learning tool.

Quote:
Could you help me make it work?

Your code do not behave the way you expect, or you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't know what your code is supposed to do, it don't find bugs, it just help you to by showing you what is going on. When the code don't do what is expected, you are close to a bug.
To see what your code is doing: Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]

27.3. pdb — The Python Debugger — Python 3.6.1 documentation[^]
Debugging in Python | Python Conquers The Universe[^]
pdb – Interactive Debugger - Python Module of the Week[^]

The debugger is here to only show you what your code is doing and your task is to compare with what it should do.
Quote:
and if you know how to optimize it, it would be great as well if you could tell me.

Optimization is a huge subject, teaching you is out if scope of this little text box.
Being good at optimization imply:
- having a very good understanding of code to optimize.
- Having extended knowledge of data structures and algorithms.
- Being seasoned at optimizing will help you too.

I wrote this article about integer factorization, it show how the trial division algorithm can be optimized. Every factor of a number is compound of prime factors of the number.
Integer Factorization: Trial Division Algorithm[^]

Advise: making a few functions instead of a monolithic bloc of code helps to separate concerns, it simplify things when you try different solutions and for testing.
   
v5
Rate this:
Please Sign up or sign in to vote.

Solution 2

Quote:
"By mathematical analysis, it can be shown ..."
What you are spending time learning here is mathematics rather than programming. If you really want to learn Python programming then go to The Python Tutorial — Python 3.7.4 documentation[^] and work through it a few times.
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100