package com.martijndashorst.euler;

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.Test;

/**
 * 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:
 * 
 * <pre>
     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
 * </pre>
 * 
 * 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?
 */
public class Euler12 {
	@Test
	public void example() {
		assertThat(firstTriangleNumberWithOverNDivisors(5), is(28L));
	}
	@Test
	public void solution() {
		assertThat(firstTriangleNumberWithOverNDivisors(500), is(76_576_500L));
	}

	private long firstTriangleNumberWithOverNDivisors(int n) {
		int divisors = 0;
		int counter = 1;
		long triangle = 0;
		do {
			triangle = (counter * (counter + 1)) / 2;
			divisors = numberOfDivisors(triangle);
			counter++;
		} while (divisors < n);
		return triangle;
	}

	@Test
	public void nrOfDivisors1() {
		assertThat(numberOfDivisors(1), is(1));
		assertThat(numberOfDivisors(2), is(2));
		assertThat(numberOfDivisors(3), is(2));
		assertThat(numberOfDivisors(4), is(3));
		assertThat(numberOfDivisors(10), is(4));
		assertThat(numberOfDivisors(28), is(6));
	}

	private int numberOfDivisors(long n) {
		if (n == 1)
			return 1;
		if (n <= 3)
			return 2;

		long nr = (long) Math.sqrt(n);
		int nrOfDivisors = 2;
		for (int i = 2; i <= nr; i++) {
			if (n % i == 0) {
				nrOfDivisors += i == nr ? 1 : 2;
			}
		}
		return nrOfDivisors;
	}
}
