[C/C++] Project Euler #44 - Pentagon Numbers

This problem requires us to generate a special type of number called pentagonal numbers.

A pentagonal number represents the number of points arranged in the shape of a pentagon.

For convenience, a diagram illustrating this can be included as follows.

 

N-gon Numbers

 

The formula for generating pentagonal numbers is given in the problem as follows:


\[P_n = \frac{n(3n-1)}{2}\]


Since pentagonal numbers increase monotonically, the goal of this problem is to find the smallest  P_s  that satisfies the following conditions:


\[P_s + P_t = P_u\]

\[P_t + P_u = P_v\]

---

A straightforward approach would be to iterate through values of  s  and  t to find a pair that satisfies these conditions. However, I approached the problem in a slightly more complex way.

N-gon numbers

Below is the source code that implements this approach. Feel free to use it as a reference.

//------------------------------------------------
//    Project Euler #44 - Pentagon Numbers
//        - by Aubrey Choi
//        - created at 2015-03-30
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>
#include <math.h>

int main()
{
    for( int64_t i = 2 ; ; i++ )
    {
        int64_t s = i*(3*i-1)/2;

        for( int64_t k = 1 ; k < i ; k++ )
        {
            int64_t t = s - k*(3*k-1)/2;
            if( t%(3*k) ) continue;
            int64_t c1 = t/(3*k);
            int64_t c2 = c1+k;
            int64_t t1 = c1*(3*c1-1)/2;
            int64_t m = (6*c2-1)*(6*c2-1)+24*t1;
            int64_t c = sqrt((double)m);
            if( c*c != m && (c+1)*(c+1) != m ) continue;
            c -= 6*c2-1;
            if( c <= 0 || c%6 ) continue;
            printf("ans = %jd\n", s);
            return 0;
        }
    }
}