Detailed mathematical approach

Problem Summary

We seek six distinct 4-digit figurate numbers, one from each of the triangular, square, pentagonal, hexagonal, heptagonal, and octagonal families. They must form a cycle: the last two digits of each number must equal the first two digits of the next, and the sixth number must link back to the first.

The problem is small enough to solve by exhaustive search, but only after we turn the infinite figurate sequences into a finite candidate set and exploit the strong prefix-suffix constraint. The implementations therefore generate all admissible 4-digit values and then search recursively for a six-term cycle that uses each family exactly once.

Mathematical Approach

The six figurate families used in the problem are

\[ T_n=\frac{n(n+1)}{2}, \quad S_n=n^2, \quad P_n=\frac{n(3n-1)}{2}, \quad H_n=n(2n-1), \quad \operatorname{Hp}_n=\frac{n(5n-3)}{2}, \quad O_n=n(3n-2). \]

For each family we only care about values in the interval \(1000 \le x \le 9999\), because the cycle must be built from 4-digit numbers.

Admissible 4-digit figurate numbers

Solving the inequalities \(1000 \le x \le 9999\) for each formula shows that only finitely many indices matter: triangular numbers come from \(45 \le n \le 140\), squares from \(32 \le n \le 99\), pentagonal numbers from \(26 \le n \le 81\), hexagonal numbers from \(23 \le n \le 70\), heptagonal numbers from \(21 \le n \le 63\), and octagonal numbers from \(19 \le n \le 58\).

There is one further restriction hidden in the wording of the problem. If a number ends in \(03\), then its suffix is not a genuine two-digit prefix for the next 4-digit number. For that reason the search keeps only candidates whose first two digits and last two digits both lie between 10 and 99.

Prefix-suffix compatibility

For any admissible 4-digit value \(x\), define

\[ p(x)=\left\lfloor \frac{x}{100} \right\rfloor, \qquad s(x)=x \bmod 100. \]

A chain \(x_1,x_2,\dots,x_6\) is cyclic exactly when

\[ s(x_i)=p(x_{i+1}) \quad (1 \le i \le 5), \qquad s(x_6)=p(x_1). \]

The type condition is just as important: one term must come from each figurate family. Some values belong to more than one family, so the mathematically correct object is a typed candidate, not just an integer by itself. The search therefore tracks which families have been used, not merely which numeric values have appeared.

Why the search space is finite and sparse

Once the admissible lists are generated, the problem becomes a depth-6 backtracking search. At each step two invariants matter: the next candidate must come from an unused family, and its prefix must equal the current required two-digit suffix.

These conditions prune the tree very aggressively. Although there are several dozen candidates in each family, a fixed two-digit prefix usually matches only a small handful of them and often none at all. Most branches therefore die after only a few steps, so the brute-force search becomes practical without any deeper number-theoretic machinery.

Worked cycle example

A full valid cycle is

\[ 8256 \rightarrow 5625 \rightarrow 2512 \rightarrow 1281 \rightarrow 8128 \rightarrow 2882 \rightarrow 8256. \]

Here the six roles are triangular, square, heptagonal, octagonal, hexagonal, and pentagonal respectively. The two-digit links are easy to verify:

\[ 82\vert 56,\; 56\vert 25,\; 25\vert 12,\; 12\vert 81,\; 81\vert 28,\; 28\vert 82. \]

This example shows exactly what the search is looking for: six typed figurate numbers, each from a different family, whose suffix-prefix relations close into one directed loop.

The closing invariant

After five successful links, the recursion has already fixed the order of all six families and all six values. At that point only one condition remains: the suffix of the last chosen number must equal the prefix of the first chosen number. If that equality holds, the chain is a genuine cycle and its sum is the desired answer.

How the Code Works

Generating the candidate lists

The C++, Python, and Java implementations evaluate each figurate formula for increasing \(n\) until the values exceed 9999. Every 4-digit value is split into a prefix and suffix, and values with a one-digit prefix or suffix are discarded immediately. What remains is a small list of admissible candidates for each of the six families.

Recursive search state

The implementation keeps a recursion state consisting of the families already used, the suffix required for the next step, the first prefix in the chain, and the running sum of the chosen values. On the first move there is no suffix restriction yet; after that, every new choice must start with the previous suffix. Because a family can be used at most once, the recursion depth is exactly six.

Detecting and returning the solution

When six candidates have been chosen, the implementation checks whether the current suffix equals the first prefix. If so, the chain closes and the accumulated sum is stored as the answer. The search then stops immediately, which is justified here because the problem instance has a unique solution up to rotation.

Complexity Analysis

If \(N_3,N_4,N_5,N_6,N_7,N_8\) denote the numbers of admissible 4-digit candidates in the six families, preprocessing costs

\[ O(N_3+N_4+N_5+N_6+N_7+N_8), \]

since each list is generated once.

The search is exponential in the worst case, but the depth is fixed at 6 and the prefix condition makes the practical search tree very small. A loose upper bound is obtained by trying every family order and every candidate in that order, while the real run time is far lower because most partial chains cannot be extended. Memory usage is \(O(N_3+\cdots+N_8)\) for the stored candidate lists plus \(O(6)\) recursion depth.

Footnotes and References

1. Problem page: Project Euler 61
2. Polygonal numbers: Wikipedia - Polygonal number
3. Figurate numbers: Wikipedia - Figurate number
4. Backtracking: Wikipedia - Backtracking
5. Depth-first search: Wikipedia - Depth-first search