Project Euler : Problem 12 - Highly divisible triangular number

Problem Statement : 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?

Concept and Theory

Triangular Numbers : The $Nth$ triangular number is the sum of continuous natural numbers from $1$ to $N$, below is the formula,

$$Nth \ Triangular \ Number \ = \ \frac{(N)(N+1)}{2}$$

As we all know that $1$ is the only common factor between two consecutive numbers. Hence one can find the factor of $N/2$ and $(N+1)$ or $N$ and $(N+1)/2$, and multiply them to get the total factor count. This will save us some time and also we will be able to avoid factoring a large number.

We have covered Prime Factorization methods in previous post.

Code for finding Nth Triangular Number

/**
 * A function to get the Nth Triangular number
 *
 * @param num Given number to test
 * @return return the nth Triangular number
 */
public static long getNthTriangularNumber(long num) {
  return (num * (num + 1)) / 2;
}

Code for this problem

public static int FactorCount(int limit) {
    int cnt = 0;
    int answer = 0;
    for (int i = 1; cnt <= limit; i++){
        if (i % 2 == 0) cnt = count(i / 2) * count (i+1);
        else cnt = count(i) * count((i+1)/2);
        //System.out.println("" + i + "\t" + cnt);
        if (cnt > limit){
            answer = i;
            break;
        }
    }
    return (answer*(answer+1))/2;
}



static int  count(int n) {
    int result = 0;
    for (int i = 1; i*i <= n; i++){
        if (n % i == 0) {
            result+=2;
            if (n / i == i)
                result--;
        }
    }
    return result;
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as given in the above mentioned post, $largestProductInAGrid$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler