Project euler #23 tricky conflict

李手指头

Project euler Problem 23 Non-abundant sums

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.

Here is my code who runs 25s to solve this problem.

import time

def check_abundant(n):
    s=0
    for i in range(1,n/2+1):
        if n%i==0:
            s+=i
    if n<s:
        return True
    else:
        return False

start = time.time()
check=[None]*28123
check[12]=True
for i in range(1,12):
    check[i]=False
total=0
can=0
for i in range(1,28123+1):
    canbe=False
    '''
    if i<24:
        total+=i
    if i==24:
        total+=0    
    '''
    for j in range(1,i/2+1):
        if check[j]==None:
            check[j]=check_abundant(j)
        if check[i-j]==None:
            check[i-j]=check_abundant(i-j)  
        if check[j]==True and check[i-j]==True:
            canbe=True
            break
    if canbe==False:
        total+=i
elapsed = (time.time() - start)
print "%s found in %s seconds" % (total,elapsed)

But I have a tricky question here, as it is said in the description, 24 is the smallest number that can be written as the sum of two abundant numbers, for me that also means 1-23 cannot be written as the sum of two abundant numbers, because they are smaller than 24 and they are positive integers.

Here is the problem. In my code, if I add 1-23 directly to the final output(because they are obviously part of the sum), I will get 4180147 which is 4179871+sum(range(1,24)). And if I check these numbers like the others, I will get the right answer 4179871.

So as far as I can see, there is a conflict between the description and my code.If 4179871 is the right answer, then 1-23 are integers can be written as the sum of two abundant numbers, but actually they cannot according to the description(24 is the smallest).

This question almost drive me crazy here, is there anyone can help?? Thanks a lot in advance!

jh314

Your code already adds numbers 1 to 23 to total.

If you modify your program to print out what numbers were added:

if canbe==False:
    print 'added ' + str(i)
    total+=i

the program will print out:

added 1
added 2
added 3
added 4
added 5
added 6
added 7
added 8
added 9
added 10
added 11
added 12
added 13
added 14
added 15
added 16
added 17
added 18
added 19
added 20
added 21
added 22
added 23
added 25
...

you will see that the numbers 1 to 23 were already added to total, so you don't need to add it yourself.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related