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.