Problem 61: Cyclical Figurate Numbers
View on Project EulerProject Euler Problem 61 Solution
EulerSolve provides an optimized solution for Project Euler Problem 61, Cyclical Figurate Numbers, with C++, Python, Java, and a step-by-step mathematical explanation.
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....
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
- Problem page: Project Euler 61
- Polygonal numbers: Wikipedia - Polygonal number
- Figurate numbers: Wikipedia - Figurate number
- Backtracking: Wikipedia - Backtracking
- Depth-first search: Wikipedia - Depth-first search
Problem 61 source code
C++
#include <array>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
namespace {
using i64 = std::int64_t;
struct Options {
bool run_checkpoints = true;
};
bool parse_arguments(int argc, char** argv, Options& options) {
for (int i = 1; i < argc; ++i) {
const std::string arg(argv[i]);
if (arg == "--skip-checkpoints") {
options.run_checkpoints = false;
continue;
}
std::cerr << "Unknown argument: " << arg << '\n';
return false;
}
return true;
}
i64 polygonal(const int type, const int n) {
switch (type) {
case 3:
return static_cast<i64>(n) * (n + 1) / 2;
case 4:
return static_cast<i64>(n) * n;
case 5:
return static_cast<i64>(n) * (3 * n - 1) / 2;
case 6:
return static_cast<i64>(n) * (2 * n - 1);
case 7:
return static_cast<i64>(n) * (5 * n - 3) / 2;
case 8:
return static_cast<i64>(n) * (3 * n - 2);
default:
return -1;
}
}
std::vector<int> generate_four_digit_values(const int type) {
std::vector<int> values;
for (int n = 1;; ++n) {
const i64 x = polygonal(type, n);
if (x > 9999) {
break;
}
if (x >= 1000) {
const int value = static_cast<int>(x);
const int prefix = value / 100;
const int suffix = value % 100;
if (prefix >= 10 && suffix >= 10) {
values.push_back(value);
}
}
}
return values;
}
int solve() {
const std::array<int, 6> types = {3, 4, 5, 6, 7, 8};
std::array<std::vector<int>, 6> nums;
for (int i = 0; i < 6; ++i) {
nums[static_cast<std::size_t>(i)] = generate_four_digit_values(types[static_cast<std::size_t>(i)]);
}
std::vector<int> chosen_values;
std::vector<int> chosen_types;
int answer = -1;
auto dfs = [&](auto&& self, int suffix_needed, int used_mask, int first_prefix, int current_sum) -> void {
if (answer != -1) {
return;
}
if (static_cast<int>(chosen_values.size()) == 6) {
if (suffix_needed == first_prefix) {
answer = current_sum;
}
return;
}
for (int t = 0; t < 6; ++t) {
if ((used_mask >> t) & 1) {
continue;
}
for (const int value : nums[static_cast<std::size_t>(t)]) {
const int prefix = value / 100;
const int suffix = value % 100;
if (!chosen_values.empty() && prefix != suffix_needed) {
continue;
}
chosen_values.push_back(value);
chosen_types.push_back(t);
const int next_first_prefix = chosen_values.size() == 1U ? prefix : first_prefix;
self(self, suffix, used_mask | (1 << t), next_first_prefix, current_sum + value);
chosen_types.pop_back();
chosen_values.pop_back();
}
}
};
dfs(dfs, -1, 0, -1, 0);
return answer;
}
bool run_checkpoints() {
if (polygonal(3, 45) != 1035 || polygonal(8, 19) != 1045) {
std::cerr << "Checkpoint failed for polygonal formulas" << '\n';
return false;
}
return true;
}
} // namespace
int main(int argc, char** argv) {
Options options;
if (!parse_arguments(argc, argv, options)) {
return 1;
}
if (options.run_checkpoints && !run_checkpoints()) {
return 2;
}
std::cout << solve() << '\n';
return 0;
}
Python
import sys
def polygonal(type_, n):
if type_ == 3:
return n * (n + 1) // 2
elif type_ == 4:
return n * n
elif type_ == 5:
return n * (3 * n - 1) // 2
elif type_ == 6:
return n * (2 * n - 1)
elif type_ == 7:
return n * (5 * n - 3) // 2
elif type_ == 8:
return n * (3 * n - 2)
else:
return -1
def generate_four_digit_values(type_):
values = []
n = 1
while True:
x = polygonal(type_, n)
if x > 9999:
break
if x >= 1000:
value = int(x)
prefix = value // 100
suffix = value % 100
if prefix >= 10 and suffix >= 10:
values.append(value)
n += 1
return values
def solve():
types = [3, 4, 5, 6, 7, 8]
nums = [generate_four_digit_values(t) for t in types]
chosen_values = []
chosen_types = []
answer = -1
def dfs(suffix_needed, used_mask, first_prefix, current_sum):
nonlocal answer
if answer != -1:
return
if len(chosen_values) == 6:
if suffix_needed == first_prefix:
answer = current_sum
return
for t in range(6):
if (used_mask >> t) & 1:
continue
for value in nums[t]:
prefix = value // 100
suffix = value % 100
if chosen_values and prefix != suffix_needed:
continue
chosen_values.append(value)
chosen_types.append(t)
next_first_prefix = prefix if len(chosen_values) == 1 else first_prefix
dfs(suffix, used_mask | (1 << t), next_first_prefix, current_sum + value)
chosen_types.pop()
chosen_values.pop()
dfs(-1, 0, -1, 0)
return answer
def main():
args = sys.argv[1:]
run_checkpoints_flag = True
for arg in args:
if arg == "--skip-checkpoints":
run_checkpoints_flag = False
else:
print(f"Unknown argument: {arg}", file=sys.stderr)
sys.exit(1)
if run_checkpoints_flag:
# Checkpoint validation
if polygonal(3, 45) != 1035 or polygonal(8, 19) != 1045:
print("Checkpoint failed for polygonal formulas", file=sys.stderr)
sys.exit(2)
print(solve())
if __name__ == "__main__":
main()
Java
import java.util.*;
public class Euler61 {
private static class Options {
boolean runCheckpoints = true;
}
private static boolean parseArguments(String[] args, Options options) {
for (int i = 0; i < args.length; ++i) {
String arg = args[i];
if (arg.equals("--skip-checkpoints")) {
options.runCheckpoints = false;
continue;
}
System.err.println("Unknown argument: " + arg);
return false;
}
return true;
}
private static long polygonal(int type, int n) {
switch (type) {
case 3: return (long)n * (n + 1) / 2;
case 4: return (long)n * n;
case 5: return (long)n * (3 * n - 1) / 2;
case 6: return (long)n * (2 * n - 1);
case 7: return (long)n * (5 * n - 3) / 2;
case 8: return (long)n * (3 * n - 2);
default: return -1;
}
}
private static List<Integer> generateFourDigitValues(int type) {
List<Integer> values = new ArrayList<>();
for (int n = 1;; ++n) {
long x = polygonal(type, n);
if (x > 9999) {
break;
}
if (x >= 1000) {
int value = (int)x;
int prefix = value / 100;
int suffix = value % 100;
if (prefix >= 10 && suffix >= 10) {
values.add(value);
}
}
}
return values;
}
private static int solve() {
int[] types = {3, 4, 5, 6, 7, 8};
@SuppressWarnings("unchecked")
List<Integer>[] nums = new List[6];
for (int i = 0; i < 6; ++i) {
nums[i] = generateFourDigitValues(types[i]);
}
List<Integer> chosenValues = new ArrayList<>();
List<Integer> chosenTypes = new ArrayList<>();
int[] answerRef = {-1};
class DfsHelper {
void dfs(int suffixNeeded, int usedMask, int firstPrefix, int currentSum) {
if (answerRef[0] != -1) {
return;
}
if (chosenValues.size() == 6) {
if (suffixNeeded == firstPrefix) {
answerRef[0] = currentSum;
}
return;
}
for (int t = 0; t < 6; ++t) {
if (((usedMask >> t) & 1) != 0) {
continue;
}
for (int value : nums[t]) {
int prefix = value / 100;
int suffix = value % 100;
if (!chosenValues.isEmpty() && prefix != suffixNeeded) {
continue;
}
chosenValues.add(value);
chosenTypes.add(t);
int nextFirstPrefix = chosenValues.size() == 1 ? prefix : firstPrefix;
dfs(suffix, usedMask | (1 << t), nextFirstPrefix, currentSum + value);
chosenTypes.remove(chosenTypes.size() - 1);
chosenValues.remove(chosenValues.size() - 1);
}
}
}
}
DfsHelper helper = new DfsHelper();
helper.dfs(-1, 0, -1, 0);
return answerRef[0];
}
private static boolean runCheckpoints() {
if (polygonal(3, 45) != 1035 || polygonal(8, 19) != 1045) {
System.err.println("Checkpoint failed for polygonal formulas");
return false;
}
return true;
}
public static void main(String[] args) {
Options options = new Options();
if (!parseArguments(args, options)) {
System.exit(1);
}
if (options.runCheckpoints && !runCheckpoints()) {
System.exit(2);
}
System.out.println(solve());
}
}