/* Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:
 *
 * Triangle	 	   T_n=n(n+1)/2	 	1, 3, 6, 10, 15, ...
 * Pentagonal	 	P_n=n(3n−1)/2	1, 5, 12, 22, 35, ...
 * Hexagonal	 	H_n=n(2n−1)	 	1, 6, 15, 28, 45, ...
 *
 * It can be verified that T_285 = P_165 = H_143 = 40755.
 *
 * Find the next triangle number that is also pentagonal and hexagonal.*/

#define _POSIX_C_SOURCE 199309L

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include "projecteuler.h"

int main(int argc, char **argv)
{
    int found = 0;
    long int i, n;
    double elapsed;
    struct timespec start, end;

    clock_gettime(CLOCK_MONOTONIC, &start);

    i = 143;

    while(!found)
    {
        i++;
        /* Hexagonal numbers are also triangle numbers, so it's sufficient
         * to generate hexagonal numbers (starting from H_144) and check if
         * they're also pentagonal.*/
        n = i * (2 * i - 1);

        if(is_pentagonal(n))
        {
            found = 1;
        }
    }

    clock_gettime(CLOCK_MONOTONIC, &end);

    elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;

    printf("Project Euler, Problem 45\n");
    printf("Answer: %ld\n", n);

    printf("Elapsed time: %.9lf seconds\n", elapsed);

    return 0;
}