Problem 12 - Highly Divisible Triangular Number

The giant triangular shaped Pidurangala Rock located north of & adjacent to Sigiriya Lion Rock
Sigiriya, Sri Lanka - May 2nd, 2025

The sequence of triangle numbers is generated by adding the natural numbers. So the 7^th 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 triangle numbers: \[ \begin{align} & \mathbf 1 \colon 1\\ & \mathbf 3 \colon 1,3\\ & \mathbf 6 \colon 1,2,3,6\\ & \mathbf{10} \colon 1,2,5,10\\ & \mathbf{15} \colon 1,3,5,15\\ & \mathbf{21} \colon 1,3,7,21\\ & \mathbf{28} \colon 1,2,4,7,14,28 \end{align} \]

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

Development

Resources:

• https://lucidmanager.org/data-science/project-euler-12/
• https://martin-ueding.de/posts/project-euler-solution-12-highly-divisible-triangular-number/

Here we can generate triangular numbers and then use trial factorization to find the number of divisors.

As stated above, the \(n^{th}\) triangular number can be generated by adding the natural numbers below it, i.e.:

\[T_n = \sum_{1}^{n}i\]

This has been proven to be simplified to:

\[T_n = \frac{n*(n+1)}{2}\]

It is known & can be proven that the number of divisors of a number is equivalent to product of the multiplicities of the prime factors of a number plus 1.

In other words, for \(n\), the prime factorization can be represented as:

\[n = p^{\alpha_1}_1 \times p^{\alpha_2}_2 \times \ldots \times p^{\alpha_k}_k\]

Where the number of divisors of \(n\) is:

\[d_n = (\alpha_1 + 1) (\alpha_2 + 1) \times \ldots \times (\alpha_k + 1)\]

To efficiently find the prime factors, we can use the Sieve of Eratosthenes from previous problems (e.g. Problem 10), calculating all possible primes up till \(\sqrt{n}\), then use trial division to obtain the prime factor list.

R

Answer 1 - Triangular Generator

sieve <- function(n) {
  if (n <= 3) {
    if (n <= 1) return(NULL)
    if (n == 2) return(n)
    return(c(2, n))
  }
  # prime candidates
  x <- rep(TRUE, n)
  # number 1 is not prime
  x[1] <- FALSE
  i = 2
  n0 <- floor(sqrt(n))
  for (i in 2:n0) {
    if (x[i]) {
      x[seq(i^2, n, i)] <- FALSE
    }
  }
  return((1:n)[x])
}

prime.factors <- function(n) {
  if (n <= 1) return(NULL)
  # prime candidates
  p <- sieve(floor(sqrt(n)))
  # prime factors
  p <- p[which(n %% p == 0)]
  # only n is prime
  if (length(p) == 0) return(n)
  # stores n's factors 
  f <- c()
  # get rest of prime factors
  for (i in p) {
    while (n %% i == 0) {
      f <- c(f, i)
      n <- n/i
    }
  }
  # gets highest last possible prime factor
  if (n > 1) {
    f <- c(f, n)
  }
  return(f)
}

triangular.nd <- function(n) {
  i <- 1
  dn <- 0
  while(dn < n) {
    tr <- i*(i+1)/2
    pn <- prime.factors(tr) |> table() |> as.numeric()
    dn <- prod(pn + 1)
    i <- i+1
  }
  return(tr)
}

tic()
triangular.nd(n = 500)
toc()

[1] 76576500
3.266 sec elapsed

Python

Answer 1 - Triangular Generator

def sieve(n: float) -> list:
  if n <= 3:
    if n <= 1: return([])
    if n == 2: return([n])
    return([2, n])
  n = int(n)
  # prime candidates
  x = [True] * n
  # number 1 is not prime
  x[0] = False
  n0 = int(n**0.5)
  for i in range(2, n0+1):
    if x[i-1]:
      for j in range(i**2, n+1, i):
        x[j-1] = False
  return([i for i, j in zip(list(range(1,n+1)), x) if j])

def prime_factors(n: int) -> list:
  """
  Returns prime factorization of an integer
  """
  if (n <= 1): return([])
  # prime candidates
  p = sieve(int(n**0.5))
  # prime factors
  p = [i for i in p if n % i == 0]
  # only n is prime
  if len(p) == 0: return([n])
  # stores n's factors 
  f = []
  # get rest of prime factors 
  for i in p:
    while(n % i == 0):
      f.append(i)
      n /= i
  if n > 1:
    f.append(int(n))
  return(f)

import time
from math import prod
from collections import Counter

def triangular_nd(n: int) -> int:
  i = 1
  dn = 0
  while(dn < n):
    tr = i*(i+1)/2
    pn = list(Counter(prime_factors(tr)).values())
    dn = prod([i+1 for i in pn])
    i += 1
  return(tr)

t0 = time.perf_counter()
print(triangular_nd(500))
t1 = time.perf_counter()
t = t1 - t0
print(f'{t:.3f} sec elapsed')

76576500.0
3.846 sec elapsed