Project Euler: #12 - Highly divisible triangular number

Problem

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 5 divisors.

What is the value of the first triangle number to have over five hundred divisors?

Problem Description

The triangular number sequence is the representation of the numbers in the form of an equilateral triangle arranged in a series or sequence.

The sum of the previous number and the order of the succeeding number results in the sequence of triangular numbers.

Given in the problem is an example of factors of the first 7 triangular sequence numbers. The triangular Number 28 which is the 7th has 6 factors/divisors. This is the first triangular number in the sequence that has more than 5 divisors.

We need to find the first triangular number that has over 500 divisors.

Approach

This is an interesting problem involving triangular numbers.

More on triangular numbers on this wiki page.

If we are to find the nth triangular number, then we can use the formula,

$$T_n = \frac{n(n + 1)}{2}$$

But we don't need the nth number, instead, we need to find the number with over 500 divisors.

We can approach this in two steps.

Find the triangular number n
Find the number of divisors of n and if the count is greater than or equals 500, then print that number n.

For finding the triangular number of n, we can either use the formula above or can use a global variable to add all the previous triangular numbers till n.

For getting all the divisors of n, we can iterate through i <= sqrt(n) instead of i <= n. For every valid divisor i, there is another divisor j, as j = n/i. More on this algorithm at finding the proper divisor of n

Count the divisors of n and when it is greater than or equals 500, then that is our Answer.

Note: Please note that the solution provided is only for learning purposes. Once you understand the problem, please try it on your own before referring to my solution below.

Solution

const properDivisors = n => {
    let divisorsArr = [1];

    for (let i = 2; i * i <= n; i++) {
        if (n % i === 0) {
            divisorsArr.push(i, n / i);
            if (i === Math.sqrt(n)) { 
                divisorsArr.pop();
            }
        }
    }
    return divisorsArr.sort(function (a, b) { return a - b; });
}

const findTriangularNum = n => (n * (n + 1)) / 2;

const findDivTriNum = nDivs => {
    let i = 1,
        triNum = 0;
    while (true) {
        let divCount = 0;

        // Either use formula or a simple addition of previous numbers.
        //triNum = findTriangularNum(i); 
        triNum += i;
        divCount = properDivisors(triNum).length;

        if (divCount >= nDivs) return triNum;

        i += 1;
    }
}

console.log(findDivTriNum(500));

You can find my solution on GitHub 12

For Hackerrank, I have modified the above code slightly to pass all the test cases. The test cases involve finding the first triangle number to have over N divisors, where 1 <= N <= 1000. So, instead of finding the triangle number starting from 1 for each test case, made use of the upper bound given. You can find Hackerrank Solution on GitHub.

If you have any feedback, please leave it below.

If you have any suggestions to improve my code or another way to approach this problem, leave it in the comment.

For the other Project Euler Solutions, please follow the series Project Euler Solutions in JS.

Thank you!

Project Euler: #12 - Highly divisible triangular number

Comments

Project Euler: JS Solution Explained!

Project Euler: #13 - Large sum

More from this blog

What is JavaScript and How It Powers Modern Websites

Project Euler: #17 - Number letter counts

Project Euler: #16 - Power digit sum

Project Euler: #15 - Lattice paths

Project Euler: #14 - Longest Collatz sequence

Problem

Problem Description

Approach

Solution

Command Palette

Comments

Project Euler: JS Solution Explained!

Project Euler: #13 - Large sum

More from this blog

Problem

Problem Description

Approach

Solution