Solution

Answer: 209110240768

We seek all binary cyclic sequences of length $2^N$ such that every binary word of length $N$ appears exactly once as a consecutive clockwise subsequence.

These are precisely the binary de Bruijn cycles of order $N$.

For $N=5$, we must compute the sum of all distinct encodings described in the problem statement.

Mathematical analysis

A binary de Bruijn cycle of order $N$ is a cyclic binary sequence in which every possible $N$-bit string occurs exactly once.

There are $2^N$ such substrings, so the cycle length must be $2^N$.

1. Graph interpretation

Define a directed graph:

Vertices = all binary strings of length $N-1$
Directed edges = all binary strings of length $N$

An edge

$$b_1b_2\dots b_N$$

goes from

$$b_1b_2\dots b_{N-1}$$

$$b_2b_3\dots b_N$$

Each vertex has:

outdegree $2$
indegree $2$

A de Bruijn cycle corresponds exactly to an Eulerian cycle in this graph.

2. Canonical representation

The problem removes rotational duplicates by requiring the sequence to begin with

$$00000$$

So we can fix the starting node to all zeros and generate all Eulerian cycles beginning there.

If the generated cyclic sequence is

$$a_0a_1\dots a_{31}$$

then the encoded integer is

$$\sum_{i=0}^{31} a_i 2^{31-i}$$

3. DFS construction

Maintain:

current $(N-1)$-bit suffix
set of visited $N$-bit strings

Initially:

visited contains $00000$
sequence starts with five zeros

At each step:

append bit $0$ or $1$
form the next $N$-bit word
continue only if that word has not appeared before

When all $2^N$ words have been visited, we obtain one valid cycle.

For $N=5$, this search is completely feasible.

Python implementation

from collections import defaultdict

def debruijn_sum(n):
    target = 1 << n                 # total N-bit strings
    mask = (1 << (n - 1)) - 1      # keeps last N-1 bits

    visited = {0}                  # start with 000...0 already used
    seq = [0] * n                  # initial sequence = N zeros

    total = 0

    def dfs(node):
        nonlocal total

        # If every N-bit word has appeared exactly once,
        # we have a complete de Bruijn cycle.
        if len(visited) == target:
            bits = seq[:target]
            value = int("".join(map(str, bits)), 2)
            total += value
            return

        suffix = node & mask

        # Try appending 0 or 1
        for bit in (0, 1):
            nxt = (suffix << 1) | bit

            if nxt not in visited:
                visited.add(nxt)
                seq.append(bit)

                dfs(nxt)

                seq.pop()
                visited.remove(nxt)

    dfs(0)
    return total

# Verify the example
print(debruijn_sum(3))   # should be 52

# Solve the problem
print(debruijn_sum(5))

Code walkthrough

Initialization

target = 1 << n

There are exactly $2^N$ distinct $N$-bit words.

mask = (1 << (n - 1)) - 1

Used to keep only the last $N-1$ bits.

visited = {0}
seq = [0] * n

We begin with the all-zero word already included.

DFS step

Suppose the current suffix is the $(N-1)$-bit number suffix.

Appending bit bit creates:

nxt = (suffix << 1) | bit

which is the next $N$-bit word.

If it has not yet appeared, we continue recursively.

Completion

When all $2^N$ words have been used:

bits = seq[:target]
value = int("".join(map(str, bits)), 2)

This converts the canonical binary representation into its integer value.

Verification on the sample

For $N=3$, the program returns:

$$23 + 29 = 52$$

matching the problem statement.

Final verification

For $N=5$:

the number of valid cycles generated is $2048$
summing all canonical encodings gives

$$209110240768$$

This is the known correct Project Euler value.

Answer: 209110240768

Project Euler Problem 265