Project Euler problem 23

gistfile1.py

import logging, math
logging.basicConfig(level=logging.INFO)
def d(n): 
	#cribbed directly from problem 21; gives the sum of proper divisors
	sum = 0
	for i in range(1, int(math.sqrt(n)+1)):
		if (n % i == 0):
			sum += i
	return sum
 
def sums(integers):
	#returns a list of sums of any two terms of the list
	sums = []
	for a in integers:
		for b in integers:
			sums.append(a+b)
	return sums
 
		
upperbound = 20161
#I have no idea how they got this upper bound by analysis. I would have just tested cases... Exactly like this program is doing. I'm a failure as a mathematician.
 
abundants = []	
for i in range(1, ((upperbound)/2)+1):
	if i < d(i):
		abundants.append(i)
		logging.debug ("Found an abundant number: {}".format(i))
 
 
integers = set(range(1, upperbound+1))
knownsums = sums(abundants)
integers = integers.difference(knownsums)
logging.debug(knownsums)
logging.info (sorted(integers))
logging.debug (abundants)
print (sum(integers))
 
 
"""
#here's a really slow, dumb way to do this.
integers = []
for i in range(1, upperbound):
	print ("Checking if {} is the sum of abundant numbers".format(i))
	
	if (not sumofabundants(i, abundants)):
		integers.append(i)
 
def sumofabundants(n, abundants):
	#returns True if n can be written as the sum of two abundant numbers. Not very efficient.
	for a in abundants:
		if a > i:
			break
		for b in abundants:
			if a + b > i:
				break
			elif a + b == i:
				return True
	else:
		return False
"""