Detailed mathematical approach

Problem Summary

For a fixed \(n\), we want binary circles in which every \(n\)-bit block appears exactly once as a cyclic substring. The problem asks for the sum of the binary integers represented by all such circles, using the canonical representation chosen by the solver.

The implementation does not search the space of bit strings directly. Instead, it models the problem as an Eulerian-cycle search in a De Bruijn graph and enumerates every valid cycle with depth-first backtracking.

Mathematical Approach

1. From Binary Circles to De Bruijn Graphs

A binary circle of order \(n\) is a cyclic bit sequence whose cyclic length-\(n\) substrings are exactly the \(2^n\) possible \(n\)-bit patterns. That condition is naturally encoded by the De Bruijn graph of order \(n\).

The graph has:

$|V|=2^{n-1},\qquad |E|=2^n.$

Each vertex is an \((n-1)\)-bit string. Each edge is an \(n\)-bit string, viewed as a transition from its first \(n-1\) bits to its last \(n-1\) bits.

2. Edge Transition Rule

If the current node is \(u\) and we append a bit \(b\in\{0,1\}\), then the next edge label is

$e=((u\ll 1)\,|\,b)\ \&\ (2^n-1),$

and the next node is its suffix of length \(n-1\):

$v=e\ \&\ (2^{n-1}-1).$

So the DFS is literally walking through the De Bruijn graph one edge at a time, where every edge corresponds to one \(n\)-bit block.

3. Why Eulerian Cycles Are Exactly the Answers

Traversing every edge exactly once means that every \(n\)-bit pattern appears exactly once. That is precisely the definition of the required binary circle.

Conversely, any binary circle determines a closed walk in the graph, because consecutive length-\(n\) windows overlap in their last \(n-1\) bits. Therefore the problem is equivalent to enumerating Eulerian cycles in this directed graph.

4. Canonical Rooting at \(0^n\)

Cycles are circular, so the same cycle can be rotated. The solver removes this rotational ambiguity by fixing the starting block to be \(0^n\). In the code this is done by marking edge 0 as already used and starting the DFS at node 0.

This anchor gives one canonical representative per cycle. Without it, the same circle would be found multiple times under different rotations.

5. Depth-First Search With Used-Edge Tracking

The recursive search keeps:

1. a boolean array of used edges,

2. the current node,

3. the partial bit sequence being built.

At each step it tries bit 0 and bit 1. If the corresponding edge has not been used, it marks the edge, appends the bit, and recurses to the suffix node. After returning, it undoes the choice and continues with the next branch.

This is a standard backtracking enumeration of all Eulerian cycles from the fixed root.

6. Why the Search Is Correct

The invariant is simple: the set of used edges is exactly the set of edges already traversed in the partial walk, and the current node is the suffix of the last traversed edge.

If all \(2^n\) edges have been used and the walk returns to node 0, then the partial walk is a closed Eulerian cycle. If any edge remains unused, then the walk is incomplete and cannot yet represent a valid binary circle.

Because the DFS tries every unused outgoing edge at every step, every Eulerian cycle rooted at \(0^n\) is enumerated exactly once.

7. Converting a Cycle to an Integer

The code stores the current bit stream in sequence. Once a full cycle has been found, the first \(2^n\) bits of that stream are interpreted as a binary integer:

$X=\sum_{i=0}^{2^n-1} b_i\,2^{2^n-1-i}.$

That value is added to the running total. The solver therefore sums the canonical integer representative of every valid binary circle.

A tiny worked example is \(n=2\). The unique anchored cycle produces the bit prefix

$0011,$

whose cyclic windows are

$00,\ 01,\ 11,\ 10.$

These are exactly the four 2-bit patterns, and the canonical integer is

$0011_2=3,$

which matches the checkpoint \(S(2)=3\).

8. Small Checkpoints

The program verifies two sample values:

$S(2)=3,\qquad S(3)=52.$

These checks are useful because they confirm both the graph construction and the integer-conversion logic before larger searches are attempted.

For \(n=3\), the two canonical cycles found by the solver are

$00010111_2=23,\qquad 00011101_2=29,$

so

$S(3)=23+29=52.$

How the Code Works

The program accepts --n and --skip-checkpoints. solve(n) first computes the edge count \(2^n\) and the node mask \(2^{n-1}-1\). The array used_edge marks which \(n\)-bit blocks have already been traversed. The vector sequence starts with \(n\) zero bits, which is the anchored \(0^n\) block.

The lambda dfs explores the two possible extensions from the current node. When a candidate edge is unused, it is marked, its trailing bit is appended, and the recursion continues from the suffix node. Once all edges are used and the walk has returned to node 0, the solver converts the collected bit stream into a binary integer and adds it to total.

The checkpoint routine simply compares the results of solve(2) and solve(3) against the expected sample values.

Complexity Analysis

The solver enumerates Eulerian cycles by backtracking, so the running time is exponential in \(n\). That is unavoidable here because the number of valid binary circles itself grows rapidly with \(n\).

Memory usage is \(O(2^n)\), dominated by the edge-usage array and the current bit sequence. The recursion depth is also proportional to the cycle length.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=265
2. De Bruijn sequence: Wikipedia - De Bruijn sequence
3. Eulerian path/cycle: Wikipedia - Eulerian path