Detailed mathematical approach

Problem Summary

Triangular, pentagonal, and hexagonal numbers are given by \(T_n=\frac{n(n+1)}{2}\), \(P_n=\frac{n(3n-1)}{2}\), and \(H_n=n(2n-1)\). The problem states that \(40755\) is simultaneously triangular, pentagonal, and hexagonal, and asks for the next number with the same property.

The implementations do not search all three families independently. They exploit a structural identity between triangular and hexagonal numbers, then scan only hexagonal candidates and apply an exact pentagonal test.

Mathematical Approach

The whole strategy is to turn a three-condition search into a one-dimensional scan with a precise arithmetic predicate.

Hexagonal Numbers Are Already Triangular

The first reduction is immediate:

$H_n=n(2n-1)=\frac{(2n-1)(2n)}{2}=T_{2n-1}.$

So every hexagonal number is automatically triangular. That means a number is triangular, pentagonal, and hexagonal exactly when it is both hexagonal and pentagonal. The triangular test disappears entirely.

This is the key invariant used by the code: once a candidate is generated in hexagonal form, one of the three required properties is already guaranteed.

An Exact Test for Pentagonality

To test whether a number \(x\) is pentagonal, start from

$x=P_k=\frac{k(3k-1)}{2}.$

Multiply by \(24\) and add \(1\):

$24x+1=12k(3k-1)+1=36k^2-12k+1=(6k-1)^2.$

Therefore \(x\) is pentagonal if and only if \(24x+1\) is a perfect square and the corresponding index

$k=\frac{1+\sqrt{24x+1}}{6}$

is an integer. This is exactly the arithmetic condition used in the three implementations.

The important detail is that the square root alone is not trusted as a final answer. After computing a floating-point square root and rounding the implied index, the implementation substitutes that integer back into \(\frac{k(3k-1)}{2}\) and checks whether it reconstructs \(x\) exactly.

Why the Search Starts at \(n=144\)

The known common value in the statement is

$H_{143}=143(2\cdot 143-1)=143\cdot 285=40755.$

Because the task asks for the next such number, the scan begins with the next hexagonal index, \(n=144\).

The hexagonal sequence is strictly increasing for positive \(n\). In fact,

$H_{n+1}-H_n=(n+1)(2n+1)-n(2n-1)=4n+1 \gt 0.$

So once the loop moves past \(n=143\), the first candidate that also passes the pentagonal test must be the next desired number.

Worked Example

The given example \(40755\) is a good checkpoint. Since

$24\cdot 40755+1=978121=989^2,$

we get

$k=\frac{1+989}{6}=165,$

so \(40755=P_{165}\). Combined with \(40755=H_{143}\) and \(H_n=T_{2n-1}\), it is indeed a member of all three families.

The very next hexagonal candidate is

$H_{144}=144(287)=41328.$

For this value, \(24\cdot 41328+1=991873\), which is not a perfect square, so the candidate fails immediately. This is exactly the kind of fast rejection that makes the linear scan practical.

How the Code Works

Generate Only Relevant Candidates

The C++, Python, and Java implementations iterate the hexagonal index upward from \(144\). For each step they compute the current candidate as \(n(2n-1)\). No triangular check is performed, because the identity \(H_n=T_{2n-1}\) has already removed that part of the problem.

Apply a Safe Pentagonal Predicate

For each candidate \(x\), the implementation forms the discriminant-like value \(1+24x\), takes its square root, converts the implied pentagonal index to the nearest integer, and then verifies the result exactly by rebuilding \(\frac{k(3k-1)}{2}\). That last exact reconstruction is what makes the test robust even though the intermediate square root is computed in floating point.

Stop at the First Success

Because the candidates are examined in increasing hexagonal index, the first passing value is automatically the next common number after \(40755\). The C++ and Java implementations also include small checkpoint tests before the full search: the known value \(40755\) must pass the pentagonal test, while \(40756\) must fail.

Complexity Analysis

Each loop iteration performs a constant amount of arithmetic and one square-root computation, so the cost per candidate is \(O(1)\). If the next solution occurs at hexagonal index \(N\), the total running time is \(O(N-143)\).

Memory usage is \(O(1)\), since the algorithm stores only a few numeric variables and does not build tables, arrays, or recursion stacks. The main optimization is conceptual rather than structural: the search is efficient because it generates only hexagonal numbers and uses a direct arithmetic test for pentagonality.

Footnotes and References

1. Project Euler, Problem 45: https://projecteuler.net/problem=45
2. Polygonal number: Wikipedia - Polygonal number
3. Triangular number: Wikipedia - Triangular number
4. Pentagonal number: Wikipedia - Pentagonal number
5. Hexagonal number: Wikipedia - Hexagonal number
6. Quadratic equation: Wikipedia - Quadratic equation