Project Euler Problem 68

Solution

Answer: 6531031914842725

1. Mathematical analysis

We want the maximum 16-digit string describing a magic 5-gon ring using the numbers $1$ through $10$.

A 5-gon ring has:

5 external nodes
5 internal nodes

Each line contains:

$$(\text{external}, \text{internal}i, \text{internal}{i+1})$$

and all five lines must sum to the same total.

Let:

external nodes: $e_1,\dots,e_5$
internal nodes: $i_1,\dots,i_5$

Then every line satisfies:

$$e_k + i_k + i_{k+1} = S$$

(indices modulo 5).

Key observation 1: Why only 16 digits?

Each number appears once, except internal nodes appear twice in the concatenation (because each belongs to two lines).

The number $10$ contributes two digits.

If $10$ is an internal node, it appears twice → total string length becomes 17 digits.

We need a 16-digit string, so:

$$10 \text{ must be external.}$$

Key observation 2: Canonical representation

The problem removes rotational symmetry:

Start from the group whose external node is smallest
Read clockwise

So every valid arrangement has a unique encoding.

Key observation 3: To maximize the number

Since the string is concatenated in order, we want the largest possible leading digits.

But the first group must start at the smallest external node.

Thus, to maximize the total string:

the smallest external node should be as large as possible,
while still being the minimum among externals.

Since $10$ must be external, the best strategy is to place the largest numbers externally.

A natural candidate is:

$${6,7,8,9,10}$$

as external nodes, leaving

$${1,2,3,4,5}$$

inside.

Then we search all valid magic rings and take the maximum valid 16-digit string.

2. Python implementation

from itertools import permutations

def solve():
    nums = set(range(1, 11))
    best = 0

    # Choose the 5 internal nodes and arrange them cyclically
    for inner in permutations(range(1, 11), 5):
        inner_set = set(inner)
        outer_nums = nums - inner_set

        # Try all permutations of outer nodes
        for outer in permutations(outer_nums):
            # Enforce canonical form:
            # first outer node must be the smallest
            if outer[0] != min(outer):
                continue

            # Compute target sum using first line
            target = outer[0] + inner[0] + inner[1]

            valid = True
            groups = []

            for i in range(5):
                a = outer[i]
                b = inner[i]
                c = inner[(i + 1) % 5]

                if a + b + c != target:
                    valid = False
                    break

                groups.append(f"{a}{b}{c}")

            if not valid:
                continue

            candidate = int("".join(groups))

            # Only keep 16-digit strings
            if len(str(candidate)) == 16:
                best = max(best, candidate)

    return best

print(solve())

3. Code walkthrough

Step 1: Generate internal node orderings

for inner in permutations(range(1, 11), 5):

We choose and arrange the 5 internal nodes.

Their order matters because they form a cycle.

Step 2: Determine external nodes

outer_nums = nums - inner_set

The remaining numbers become external nodes.

Step 3: Try all external arrangements

for outer in permutations(outer_nums):

We test every assignment.

Step 4: Enforce unique representation

if outer[0] != min(outer):
    continue

The problem requires starting from the line whose external node is smallest.

This removes rotational duplicates.

Step 5: Fix the magic sum

target = outer[0] + inner[0] + inner[1]

The first line determines the required total.

Every other line must match.

Step 6: Validate all 5 lines

for i in range(5):
    a = outer[i]
    b = inner[i]
    c = inner[(i + 1) % 5]

These define the ring:

$$(e_i, i_i, i_{i+1})$$

with wraparound using modulo.

We check:

if a + b + c != target:

If any fail, reject the arrangement.

Step 7: Build the concatenated string

groups.append(f"{a}{b}{c}")
candidate = int("".join(groups))

This exactly follows the problem definition.

Small example check (3-gon)

The example:

$$4,3,2;\ 6,2,1;\ 5,1,3$$

concatenates to:

$$432621513$$

which matches the problem statement.

4. Final verification

The optimal arrangement found is:

$$6,5,3;\ 10,3,1;\ 9,1,4;\ 8,4,2;\ 7,2,5$$

Concatenation gives:

$$6531031914842725$$

Checks:

Exactly 16 digits ✓
Uses numbers 1–10 once each ✓
All line sums equal:

$$6+5+3=14$$

$$10+3+1=14$$

$$9+1+4=14$$

$$8+4+2=14$$

$$7+2+5=14$$

✓

Answer: 6531031914842725