euler12.py

"""
The sequence of triangle numbers is generated by adding the natural numbers.

So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

What is the value of the first triangle number to have over five hundred divisors?
"""
import math

def num_divisors(n):
	"""
	Returns the number of divisors of integer n
	Brute force approach: Check all integers up to sqrt(n) and count pairs of divisors

	Another approach using the divisor or Tau function:	
		Write the number as a product of prime factors: n = p^a * q^b * r^c * ...
		then the number of divisors, d(n) = (a+1)*(b+1)*(c+1)* ...
	"""
	
	divisor_list = [1,n]
	for i in range(2, int(math.floor(math.sqrt(n)))):
		if n % i == 0:
			divisor_list.append(i)
			divisor_list.append(n/i)
	divisor_list = list(set(divisor_list))
	return len(divisor_list)

def tri_num_500_divisors():
	""" Prints the first triangle number with over 500 divisors """
	tri_num = 1
	index = 2
	while num_divisors(tri_num) <= 500:
		tri_num += index
		index += 1

	print str(tri_num) + " has " + str(num_divisors(tri_num)) + " divisors."

# run script
if __name__ == "__main__":
	"""
	print num_divisors(1)
	print num_divisors(3)
	print num_divisors(6)
	print num_divisors(10)
	print num_divisors(15)
	print num_divisors(21)
	print num_divisors(28)
	"""

	print tri_num_500_divisors()