Problem #12 medium

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, \dots$

Let us list the factors of the first seven triangle numbers:

\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?

View on Project Euler

Implementations

// https://projecteuler.net/problem=12
// 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, ...
//
// 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?

// Answer: 76576500

#include <iostream>
#include <algorithm>

// @see http://en.wikipedia.org/wiki/Triangular_number
int triangle(int n)
{
  if( 1 == n ){
    return 3;
  }
  return ((n+1)*n)/2;
}

// Math fact: a prime decomposition n = Prod_i p_i^e_i yields
// Prod_i (e_i + 1) different divisors
int num_divisors(int n)
{
  int divisors = 1;

  // Evens
  {
    int count = 0;
    while ( 0 == (n % 2)) {
      ++count;
      n /= 2;
    }
    divisors *= (count + 1);
  }

  // Odds
  for (size_t i = 3; i <= n; i += 2){
    int count = 0;
    while ( 0 == (n % i) ) {
      ++count;
      n /= i;
    }
    divisors *= (count + 1);
  }

  return divisors;
}

int find_highest_divisible_triangular_number( int hurdle )
{
  int divisor_count = 0;
  int i = 1;

  while( divisor_count <= hurdle ){
    divisor_count = num_divisors(triangle(i));
    i++;
  }
  return triangle(i-1);
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
  std::cout << "Answer: " << find_highest_divisible_triangular_number(500) << std::endl;
}
#endif // #if ! defined UNITTEST_MODE

View on GitHub

O(n) time complexity

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;

public class Solution012 implements Solution {
  public String solve() {
    long n = 1;
    while (true) {
      long triangle = n * (n + 1) / 2;
      if (countDivisors(triangle) > 500) {
        return Long.toString(triangle);
      }
      n++;
    }
  }

  private int countDivisors(long number) {
    int count = 0;
    for (long i = 1; i * i <= number; i++) {
      if (number % i == 0) {
        count += (i * i == number) ? 1 : 2;
      }
    }
    return count;
  }
}

View on GitHub

def solve():
    """
    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 number 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?
    """
    def num_divisors(n):
        count = 0
        for i in range(1, int(n**0.5) + 1):
            if n % i == 0:
                count += 2 if i != n // i else 1
        return count

    i = 1
    triangle = 0
    while True:
        triangle += i
        if num_divisors(triangle) > 500:
            return triangle
        i += 1

View on GitHub

require_relative './core_extensions/integer/divisors'

# @see http://en.wikipedia.org/wiki/Triangular_number
def triangle(num)
  return 3 if num == 1

  ((num + 1) * num) / 2
end

def highest_divisible_triangular_number(stop)
  i = 1
  i += 1 while triangle(i).divisor_count < stop
  triangle(i)
end

puts highest_divisible_triangular_number(500) if __FILE__ == $PROGRAM_NAME

View on GitHub

// https://projecteuler.net/problem=12
//
// 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, ...
//
// 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?
//
// Answer: 76576500

fn divisor_count(n: u64) -> usize {
    let mut count = 0;
    let sqrt_n = (n as f64).sqrt() as u64;
    for i in 1..=sqrt_n {
        if n % i == 0 {
            count += 2;
            if i == n / i {
                count -= 1;
            }
        }
    }
    count
}

pub fn highly_divisible_triangular_number(min_divisors: usize) -> u64 {
    let mut n = 1u64;
    loop {
        let triangular = n * (n + 1) / 2;
        if divisor_count(triangular) > min_divisors {
            return triangular;
        }
        n += 1;
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn euler_012() {
        assert_eq!(highly_divisible_triangular_number(5), 28);
        assert_eq!(highly_divisible_triangular_number(500), 76_576_500);
    }
}

View on GitHub

// https://projecteuler.net/problem=12
// 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, ...
//
// 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?

// Answer: 76576500

#include <iostream>
#include <algorithm>

// @see http://en.wikipedia.org/wiki/Triangular_number
int triangle(int n)
{
  if( 1 == n ){
    return 3;
  }
  return ((n+1)*n)/2;
}

// Math fact: a prime decomposition n = Prod_i p_i^e_i yields
// Prod_i (e_i + 1) different divisors
int num_divisors(int n)
{
  int divisors = 1;

  // Evens
  {
    int count = 0;
    while ( 0 == (n % 2)) {
      ++count;
      n /= 2;
    }
    divisors *= (count + 1);
  }

  // Odds
  for (size_t i = 3; i <= n; i += 2){
    int count = 0;
    while ( 0 == (n % i) ) {
      ++count;
      n /= i;
    }
    divisors *= (count + 1);
  }

  return divisors;
}

int find_highest_divisible_triangular_number( int hurdle )
{
  int divisor_count = 0;
  int i = 1;

  while( divisor_count <= hurdle ){
    divisor_count = num_divisors(triangle(i));
    i++;
  }
  return triangle(i-1);
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
  std::cout << "Answer: " << find_highest_divisible_triangular_number(500) << std::endl;
}
#endif // #if ! defined UNITTEST_MODE

View on GitHub

O(n) time complexity

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;

public class Solution012 implements Solution {
  public String solve() {
    long n = 1;
    while (true) {
      long triangle = n * (n + 1) / 2;
      if (countDivisors(triangle) > 500) {
        return Long.toString(triangle);
      }
      n++;
    }
  }

  private int countDivisors(long number) {
    int count = 0;
    for (long i = 1; i * i <= number; i++) {
      if (number % i == 0) {
        count += (i * i == number) ? 1 : 2;
      }
    }
    return count;
  }
}

View on GitHub

function countDivisors(n) {
  let count = 0;
  for (let i = 1; i <= Math.sqrt(n); i++) {
    if (n % i === 0) {
      count += (i === n / i) ? 1 : 2;
    }
  }
  return count;
}

module.exports = {
  answer: () => {
    let n = 1;
    while (true) {
      const triangle = n * (n + 1) / 2;
      if (countDivisors(triangle) > 500) {
        return triangle;
      }
      n++;
    }
  }
};

View on GitHub

def solve():
    """
    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 number 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?
    """
    def num_divisors(n):
        count = 0
        for i in range(1, int(n**0.5) + 1):
            if n % i == 0:
                count += 2 if i != n // i else 1
        return count

    i = 1
    triangle = 0
    while True:
        triangle += i
        if num_divisors(triangle) > 500:
            return triangle
        i += 1

View on GitHub

require_relative './core_extensions/integer/divisors'

# @see http://en.wikipedia.org/wiki/Triangular_number
def triangle(num)
  return 3 if num == 1

  ((num + 1) * num) / 2
end

def highest_divisible_triangular_number(stop)
  i = 1
  i += 1 while triangle(i).divisor_count < stop
  triangle(i)
end

puts highest_divisible_triangular_number(500) if __FILE__ == $PROGRAM_NAME

View on GitHub

package main

import "fmt"

func numDivisors(n int) int {

    count := 0

    for i := 1; i*i <= n; i++ {

        if n%i == 0 {

            count += 2

            if i*i == n {

                count--

            }

        }

    }

    return count

}

func main() {

    n := 1

    triangular := 0

    for {

        triangular += n

        if numDivisors(triangular) > 500 {

            fmt.Println(triangular)

            break

        }

        n++

    }

}

View on GitHub

// https://projecteuler.net/problem=12
//
// 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, ...
//
// 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?
//
// Answer: 76576500

fn divisor_count(n: u64) -> usize {
    let mut count = 0;
    let sqrt_n = (n as f64).sqrt() as u64;
    for i in 1..=sqrt_n {
        if n % i == 0 {
            count += 2;
            if i == n / i {
                count -= 1;
            }
        }
    }
    count
}

pub fn highly_divisible_triangular_number(min_divisors: usize) -> u64 {
    let mut n = 1u64;
    loop {
        let triangular = n * (n + 1) / 2;
        if divisor_count(triangular) > min_divisors {
            return triangular;
        }
        n += 1;
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn euler_012() {
        assert_eq!(highly_divisible_triangular_number(5), 28);
        assert_eq!(highly_divisible_triangular_number(500), 76_576_500);
    }
}

View on GitHub

Solution Notes

Mathematical Background

Triangular numbers are generated by the formula $T_n = \frac{n(n+1)}{2}$ . They represent the sum of the first n natural numbers and form a quadratic sequence.

The number of divisor function $d(n)$ counts how many positive divisors n has. For a number with prime factorization $n = p_1^{a_1} \times p_2^{a_2} \times \dots \times p_k^{a_k}$ , the number of divisors is $d(n) = (a_1 + 1)(a_2 + 1) \dots (a_k + 1)$ .

Highly composite numbers (numbers with many divisors) often result from having many small prime factors. Triangle numbers can be highly composite because they may share factors with many other numbers.

Algorithm Analysis

The implementations combine two key components:

Triangle number generation: $T_n = \frac{n(n+1)}{2}$ computed incrementally or via formula.

Divisor counting: Factorize each triangle number and compute $d(n) = \prod (e_i + 1)$ where $e_i$ are exponents in prime factorization.

Optimization: Check divisors of $T_n$ by factoring $T_n$ directly, often more efficient than checking all numbers up to $T_n$ .

Time complexity depends on factorization efficiency. For large triangle numbers, fast factorization methods become crucial.

Key Insights

Triangle numbers can be written as $T_n = \frac{n(n+1)}{2}$ , where n and n+1 are coprime
The number with the most divisors below a certain size is often a triangle number
76576500 = T_{12375} has exactly 576 divisors (> 500)
The search requires checking increasingly large triangle numbers until one has >500 divisors
Most triangle numbers have relatively few divisors, but highly composite ones are well-distributed
This problem demonstrates the connection between additive sequences and multiplicative properties

Educational Value

This problem teaches fundamental concepts in:

Number theory and divisor functions
Prime factorization and its applications
The relationship between different number sequences
Algorithm efficiency for computational number theory
The mathematical properties of highly composite numbers
How additive and multiplicative properties interact in number sequences