princeofsudan

Project Euler #23 Non-abundant sums

Mar 19th, 2013
117
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 2.13 KB | None | 0 0
  1. #A perfect number is a number for which the sum of its proper divisors is
  2. #exactly equal to the number. For example, the sum of the proper divisors of 28
  3. #would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.
  4.  
  5. #A number n is called deficient if the sum of its proper divisors is less than
  6. #n and it is called abundant if this sum exceeds n.
  7.  
  8. #As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest
  9. #number that can be written as the sum of two abundant numbers is 24.
  10. #By mathematical analysis, it can be shown that all integers greater than
  11. #28123 can be written as the sum of two abundant numbers.
  12. #However, this upper limit cannot be reduced any further by analysis even
  13. #though it is known that the greatest number that cannot be expressed as the
  14. #sum of two abundant numbers is less than this limit.
  15.  
  16. #Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.
  17.  
  18. from bisect import bisect_left
  19.  
  20. def divisorsSum(n):
  21.     acc = 0
  22.     for i in range(1,(n/2)+1):
  23.         if n % i == 0:
  24.             acc += i
  25.     return acc
  26.  
  27. def isAbundentPos(n):
  28.     if n > 0 and divisorsSum(n) > n:
  29.         return True
  30.     else:
  31.         return False
  32.  
  33. #Binary Search
  34. def search(a, x):
  35.     'Locate the leftmost value exactly equal to x'
  36.     i = bisect_left(a, x)
  37.     if i != len(a) and a[i] == x:
  38.         return True
  39.     return False
  40.  
  41. #Generate list of Abundent Numbers till 28124.
  42. abundentNumbers = []
  43. for i in range (1,28124):
  44.     if isAbundentPos(i):
  45.         abundentNumbers.append(i)
  46.  
  47. #Generate list of Abundent Sums till 28124 then Sorted and Duplicates Removed.
  48. abSum = []
  49. for i in abundentNumbers:
  50.     for j in abundentNumbers[abundentNumbers.index(i):]:
  51.         x = i+j
  52.         while x < 28124:
  53.             abSum.append(x)
  54.             break
  55. abSum = sorted(set(abSum))
  56.  
  57. #Generate list of Non Abundent Sums by subtracting Abundent Sums List.
  58. nonAbSum = []
  59. for i in range(1,28124):
  60.     if not search(abSum,i):
  61.         nonAbSum.append(i)
  62.  
  63. #Sum all numbers in the Non Abundent Sums List
  64. count = 0
  65. for i in nonAbSum:
  66.     count += i
  67. print count
Advertisement
Add Comment
Please, Sign In to add comment