Project Euler

Problem 12: 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: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... Let us list the factors of the first seven triangle numbers. 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?
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

The Catch

How to find all of the divisors of an arbitrary number x.

The Light

Using similar idea from Problem 3, we only need to check numbers from 1 to sqrt(x) and times the answer by 2 to get x's total numbers of divisors.

Example: How many divisors does 360 have?
Check numbers from 1 to sqrt(360) = 18.97.
From 1 to 18.97, 360 has 12 divisors (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18). Thus, 360 has a total of 24 divisors (1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360).

There is an even better way to calculate the number of divisors the number x has: prime factorization. A positive number x can be written as the product of primes:

• Divide x by the first prime, 2, until x is no longer divisible by 2.
• Repeat with the next lowest prime number until x gets reduced to 1.
• Write the prime factors into exponent forms.
• Add 1 to each exponent and find their product, which is the total number of divisors.

Example: Find 360's total number of divisors.
360/2 = 180
180/2 = 90
90/2 = 45 (No longer divisible by 2, move on to 3)
45/3 = 15
15/3 = 5 (No longer divisible by 3, move on to 5)
5/5 = 1 (x gets reduced to 1, stop)
So 360 = 2³ * 3² * 5¹
Total number of divisors = (3 + 1) * (2 + 1) * (1 + 1) = 24

Prime factorization requires a pre-calculated list of prime, which can be achieved by Sieve of Eratosthenes as discussed in Problem 35.

The Code

import java.util.*;

public class Problem12
{    
  static List primeList = generatePrimes(100000);

  public static void main(String[] args)
  {
    long triNum = 0;

    for( int i = 1;; i++ )
    {
      triNum += i;
      if(primeFactorize(triNum) > 500)
      {
        System.out.println(triNum);
        break;
      }	  
    }
  }

  public static int primeFactorize(long n)
  {
    int index = 0;
    int divisors = 1;

    while(n > 1)
    {
      int count = 0;
      while(n % primeList.get(index) == 0)
      {
        count++;
    	n /= primeList.get(index);
      }
      divisors *= ++count;
      index++;
    }

    return divisors;
  }

  public static List generatePrimes(int max) 
  {
    boolean[] isComposite = new boolean[max + 1];
    for (int i = 2; i * i <= max; i++) 
    {
      if (!isComposite [i]) 
        for (int j = i; i * j <= max; j++) 
        {
          isComposite [i*j] = true;
        }
    }   
    ArrayList list = new ArrayList();

    for (int i = 2; i <= max; i++)  
    {
      if (!isComposite [i]) 
        list.add(new Integer(i));
    }
    return list;
  }
}