[C/C++] Project Euler #45 - Triangular, Pentagonal, and Hexagonal

Project Euler problem #45 explores the relationships among specific numerical sequences.

 

This problem involves the concepts of triangular numbers, pentagonal numbers, and hexagonal numbers. A triangular number is defined as the sum of natural numbers and can be expressed using the formula \(T_n = \frac{n(n+1)}{2}\) . A pentagonal number follows a specific pattern of growth among polygonal numbers and is given by the formula \(P_n = \frac{n(3n-1)}{2}\) . A hexagonal number follows a regular hexagonal pattern and is defined using the formula \(H_n = n(2n-1)\) .

 

The goal of this problem is to find the intersection of these three sequences. The given example states that \(T_{285} = P_{165} = H_{143} = 40755\) is the only common number provided. The objective is to find the next number that is common among triangular, pentagonal, and hexagonal numbers, greater than 40755.

 

To solve this, we need to generate these three sequences and compare them. An efficient approach involves utilizing specific patterns to reduce redundant computations.

---

Triangular, pentagonal, and hexagonal numbers correspond to the number of points that appear when drawing specific geometric shapes, as explained in problem #44 (http://odev.tistory.com/75)

 

One can take different approaches, either using triangular numbers as the base and matching the others or using hexagonal numbers as the base and matching the rest. In my case, I first matched triangular and pentagonal numbers and then adjusted the hexagonal number accordingly. For example, if both triangular and pentagonal numbers reach a common value a , I increment the hexagonal sequence to match this value. If the hexagonal number surpasses a , I increase the triangular number.

 

Using arithmetic sequences simplifies the calculations. Since a triangular number is the sum of numbers from 1 to N , its common difference is N , meaning that the difference increases by 1 at each step. A pentagonal number increases by 3, while a hexagonal number increases by 4.

---

Triangular Number

Based on this logic, the following code was created:

//------------------------------------------------
//    Project Euler #45 - Triangular, Pentagonal, and Hexagonal
//        - by Aubrey Choi
//        - created at 2015-03-29
//------------------------------------------------
#include <stdio.h>
#include <stdint.h>

int main()
{
    uint64_t t = 40755, p = 40755, h = 40755;
    uint64_t dt = 286, dp = 496, dh = 573;

    t += dt; dt++;
    while( 1 )
    {
        if( t < p ) { t += dt; dt++; }
        else if( p < t ) { p += dp; dp += 3; }
        else if( h < p ) { h += dh; dh += 4; }
        else if( t < h ) { t += dt; dt++; }
        else break;
    }
    printf("ans = %ju\n", t);
}