Project Euler Problem #12:

Problem #12 is the first of many Project Euler problems to feature multiplicative functions. A multiplicative function is a function f such that for all natural numbers x and y such that gcd(x,y)=1, f(xy) = f(x) * f(y). One of the most common multiplicative functions is the Divisor Function, or the function which returns the number of divisors of a number. Understanding this function is crucial to solving this problem:

Project Euler Problem 12: Highly divisible triangular number
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?

A simplistic way of counting the divisors of a number is to iterate through all numbers from 1 to the number and count the numbers that divide evenly. A slightly better way is counting from 1 to the square root of the number and doubling the result (or adding 1 in the case of square numbers). However, the fastest method of counting the divisors of a number reveals that the Divisor Function is multiplicative: the number of divisors of a function is the product of the results when 1 is added to each exponent in the prime factorization of the number. Using this fact, we can quickly count the divisors of a number. This results in the following solution:

Solution #1: Brute Force Approach

As discussed in an earlier problem, the nth triangular number is n(n+1)/2. This number gets big quite fast, so it could be difficult to factor the triangular numbers as they get bigger. The key observation that circumvents this problem is that n is relatively prime to (n+1). Because of this, we know that if d(n) is the divisor function, then d(n(n+1)/2) = d(n/2)*d(n+1) if n is even or d(n(n+1)/2) = d(n)*d((n+1)/2) if n is odd. Thus, it is not necessary for us to count the divisors of each large triangular number. Instead we only need to count the divisors of each index for the triangular numbers and then multiply consecutive numbers of divisors until one product is greater than 500. Here is an implementation of this approach in Python 2.7:

'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #12
'''
import time
from math import sqrt
def numberDivisors(n):
    total = 1
    c = 2
    while(c<=sqrt(n)):
        if(n%c==0):
            t = 0
            while(n%c==0):
                n/=c
                t+=1
            total*=(t+1)
        c+=1
    if(n>1):
        total*=2
    return total

def projectEulerProblemTwelve(n):
    last = 1
    if(n==1):
        return 1
    c = 3
    while(True):
        if(c%2==0):
            a = numberDivisors(c/2)
        else:
            a = numberDivisors(c)
        if(a*last>n):
            return c*(c-1)/2
        last = a
        c+=1

start = time.time()
print projectEulerProblemTwelve(500)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
76576500
--- 0.0434160232544 seconds ---
for input of n=500
'''

I am not thrilled with this solution as I believe it can be optimized with a different method. If it were possible to place an upper bound on the first number with a given number of factors, a sieve could be used to find the number of divisors of all numbers up to a given number. I may return to this question eventually.

That is all for today. I hope you enjoyed!