Project Euler Problem 61

Solution

Answer: 28684

We seek a cyclic set of six distinct 4-digit polygonal numbers, one from each type:

Triangle $P_{3,n}$
Square $P_{4,n}$
Pentagonal $P_{5,n}$
Hexagonal $P_{6,n}$
Heptagonal $P_{7,n}$
Octagonal $P_{8,n}$

such that:

Every number is 4 digits.
The set is cyclic:

$$\text{last two digits of } a_i = \text{first two digits of } a_{i+1}$$

and the last links back to the first. 3. Each polygonal type appears exactly once.

1. Mathematical analysis

Step 1: Generate polygonal numbers

The formulas are:

$$P_{3,n}=\frac{n(n+1)}{2}$$

$$P_{4,n}=n^2$$

$$P_{5,n}=\frac{n(3n-1)}{2}$$

$$P_{6,n}=n(2n-1)$$

$$P_{7,n}=\frac{n(5n-3)}{2}$$

$$P_{8,n}=n(3n-2)$$

We only care about 4-digit values, i.e.

$$1000 \le P_{k,n} \le 9999$$

Step 2: Model as a graph problem

A number like $8128$ can connect to another number whose first two digits equal $28$.

Example:

$$8128 \to 2882$$

because:

$$8128 \mod 100 = 28$$

and

$$\left\lfloor \frac{2882}{100} \right\rfloor = 28$$

Thus each number behaves like a directed edge between:

prefix = first two digits
suffix = last two digits

We search for a cycle of length 6 where:

each polygonal type is used once,
numbers are distinct,
adjacency rule holds,
cycle closes.

This is naturally solved with depth-first search (DFS) over permutations of polygonal types.

Step 3: Restrict invalid transitions

A useful observation:

If a suffix is less than 10, then it cannot be the first two digits of a 4-digit number.

Example:

$$8120$$

ends in $20$, valid.

But

$$8105$$

ends in $05$, impossible because no 4-digit number starts with “05”.

So we keep only numbers whose last two digits are at least 10.

2. Python implementation

from collections import defaultdict

# Polygonal formulas
def polygonal(s, n):
    if s == 3:
        return n * (n + 1) // 2
    elif s == 4:
        return n * n
    elif s == 5:
        return n * (3 * n - 1) // 2
    elif s == 6:
        return n * (2 * n - 1)
    elif s == 7:
        return n * (5 * n - 3) // 2
    elif s == 8:
        return n * (3 * n - 2)

# Generate all valid 4-digit polygonal numbers
poly = {}

for s in range(3, 9):
    nums = []
    n = 1

    while True:
        x = polygonal(s, n)

        if x >= 10000:
            break

        # Keep only valid 4-digit cyclic candidates
        if 1000 <= x <= 9999 and x % 100 >= 10:
            nums.append(x)

        n += 1

    poly[s] = nums

def dfs(path, used_types):
    # If we have 6 numbers, check cyclic closure
    if len(path) == 6:
        return path if path[-1] % 100 == path[0] // 100 else None

    suffix = path[-1] % 100

    # Try unused polygonal types
    for s in range(3, 9):
        if s not in used_types:
            for num in poly[s]:
                if num // 100 == suffix:
                    result = dfs(
                        path + [num],
                        used_types | {s}
                    )
                    if result:
                        return result

    return None

# Start search from octagonal numbers
# (any type works, but this reduces symmetry)
answer_cycle = None

for start in poly[8]:
    result = dfs([start], {8})
    if result:
        answer_cycle = result
        break

print(answer_cycle)
print(sum(answer_cycle))

3. Code walkthrough

Generating polygonal numbers

We implement the six formulas in polygonal(s, n).

For each type:

for s in range(3, 9):

we generate values until exceeding 9999.

We retain only:

1000 <= x <= 9999

and

x % 100 >= 10

to ensure the final two digits can form the first two digits of another 4-digit number.

DFS search

The recursive function:

dfs(path, used_types)

maintains:

path → current chain of numbers
used_types → polygonal categories already chosen

At each step:

suffix = path[-1] % 100

We try every unused polygonal type and search for numbers with:

num // 100 == suffix

meaning the first two digits match.

When six numbers are collected:

len(path) == 6

we verify the cycle closes:

path[-1] % 100 == path[0] // 100

Verifying the example

The problem’s example:

$$8128, 2882, 8281$$

works because:

$8128 \to 2882$ via 28
$2882 \to 8281$ via 82
$8281 \to 8128$ via 81

and the numbers are triangle, pentagonal, square respectively.

The DFS logic reproduces exactly this behavior for six types.

4. Final verification

Running the program finds the unique cyclic set:

$$1281,\ 8128,\ 2882,\ 8256,\ 5625,\ 2512$$

(using one number from each polygonal family exactly once).

Their sum is:

$$1281+8128+2882+8256+5625+2512=28684$$

The magnitude is sensible (six 4-digit numbers summing to around $6\times 5000\approx 30000$) and matches the uniqueness condition in the problem.

Answer: 28684