Highly Divisible Triangular Number

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:

\begin{align} 1, 3, 6, 10, 15, 21, 28, 36, 45, 55 \end{align}

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?

Solution

Generating the triangle numbers is very easy. The real challenge is to find the number of divisors in an efficient way.

The naive method wouldn’t work. You can try it, but it will take too long to finish, because the number that has 500 divisors will be quite large.

Any number can be represented as a product of prime factors. For example, \(28\) is \(2^2 × 7^1\).

We can get these factors by dividing the 28 by its prime factors:

\begin{align} 28 ÷ 2 = 14\\ 14 ÷ 2 = 7\\ 7 ÷ 7 = 1\\ \end{align}

The next interesting thing is, that if we take increase those factors by one and multiply them with each other, we’ll get a total number of factors: \((2+1)(1+1) = 6\).

We can leverage those facts to quickly find the number of divisors, the only thing we need is a list of primes to use.

Let’s assume that our number will fit as a regular integer, in that case, we can get all primes like that:

  private val primes: Seq[Int] =
  (2 to Math.sqrt(Integer.MAX_VALUE).toInt)
    .filter(EulerHelper.naiveIsPrime)

We could also use a sieve of Eratosthenes here, but let’s keep it simple instead.

Getting next triangle numbers is easy, we can do it with a simple recursive function that keeps the current triangle number as n and the addend that was used to create it as k. Each iteration we increase k by one and calculate n from n + k.

  @tailrec
private def findTriangleNumber(n: Int = 1, k: Int = 2): Int =
  if (divisors(n) > 500) n
  else findTriangleNumber(n + k, k + 1)

The missing part is to implement the divisors(n) function that calculates the number of divisors of n.

We’ve already discussed the algorithm, let’s think about the method signature:

  @tailrec
private def divisors(
                      n: Int,
                      primes: Seq[Int] = primes,
                      divisorsFound: Map[Int, Int] = Map.empty
                    ): Int 

• n is the number
• primes is a sequence of primes, initially all of them
• divisorsFound is how we can represent the prime factors. Map key is a prime, and value is a factor.
• the return value is the number of divisors

Let’s take a look at the whole solution:

import scala.annotation.tailrec

object Euler012 extends EulerApp {
  override def execute(): Any = findTriangleNumber()

  private val primes: Seq[Int] =
    (2 to Math.sqrt(Integer.MAX_VALUE).toInt)
      .filter(EulerHelper.naiveIsPrime)

  @tailrec
  private def findTriangleNumber(n: Int = 1, k: Int = 2): Int =
    if (divisors(n) > 500) n
    else findTriangleNumber(n + k, k + 1)

  @tailrec
  private def divisors(
      n: Int,
      primes: Seq[Int] = primes,
      divisorsFound: Map[Int, Int] = Map.empty
  ): Int = {
    val prime = primes.head

    if (n % prime == 0) {
      val newFactor = divisorsFound.get(prime) match {
        case Some(factor) => factor + 1
        case None         => 1
      }
      divisors(
        n / prime,
        primes,
        divisorsFound + (prime -> newFactor)
      )
    } else if (prime > n) divisorsFound.foldLeft(1) { case (accumulator, (_, factor)) =>
      accumulator * (factor + 1)
    }
    else divisors(n, primes.tail, divisorsFound)
  }

}

It covers three cases:

if (n % prime == 0)

This condition is met when we’re processing a prime that can divide a number. It will result in the divisorsFound being updated.

else if (prime > n) 

If we hit a prime that’s higher or equal than n, then it’s time to calculate the divisors based on the divisorsFound map. Keep in mind that n decreases every time we find a new divisor.

In fact, we could also use a (n == 1) condition here.

else divisors(n, primes.tail, divisorsFound)

If previous conditions are both false, then it means that we simply need to check the next prime, because the current one is not a divisor and we’re not finished yet.

Closing notes

The solution is functional, it doesn’t mutate any of the collections it uses, but despite that it’s still pretty fast.

Obviously it could be faster, if, for example, instead of calling the primes.tail every time we want to move to the next prime number we simply maintained an index of which prime we’re processing.

Likewise, creating a new divisorsFound map after every change will be less efficient than reusing a single map and mutating it.