#12 - Highly divisible triangular number

in Project Euler on 5%

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, \dots\]

Let us list the factors of the first seven triangular 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 triangular number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

We will take an optimized brute force approach. The formula for the $n^{\text{th}}$ triangular number $T_n$ is \[T_n = \sum_{i=1}^n i = \frac{n(n+1)}{2}\]

It is possible for us to look for the factors in a brute force manner, by looping until $\sqrt{T_n}$. However, note that the problem doesn’t require us to find the factors themselves, only the number of divisors. If we have the prime factorization of a number, it is trivial to find the number of divisors. If the prime factorization of $n$ is \[n = p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\]

Then the number of divisors $D$ is \[D = \prod_{i=1}^k (e_i+1)\]

Add one to each exponent, and multiply them all together. This is the method we will use.

# file: "problem012.py"
def numOfFactors(n):
    # Get prime numbers less
    # than square root of n
    primes = primesieve.primes(n ** 0.5)
    # Filter...
    primes = [p for p in primes if n % p == 0]
    # Now we need to find powers...
    prod = 1
    for p in primes:
        count = 0
        while n % p == 0:
            count += 1
            n //= p
        # Multiply by one more
        # than the number of powers
        prod *= (count + 1)
    return prod
    
n = 8
while True:
    num = n * (n + 1) // 2
    f = numOfFactors(num)
    if f > 500:
        print(num)
        break
    n += 1

Running gives

76576500
0.7927415999874938 seconds.

Thus, 76576500 is our answer.