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:
- Generate triangle numbers using the formula: T(n) = n(n+1)/2
- For each triangle number, count its divisors
- 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).