Problem #12 Difficulty: 5%

Highly Divisible Triangular Number

Solution Language: Java

Problem Statement

The sequence of triangle numbers is generated by adding the natural numbers. The 7th triangle number is 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28.

The first ten terms are: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, …

The divisors of the 7th triangle number (28) are: 1, 2, 4, 7, 14, 28. This number has 6 divisors.

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

Approach

To solve this problem:

  1. Generate triangle numbers using the formula: T(n) = n(n+1)/2
  2. For each triangle number, count its divisors
  3. Stop when we find a triangle number with more than 500 divisors

To count divisors efficiently:

  • Find all prime factors and their powers
  • Use the formula: if n = p₁^a₁ × p₂^a₂ × … × pₖ^aₖ, then the number of divisors = (a₁+1)(a₂+1)…(aₖ+1)

Optimization: Since T(n) = n(n+1)/2, and n and (n+1) are coprime, we can count divisors of n and (n+1) separately and combine the results (adjusting for the factor of 2).