Problem 012 : Highly Divisible Triangular Number

Highly divisible triangular number

Problem 12

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:

 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?

                                                                                                       (https://projecteuler.net/problem=12)

We have a problem about triangular number, so let's go over the formula first.

The formula to get nth triangular number is n * (n + 1) / 2, which is faster than adding consecutive integers.


Now, how can we get the number of factors?

If we remember our learning from Algebra class, we can instantly know that:

if our number n is:

n=∏k=1Npakk

then

#factors(n)=∏k=1N(ak+1)

If you don't understand the formula because you don't know the Pi function, then here is an example for you:

36 has 9 factors total: 1, 2, 3, 4, 6, 9, 12, 18, 36.

And 36 prime factorization is 36 = 2² x 3².

Then we use our exponents to calculate. (2 + 1) x ( 2 + 1) = 9, or 9 factors total.

Our implementation of the logic is here:

public static int countFactor(int n)
{
 int count = 0, two = 1;
 while (n%2 == 0)
 {
  two++;
  n/=2;
 }
 int sqrt = (int) Math.sqrt(n);
 for (int i = 1; i <= sqrt; i+=2)
  if (n%i == 0) count += 2;
 if (n == sqrt*sqrt) count--;
 return count*two;
}

Now, it becomes dramatically easy problem.

The one thing I did to improve the efficiency is that instead of putting the original triangular number into the function, I used our formula n * (n + 1) / 2 to divide the number into two components.

Calculating factors for the large number will take a long time, yet getting factors for two sub-numbers and multiplying the total number is way faster and easier to calculate.

int i=1;
for (int count = 0; count <= 500; i++)
{
 if (i%2 == 1) count = countFactor((i+1)/2)*countFactor(i);
 else count = countFactor(i/2)*countFactor(i+1);
}

Answer is 76576500
Execution time is 8.203672 ms
Source Code: https://github.com/Ainodyne/Project-Euler/blob/master/Problem012.java