CodeWords

By the use of a theorem and a (relatively) efficient factorization algorithm, we can solve this problem fairly quickly. First, the theorem:

Theorem. If , then

.

This theorem tells us that if we can decompose into its prime factors, we can efficiently calculate the number of divisors of . It remains, therefore, for us to find a sufficiently efficient factorization algorithm. How about this:

def prime_factorization(n):
	divisor = 2
	while n > 1:
		factors = []
		while n % divisor == 0:
			factors.append(divisor)
			n /= divisor
		if factors:
			yield factors
		divisor += 1

This algorithm starts with a divisor of 2 and, if n is divisible by the divisor, it divides n by the divisor as long as n is still divisible by the divisor. When n no longer is, it increments the divisor and tries again until n is reduced to 1. Furthermore, each of the prime factors of n that equal each other are grouped into subsequences. That is, for n = 1701, we get [[3, 3, 3, 3, 3], [7]]. This makes it easier to use the theorem above.

We use a generator function to yield the triangle numbers, and a divisor-counting function that makes use of the theorem above, to get the desired number. All of the code, then, together, is:

def triangle_numbers():
	n = 1
	while True:
		yield n * (n + 1) / 2
		n += 1

def prime_factorization(n):
	candidate_factor = 2
	while n > 1:
		factors = []
		while n % candidate_factor == 0:
			factors.append(candidate_factor)
			n /= candidate_factor
		if factors:
			yield factors
		candidate_factor += 1

def count_divisors(n):
	count = 1
	for tuple in prime_factorization(n):
		count *= (len(tuple) + 1) 
	return count

for t in triangle_numbers():
	if count_divisors(t) > 500:
		print t
		break