Problem 61: Cyclical Figurate Numbers

Mathematical Foundation

Definition 1. The $s$-gonal number of order $n$ is defined as

Theorem 1 (Closed form for polygonal numbers). The formula in Definition 1 satisfies $P(s,1) = 1$ for all $s \ge 3$, and the recurrence $P(s,n) - P(s,n-1) = (s-2)(n-1) + 1$ for $n \ge 2$.

Proof. Verification of the initial condition: $P(s,1) = \frac{1 \cdot [(s-2) - (s-4)]}{2} = \frac{2}{2} = 1$. For the recurrence, compute

Simplifying: $\frac{2(s-2)n - (s-2) - (s-4)}{2} = \frac{2(s-2)n - 2s + 6}{2} = (s-2)n - s + 3 = (s-2)(n-1) + 1$. This matches the defining property that consecutive differences of $s$-gonal numbers form an arithmetic progression with common difference $s-2$. $\square$

Lemma 1 (Index bounds for 4-digit polygonal numbers). For each $s \in \{3,4,5,6,7,8\}$, the indices $n$ producing 4-digit values $1000 \le P(s,n) \le 9999$ form a contiguous range $[n_{\min}(s), n_{\max}(s)]$:

Proof. Since $P(s,n)$ is a strictly increasing function of $n$ for $n \ge 1$ (each successive difference $(s-2)(n-1)+1 > 0$), the set $\{n : 1000 \le P(s,n) \le 9999\}$ is a contiguous integer interval. The endpoints are obtained by solving the quadratic $P(s,n) = M$:

taking the positive root. Then $n_{\min}(s) = \lceil n(M=1000) \rceil$ and $n_{\max}(s) = \lfloor n(M=9999) \rfloor$. Direct evaluation confirms the table entries. $\square$

Definition 2 (Cyclic linking). A 4-digit number $N$ links to another 4-digit number $N'$ if $N \bmod 100 = \lfloor N'/100 \rfloor$, i.e., the last two digits of $N$ equal the first two digits of $N'$. Both the suffix $N \bmod 100$ and the prefix $\lfloor N'/100 \rfloor$ must lie in $\{10, 11, \ldots, 99\}$ for meaningful two-digit linking.

Theorem 2 (Graph formulation). Define a directed labeled multigraph $G = (V, E)$ where:

• $V = \{10, 11, \ldots, 99\}$ (the 90 possible two-digit prefixes/suffixes),
• For each 4-digit polygonal number $N$ of type $s$ with $\lfloor N/100 \rfloor = p$ and $N \bmod 100 = q \ge 10$, include the directed edge $(p, q)$ with label $s$ and weight $N$.

Then a valid solution to the problem corresponds to a directed 6-cycle $v_1 \to v_2 \to \cdots \to v_6 \to v_1$ in $G$ whose edges carry all six distinct labels $\{3,4,5,6,7,8\}$.

Proof. Let $(N_1, N_2, \ldots, N_6)$ be a valid cyclic set. Define $v_i = \lfloor N_i / 100 \rfloor$. The cyclic condition $N_i \bmod 100 = \lfloor N_{i+1}/100 \rfloor = v_{i+1}$ (indices modulo 6) means each $N_i$ corresponds to the edge $(v_i, v_{i+1})$. Each $N_i$ has a unique polygonal type, giving six distinct edge labels. Conversely, any such 6-cycle in $G$ with all six labels yields a valid solution by reading off the edge weights. $\square$

Theorem 3 (Uniqueness). The solution is unique up to cyclic rotation.

Proof. By exhaustive depth-first search over $G$ with backtracking, starting from every possible initial edge and exploring all label-valid extensions, exactly one equivalence class of 6-cycles (under cyclic rotation) is found. The completeness of depth-first search with backtracking guarantees that no valid cycle is missed. $\square$

Editorial

We first enumerate all 4-digit polygonal numbers of types $3$ through $8$ and keep only those whose last two digits form a valid two-digit suffix. Each remaining number is then treated as a labeled link from its first two digits to its last two digits. Starting from every possible value, we perform a depth-first backtracking search that extends the chain only through matching suffix-prefix links and polygonal types that have not yet been used. A candidate is accepted only when it contains six values, uses all six types exactly once, and closes back to its starting prefix.

Pseudocode

Generate the 4-digit polygonal numbers of each required type.
Ignore any value whose final two digits do not form a valid link.

Organize the remaining values by polygonal type and by their first two digits.

For each possible starting value:
    begin a chain containing only that value
    mark its polygonal type as used
    try to extend the chain recursively

During the recursive search:
    if the chain already contains six values:
        accept it only when the current suffix matches the opening prefix

    otherwise, for each polygonal type not yet used:
        inspect the values of that type whose prefix matches the current suffix
        extend the chain by each such value in turn

Return the sum of the first chain that closes cyclically.

Complexity Analysis

Time: Let $E = \sum_{s} |E_s| \le 351$ be the total number of valid edges. The DFS explores at most $\prod_{d=1}^{5} B_d$ paths from each starting edge, where $B_d$ is the branching factor at depth $d$. Since the label-uniqueness constraint eliminates at least one type per level and the average out-degree per vertex is $E/|V| \approx 4$, the effective search space is small. The overall worst-case bound is $O(E \cdot (E/|V|)^5)$, which evaluates to a constant for this problem size.

Space: $O(E)$ for the adjacency lists, plus $O(6)$ for the DFS recursion stack. Total: $O(E)$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // P(s,n) = n * ((s-2)*n - (s-4)) / 2
    auto polygonal = [](int s, int n) -> int {
        return n * ((s - 2) * n - (s - 4)) / 2;
    };

    // Generate all 4-digit polygonal numbers for types 3..8
    vector<vector<int>> poly(6);
    for (int s = 3; s <= 8; s++) {
        for (int n = 1; ; n++) {
            int val = polygonal(s, n);
            if (val >= 10000) break;
            if (val >= 1000 && val % 100 >= 10)
                poly[s - 3].push_back(val);
        }
    }

    // Build adjacency: by_prefix[type][prefix] = list of (suffix, value)
    vector<unordered_map<int, vector<pair<int,int>>>> by_prefix(6);
    for (int t = 0; t < 6; t++)
        for (int v : poly[t]) {
            int p = v / 100, s = v % 100;
            by_prefix[t][p].push_back({s, v});
        }

    // DFS to find 6-cycle using all six types
    int answer = 0;
    int chain[6];

    function<void(int, int, int, int)> dfs =
        [&](int depth, int used_mask, int cur_suffix, int start_prefix) {
        if (answer) return;
        if (depth == 6) {
            if (cur_suffix == start_prefix) {
                int sum = 0;
                for (int i = 0; i < 6; i++) sum += chain[i];
                answer = sum;
            }
            return;
        }
        for (int t = 0; t < 6; t++) {
            if (used_mask & (1 << t)) continue;
            auto it = by_prefix[t].find(cur_suffix);
            if (it == by_prefix[t].end()) continue;
            for (auto& [suf, val] : it->second) {
                chain[depth] = val;
                dfs(depth + 1, used_mask | (1 << t), suf, start_prefix);
                if (answer) return;
            }
        }
    };

    for (int t = 0; t < 6 && !answer; t++)
        for (int v : poly[t]) {
            int p = v / 100, s = v % 100;
            chain[0] = v;
            dfs(1, 1 << t, s, p);
            if (answer) break;
        }

    cout << answer << endl;
    return 0;
}

"""
Problem 61: Cyclical Figurate Numbers

Find the sum of the only ordered set of six cyclic 4-digit numbers
for which each polygonal type (triangle through octagonal) is represented.
"""

from collections import defaultdict


def polygonal(s, n):
    """Return the n-th s-gonal number: P(s,n) = n*((s-2)*n - (s-4)) / 2."""
    return n * ((s - 2) * n - (s - 4)) // 2


def solve():
    # Generate 4-digit polygonal numbers for each type s in {3,...,8}
    poly = [[] for _ in range(6)]  # index 0..5 for types 3..8
    for s in range(3, 9):
        n = 1
        while True:
            val = polygonal(s, n)
            if val >= 10000:
                break
            if val >= 1000 and val % 100 >= 10:
                poly[s - 3].append(val)
            n += 1

    # Build adjacency: by_prefix[type][prefix] -> list of (suffix, value)
    by_prefix = [defaultdict(list) for _ in range(6)]
    for t in range(6):
        for v in poly[t]:
            p, s = divmod(v, 100)
            by_prefix[t][p].append((s, v))

    # DFS to find a 6-cycle using all six types
    def dfs(depth, used_mask, cur_suffix, start_prefix, chain):
        if depth == 6:
            if cur_suffix == start_prefix:
                return sum(chain)
            return None
        for t in range(6):
            if used_mask & (1 << t):
                continue
            for suf, val in by_prefix[t].get(cur_suffix, []):
                result = dfs(depth + 1, used_mask | (1 << t),
                             suf, start_prefix, chain + [val])
                if result is not None:
                    return result
        return None

    # Try starting with each type and each number
    for t in range(6):
        for v in poly[t]:
            p, s = divmod(v, 100)
            result = dfs(1, 1 << t, s, p, [v])
            if result is not None:
                return result


answer = solve()
assert answer == 28684
print(answer)