Solution to Project Euler Problem 12: Highly divisible triangular number - 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?

• Java Code

package sikademy;
/**
 *
 * @author Archangel Macsika
 * Copyright (c) Sikademy. All rights reserved
 */

public class SikademyEulerSolution {
	
	public String run() {
		int triangle = 0;
		for (int i = 1; ; i++) {
			if (Integer.MAX_VALUE - triangle < i)
				throw new ArithmeticException("Overflow");
			triangle += i;  
			if (countDivisors(triangle) > 500)
				return Integer.toString(triangle);
		}
	}
	
        public static int sqrt(int x) {
		if (x < 0)
			throw new IllegalArgumentException("Square root of negative number");
		int y = 0;
		for (int i = 1 << 15; i != 0; i >>>= 1) {
			y |= i;
			if (y > 46340 || y * y > x)
				y ^= i;
		}
		return y;
	}
	
	// Returns the number of integers in the range [1, n] that divide n.
	private static int countDivisors(int n) {
		int count = 0;
		int end = sqrt(n);
		for (int i = 1; i < end; i++) {
			if (n % i == 0)
				count += 2;
		}
		if (end * end == n)  // Perfect square
			count++;
		return count;
	}

	public static void main(String[] args) {
                SikademyEulerSolution solution = new SikademyEulerSolution();
		System.out.println(solution.run());
	}	
}

• Python Code

# 
# @author Archangel Macsika
# Copyright (c) Sikademy. All rights reserved.
# 

import itertools


def sqrt(x):
	assert x >= 0
	i = 1
	while i * i <= x:
		i *= 2
	y = 0
	while i > 0:
		if (y + i)**2 <= x:
			y += i
		i //= 2
	return y

def compute():
	triangle = 0
	for i in itertools.count(1):
		triangle += i  # This is the ith triangle number, i.e. num = 1 + 2 + ... + i = i * (i + 1) / 2
		if num_divisors(triangle) > 500:
			return str(triangle)


# Returns the number of integers in the range [1, n] that divide n.
def num_divisors(n):
	end = sqrt(n)
	result = sum(2
		for i in range(1, end + 1)
		if n % i == 0)
	if end**2 == n:
		result -= 1
	return result


if __name__ == "__main__":
	print(compute())