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. The first ten terms would be: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Let us list the factors of the first seven triangle numbers: 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 We can see that 28 is the first triangle number to have over five divisors. What is the value of the first triangle number to have over five hundred divisors?
In [7]:
def first_N_primes(N):
primes_found = []
i = 1
while len(primes_found) < N:
i += 1
d = 1
for p in primes_found:
if i % p == 0:
d = i / p
break
if d == 1:
primes_found.append(i)
return primes_found
some_primes = first_N_primes(10000)
In [8]:
def ith_triang(i):
return i*(i+1)/2.0
def get_factors(N):
factors = {}
sq_N = sqrt(N)
while N > 1:
for i,p in enumerate(some_primes):
if N % p == 0:
N = N/p
if p not in factors:
factors[p] = 0
factors[p] += 1
break
return factors
def num_divisors(n):
f = get_factors(n)
num_d = 1
for e in f.itervalues():
num_d = num_d*(e + 1)
return num_d
i = 1
U = 500
while num_divisors(ith_triang(i)) < U:
i += 1
if i % 1000 == 0:
print i, ith_triang(i), num_divisors(ith_triang(i))
print "Finished:",i, ith_triang(i), num_divisors(ith_triang(i))
In [ ]: