Euler12.py

# -*- coding: utf-8 -*-
"""
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?

Math Insight: 
Triangular numbers are products of consecutive integers, n,(n+1) divided by two.
These are necessarily coprime, so their divisors, d(n), d(n+1) are unique. When 
counting the number of divisors for a triangular number, we can just consider 
the divisors of n and (n+1). One of them is even, since we're dividing by two, 
we subtract off the number of divisors by 1 for the even integer.

Answer: 76576500 
Ricky Kwok, rickyk9487@gmail.com, 2014-10-22
"""

def get_divisors(n):
    """ Computes the number of divisors for n by dividing out all powers of 2,
        then all odd integers. If the problem were larger, we could use a 
        Sieve of Eratosthenes to compute the primes first in a global variable. """
    divisors_cnt, i, m = 1, 3, n
    if n % 2 == 0:
        div_2_cnt = 0
        m = n / 2
        while m % 2 == 0 and m > 1:
            # counting powers of 2.
            div_2_cnt += 1
            m = m / 2
        divisors_cnt *= div_2_cnt + 1
        
    while i <= n and m > 1:
        # counting powers of i, where i is odd
        div_n_cnt = 0
        while m % i == 0 and m > 1:
            div_n_cnt += 1
            m = 1.0 * m / i
        else:
            divisors_cnt *= (div_n_cnt + 1)
            i += 2

    return divisors_cnt
    
def main():
    """ Calls get_divisors on producuts of consecutive integers divided by 2 and
        prints the first one that has number of divisors larger than 500. """
    left, right, n = get_divisors(2), get_divisors(3), 3
    while left*right < 500:
        n += 1
        left, right = right, get_divisors(n)
    print n * (n - 1) / 2
    
if __name__ == "__main__":
    main()