Project Euler 12: Highly divisible triangular number

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:

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?

Official Problem

Solution Approach

In this problem of Highly divisible triangular number, we are supposed to find the first triangle number to have over five hundred divisors. We are only concerned with the number of divisors not what they are.

The problem, the highest divisible triangular number can be divided into two parts – finding the triangular numbers and then finding the factors of those numbers. Let’s tackle both the parts one by one.

To find the triangular numbers, we can use arithmetic progression to find the sum of n natural numbers. The formula (which can be derived from Arithmetic progression) of the sum of n natural numbers is S = n(n + 1)/2. Using this we can change the n and find the respective sums and hence the triangular numbers.

Now that we found the triangular numbers we need to find the factors of a number. The number itself and 1 will always be a factor. To find other factors we iterate from 2 to half of the number, checking if the iterator is a factor. We also keep a variable to store the number of factors to check if that is five hundred or more. If it is then we simply return the number as the answer.

The time complexity of this approach is O(n²) as we are finding the triangle number and its factor in a nested loop. The space complexity is O(1) as we are using only a handful of variables that are independent of value n.

Coding Approach

Coming to the code of this approach, we initialize a variable to store the triangular number as we calculate. We start with n=1 and iterate till infinity simultaneously finding the triangle number using that n. We take that triangle number and send it to another method that finds out the number of divisors of that triangle number. Inside the method, we iterate through 2 to half of the number finding divisors and return the number of divisors. In the end, if the number of divisors is five hundred or more we end the infinite loop and return the number as the answer.

Solution Code

Java Solution

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution
{
	 public static void main(String []args){
        int triangleNumber = 0;
        int n = 2;
        int divisors = 0;
        while(divisors < 500){
            triangleNumber = (int) n*(n+1)/2;
            divisors = countDivisors(triangleNumber);
            n += 1;
        }
        System.out.println(triangleNumber);
     }
     
     private static int countDivisors(int number){
         int divisors = 2;
         int begin = 2;
         int end = number / 2 ;
         for(int i=begin; i<=end; i++){
             if(number % i == 0) divisors +=1;
         }
         return divisors;
     }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Solution

{

public static void main(String []args){

int triangleNumber = 0;

int n = 2;

int divisors = 0;

while(divisors < 500){

triangleNumber = (int) n*(n+1)/2;

divisors = countDivisors(triangleNumber);

n += 1;

}

System.out.println(triangleNumber);

}

private static int countDivisors(int number){

int divisors = 2;

int begin = 2;

int end = number / 2 ;

for(int i=begin; i<=end; i++){

if(number % i == 0) divisors +=1;

}

return divisors;

}

Python Solution

def count_divisors(number):
    divisor = 2
    begin = 2
    end = number // 2
    for i in range(begin, end + 1):
        if number % i == 0:
            divisor = divisor + 1
    return divisor


triangle_number = 0
n = 2
divisors = 0
while divisors < 500:
    triangle_number = n * (n + 1) // 2
    divisors = count_divisors(triangle_number)
    n = n + 1
print(triangle_number)

def count_divisors(number):

divisor = 2

begin = 2

end = number // 2

for i in range(begin, end + 1):

if number % i == 0:

divisor = divisor + 1

return divisor

triangle_number = 0

n = 2

divisors = 0

while divisors < 500:

triangle_number = n * (n + 1) // 2

divisors = count_divisors(triangle_number)

n = n + 1

print(triangle_number)

For more Project Euler explained solutions visit Project Euler Detailed Solutions.

For Leetcode detailed solutions go to Leetcode Detailed Solutions.

If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via the Contact page I will surely respond. Happy Coding.

Solution Approach

Coding Approach

Solution Code

Java Solution

Python Solution

Leave a Comment Cancel Reply