### Problem 12

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?

### Solution 1: Rough answer

``````
'''
#This method num_divisors(Num, start_divisor) only checks half of divisors
#and with out counting 1 and itself if start_divisor is > 1
#The number of full divisors is 2*ret of num_divisors
'''
def num_divisors(n, divisor):
sqrtN = n**0.5
i = divisor
c = 0
while i < sqrtN:
if not n%i:
divisor = i
c += 1
break
i += 1
if i < sqrtN:
divisor += 1
c += num_divisors(n, divisor)
return c

" Brute forcing which takes only 9.84299993515 sec"
i = 1
answer = 0
while True:
n = (i**2 + i)//2
num = num_divisors(n, 1)

if 2*num > 500:
answer = n
break
i += 1

print(answer)
``````

This run:~ 6.115420579910278 in good time. The output: 76576500

### Solution 2:

I am gonna use this theorem for good!

Theorem:

The number of factors of N is equal to the product of the power of prime factorization of N + 1.

``````
def num_factors(n):
num = n
answer = 2
i = 2

temp = 0
while not num%i:
num //= i
temp += 1

answer *= temp+1

i = 3
while i < num**0.5:

# Reducing num to not multiple of i
temp = 0
while not num%i:
num //= i
temp += 1

answer *= temp+1

i += 2

if not num**0.5%1:
answer /= 2
answer *= 3

#print(answer)
return answer

" Brute forcing which takes only 9.84299993515 sec"
i = 1
answer = 0
while True:
n = (i**2 + i)//2
num = num_factors(n)

if num > 500:
answer = n
break
i += 1

print(answer)

``````

This run:~ 0.5420579910278. It is open for improvement.
The output: 76576500.