Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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.
- from bisect import bisect_left
- def divisorsSum(n):
- acc = 0
- for i in range(1,(n/2)+1):
- if n % i == 0:
- acc += i
- return acc
- def isAbundentPos(n):
- if n > 0 and divisorsSum(n) > n:
- return True
- else:
- return False
- #Binary Search
- def search(a, x):
- 'Locate the leftmost value exactly equal to x'
- i = bisect_left(a, x)
- if i != len(a) and a[i] == x:
- return True
- return False
- #Generate list of Abundent Numbers till 28124.
- abundentNumbers = []
- for i in range (1,28124):
- if isAbundentPos(i):
- abundentNumbers.append(i)
- #Generate list of Abundent Sums till 28124 then Sorted and Duplicates Removed.
- abSum = []
- for i in abundentNumbers:
- for j in abundentNumbers[abundentNumbers.index(i):]:
- x = i+j
- while x < 28124:
- abSum.append(x)
- break
- abSum = sorted(set(abSum))
- #Generate list of Non Abundent Sums by subtracting Abundent Sums List.
- nonAbSum = []
- for i in range(1,28124):
- if not search(abSum,i):
- nonAbSum.append(i)
- #Sum all numbers in the Non Abundent Sums List
- count = 0
- for i in nonAbSum:
- count += i
- print count
Advertisement
Add Comment
Please, Sign In to add comment