Project 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, \ldots\)

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?

In the video below, Vishal Kataria explains a simple method to determine the number of divisors using prime factorization. The prime factorization of \(n\) is given by:

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

Where \(p\) is a prime factor, and \(\alpha\) is the number of times the factor is repeated.

The number of proper divisors is for \(n\) is:

$$d = (\alpha_1 + 1) (\alpha_2 + 1) \times \ldots \times (\alpha_k + 1)$$

The code reuses the prime factorisation function developed for Euler Problem 3. This function results in a vector of all prime factors, e.g. the prime factors of 28 are 2, 2 and 7.

The code to solve this problem determines the values for alpha using the run-length rle() function. This function counts the number of times each element in a sequence is repeated. The outcome of this function is a vector of the values and the number of times each is repeated. The prime factors of 28 are 2, 2 and 7, and their run lengths are 2 and 1. The number of divisors can now be determined.

$$ 28 = 2^2 \times 7^1$$

$$ d = (2+1)(1+1) = 6$$

The six divisors of 28 are 1, 2, 4, 7, 14 and 28.

The code to solve Project Euler 12 is shown below. The loop continues until it finds a triangular number with 500 divisors. The first two lines increment the index and create the next triangular number. The third line in the loop determines the number of times each factor is repeated (the run lengths). The last line calculates the number of divisors using the above formula.

ProjectEuler

  ## Project Euler 12: Highly Divisible Triangular Number
  i <- 0
  divisors <- 0
  while (divisors < 500) {
      i <- i + 1
      triangle <- (i * (i + 1)) / 2
      pf <- prime.factors(triangle)
      alpha <- rle(pf)
      divisors <- prod(alpha$lengths + 1)
  }
  answer <- triangle
  print(answer)