Project Euler | Problem 12 | Highly divisible triangular number

Problem Description:

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

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

Figure1

Concept:

If you know how to find triangular number and divisors of given number then you can easily solve this problem. Use below steps to solve it.

1. Find triangular number.
2. Find number of divisors of triangular number that we got in step 1.
3. If number of divisors are greater than 500, print triangular number otherwise continue.

Recommended:

What is triangular number and how to generate it?

How to find divisors of given number?

Java Program:

	package com.javamultiplex.projecteuler;
	import java.util.ArrayList;
	import java.util.List;
	/**
	*
	* @author Rohit Agarwal
	* @category Project Euler Problems
	* @Problem 12 - Highly divisible triangular number.
	*
	*/
	public class Problem12 {
	public static void main(String[] args) {
	int target = 500;
	long number = 1;
	long triangularNumber = 0;
	int count = 0;
	while (true) {
	/*
	* Step 1: Find the triangular number.
	*
	* As triangular number is generated by adding natural numbers so
	* Sum of first n natural number is = n(n+1)/2
	*
	*/
	triangularNumber = (number) * (number + 1) / 2;
	// Step 2: Get the number of divisors.
	count = getCountofDivisors(triangularNumber);
	// Step 3: If number of divisors > 500 then print it otherwise
	// continue.
	if (count > target) {
	System.out.println("The value of the first triangle number to have over five hundred divisors :" + triangularNumber);
	break;
	}
	number++;
	}
	}
	private static int getCountofDivisors(long triangularNumber) {
	long limit = (long) Math.sqrt(triangularNumber);
	List<Long> list = new ArrayList<>();
	long temp = 0;
	for (long i = 1; i <= limit; i++) {
	if (triangularNumber % i == 0) {
	list.add(i);
	temp = triangularNumber / i;
	if (i != temp) {
	list.add(temp);
	}
	}
	}
	int divisors = list.size();
	return divisors;
	}
	}

view raw Problem12.java hosted with ❤ by GitHub

Output:

Figure2

References:

https://projecteuler.net/problem=12

https://en.wikipedia.org/wiki/Triangular_number

Thank you friends, I hope you have clearly understood the solution of this problem. If you have any doubt, suggestion or query please feel free to comment below. You can also discuss this solution in our forum.

About Author:

I am simple guy with lot of ambitions. My main motive is to share whatever knowledge I have related to programming. With me you can easily learn how to solve any programming problem in Java.You can connect with me on social networking sites also.

Let's Get Connected: Linkedin | Facebook | Google Plus