Euler #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?
https://projecteuler.net/problem=12

Every college student is familiar with triangle numbers. They are the number of cups required for a rack in beer pong. Classic beer pong is played with 6 cups on a side. 6 is the 3rd triangle number. Sometimes, people elect to play longer games with 10 or 15 cups a side. This is just one place where triangle numbers show up.

Counting the divisors of a number is intimately related to the number’s prime factorization. The prime factorization decomposes a number down to its constituent prime factors. These prime factors can be combined with each other to create composite numbers that also divide the number cleanly.

For example, 28 has the prime factorization $2^2 \times 7^1$ . These prime factors can be combined with each other to create the divisors of 28.

	2⁰	2¹	2²
7⁰	1	2	4
7¹	7	14	28

We see that the number of divisors is related to the number of prime factors. 1 is added to each exponent of the prime factorization, then they are multiplied together to give the number of divisors. So, for 28, the exponents are 2 and 1. Add 1 to both of them, getting 3 and 2. Multiply them together to get 6, which is the number of divisors.

To solve the problem, it is necessary to find the exponents of the prime factorization of a triangle number. Luckily, the topic of prime factorization was covered in Euler #3: Largest Prime Factor. The function factorize from that post can be reused to find the exponents of the prime factorization.

As it stands now, the prime factorization function for 28 returns something like this: [2, 2, 7]. The exponents can be derived from this list by first converting the list to a set of unique prime factors. Then exponents are the counts of each unique factor in the list. This is a cinch using collections.Counter.

from collections import Counter

def prime_factorization_with_exponents(n):
    prime_factors = factorize(n) # Returns something like [2, 2, 7]
    exponents = Counter(prime_factors) # Returns something like {2: 2, 7: 1}
    return exponents

The values of the dictionary exponents are the exponents of the prime factorization. To count the divisors, simply add 1 to each exponent then multiply them all together. Multiplying together all elements of a list uses math.prod, a new addition in Python 3.8, an analogue to the sum function.

from collections import Counter
import math

def number_of_divisors(n):
    exponents = prime_factorization_with_exponents(n).values()
    return math.prod([exponent + 1 for exponent in exponents])

Now, we just need to generate triangle numbers and check their number of divisors till we hit the magic number of over 500 divisors.

i = 2
triangle_number = 1
while number_of_divisors(triangle_number) <= 500:
    triangle_number += i
    i += 1
print(triangle_number)

The complete script can be found on my GitHub. Running it gives the result $76576500$ . That’s one huge beer pong rack!