Problem 265: Binary Circles

Project Euler Problem 265 Solution

EulerSolve provides an optimized solution for Project Euler Problem 265, Binary Circles, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

We place $2^N$ binary digits on a circle so that the $2^N$ strings of $N$ consecutive digits read clockwise, the blocks, are all different; arrangements that differ only by a rotation count as one. The code of an arrangement is the binary number formed by its digits read clockwise, starting with the block of $N$ zeros as the most significant digits, and $S(N)$ is the sum of all codes. For $N=3$ there are two arrangements: the first has the blocks $000$, $001$, $010$, $101$, $011$, $111$, $110$, $100$ in clockwise order, the codes are $00010111_2=23$ and $00011101_2=29$, and $S(3)=52$. We must find $S(5)$. ^[1]

The whole solution in one sentence: the blocks of a circle form a walk in which every step drops the first digit and appends a new one, so a search that starts with the block of zeros, appends $0$ or $1$ and never repeats a block finds every circle exactly once, and for $N=5$ only $2048$ circles have to be added up.

Mathematical Approach

We turn every circle into a walk through a graph and prove that a simple search finds each such walk exactly once.

1. Every block exactly once

Let $L=2^N$ and write the digits of a circle as $c_0,\dots,c_{L-1}$, with indices modulo $L$. A circle has $L$ blocks, one starting at each position, and there are exactly $L$ binary strings of length $N$, so the blocks are all different exactly when every string of length $N$ occurs exactly once: the circle is a binary de Bruijn sequence of order $N$. ^[2] In particular the block $0^N$ of $N$ zeros (the exponent counts repetitions) occurs once, so the code starts at a well-defined place. Numbering the digits from there, so that $c_0=\dots=c_{N-1}=0$, the code is

$$x=\sum_{i=0}^{L-1}c_i\,2^{L-1-i}.$$

For $N\ge2$ the block $c_1\cdots c_N$ begins with $N-1$ zeros and is not $0^N$, so $c_N=1$; likewise the block $c_{L-1}c_0\cdots c_{N-2}$ forces $c_{L-1}=1$. Every code therefore reads $0^N1\cdots1$ in binary: it is odd, and $2^{L-N-1}\le x\lt2^{L-N}$. Reflections are not identified: $00010111$ read anticlockwise from its zero block is $00011101$, the other circle for $N=3$.

2. Small circles by hand

For $N=1$ the only circle is $01$, so $S(1)=1$. For $N=2$ the forced digits leave only $0011$, with the blocks $00$, $01$, $11$, $10$, so $S(2)=3$. For $N=3$ a circle reads $0001c_4c_5c_61$, and of the eight choices for $c_4c_5c_6$ only $011$ and $110$ avoid a repeated block. For $N=5$ such a trial would test $2^{25}=33\,554\,432$ middle parts; the search of the next sections builds far fewer partial circles, adding one digit at a time and never repeating a block.

3. Blocks as edges of a graph

The block that starts one position later drops the first digit and appends the next one, as in $000\to001\to010\to101$ for the first circle of the statement. The de Bruijn graph of dimension $N-1$ records this overlap: ^[3] its vertices are the $2^{N-1}$ strings of length $N-1$, and every string $w$ of length $N$ is an edge from the first $N-1$ digits of $w$ to its last $N-1$ digits. Every vertex $u$ has two outgoing edges, $u0$ and $u1$, and two incoming edges, $0u$ and $1u$. For $N=3$ the eight edges are

$000\colon00\to00$, $001\colon00\to01$, $010\colon01\to10$, $011\colon01\to11$,
$100\colon10\to00$, $101\colon10\to01$, $110\colon11\to10$, $111\colon11\to11$.

4. Circles are Eulerian circuits

Consecutive blocks are therefore consecutive edges, and listing the blocks of a circle clockwise gives a closed walk that uses every edge exactly once, an Eulerian circuit. ^[4] For the first circle of $N=3$ it visits the vertices

$$\begin{aligned}00&\to00\to01\to10\to01\\&\to11\to11\to10\to00.\end{aligned}$$

Conversely, take an Eulerian circuit $e_0,\dots,e_{L-1}$ with $e_0=0^N$ and let $c_i$ be the first digit of $e_i$. Each edge is the previous one shifted by one place, so $c_i\cdots c_{i+N-1}$ are the digits of $e_i$, also across the end, because the walk is closed. So the circles, counted up to rotation, correspond one to one to the Eulerian circuits that start with $0^N$.

5. How many circles exist

By Euler's theorem for directed graphs, a graph has an Eulerian circuit exactly when every vertex has as many incoming as outgoing edges and all vertices with edges lie in one strongly connected component. ^[4] Both hold here: every vertex has two edges in and two out, and any vertex $v$ can be reached from any other by appending the $N-1$ digits of $v$. So circles exist for every $N$, and the BEST theorem counts them: ^[5]

$$\operatorname{ec}(G)=t_w(G)\prod_{v}\bigl(\deg(v)-1\bigr)!.$$

Here $\operatorname{ec}(G)$ counts the Eulerian circuits with a fixed first edge, for us $0^N$, and every factor is $(2-1)!=1$, as two edges leave every vertex. The number $t_w(G)$ counts the spanning trees directed towards a vertex $w$: every other vertex chooses one outgoing edge so that the choices always lead to $w$. For $N=3$ and $w=00$, the vertex $11$ must take $11\to10$, its other edge being a loop, and $10$ must take $10\to00$, since after $10\to01$ both edges of $01$ lead back to $10$; $01$ is free, so there are two trees and two circles. For general $N$ the number of trees is a classical result of Flye Sainte-Marie (1894) and de Bruijn (1946): ^[2]

$$C(N)=2^{2^{N-1}-N},$$

that is, $1$, $1$, $2$, $16$ and $2048$ circles for $N=1,\dots,5$. For $N=5$ it is therefore practical to generate every circle and add its code, as the programs do; the count alone does not give the sum.

6. Building a circle digit by digit

Backtracking explores a tree of partial solutions depth first and undoes a step when it cannot be continued. ^[6] Here a partial solution is the beginning of a walk: the digits written, the blocks used and the current vertex $u$, the last $N-1$ digits. We start with $0^N$ written and used, at $u=0^{N-1}$. A step tries $b=0$ and then $b=1$: if the block $u$ followed by $b$ is unused, we mark it, write $b$, move to its last $N-1$ digits and continue, and afterwards erase $b$ and unmark the block. When all $2^N$ blocks are used, the first $L$ digits are a circle, as Section 7 shows. Read as binary numbers, the new block $e$ and the new vertex $u'$ are

$$e=(2u+b)\bmod2^N,\qquad u'=e\bmod2^{N-1};$$

for $N=3$, the vertex $u=10_2=2$ and $b=1$ give $e=101_2=5$ and $u'=01_2=1$.

7. Why the search closes every circle

Claim. Whenever the search cannot continue, it stands at the vertex $0^{N-1}$.

Proof. The walk starts at $0^{N-1}$, since $0^N$ leads from $0^{N-1}$ to itself. If the search stands at another vertex $v$, it has arrived at $v$ once more often than it has left, and every arrival used a different one of the two incoming edges of $v$. So it has left $v$ at most once, and an outgoing edge of $v$ is still free.

Three consequences follow. When all blocks are used, the search is at $0^{N-1}$, so the last $N-1$ of the $L+N-1$ digits written are zeros like the first ones, and every block of the circle that wraps around its end, such as $c_{L-1}c_0\cdots c_{N-2}$, is the block of the walk at the same position: no further test is needed. Every dead end is an early return to $0^{N-1}$, whose outgoing edges $0^N$ and $0^{N-1}1$ are used from the first step on, so the walk stops when it comes back through $10^{N-1}$, with a circle exactly when no block is left. And every circle is found exactly once: read from its zero block, it is a sequence of digit choices without a repeated block, which the search follows, and two complete leaves differ where their paths split, among the first $L$ digits, as both end with $N-1$ zeros.

8. Worked example: $N=3$

The search starts with $000$ at the vertex $00$, and its first digit must be $1$. The search tree has seven leaves, met in this order; each shows the digits written:

$000100$: a dead end after $4$ blocks;
$000101100$: a dead end after $7$ blocks, with $111$ missing;
$0001011100$: all $8$ blocks, the circle $00010111$;
$0001100$, $000110100$, $00011100$: dead ends after $5$, $7$ and $6$ blocks;
$0001110100$: all $8$ blocks, the circle $00011101$.

Every leaf ends with the block $100$, the only way back into $00$, and the search makes $23$ calls. Horner's rule computes a code with one doubling and one addition per digit, $x\leftarrow2x+c_i$: ^[7] the values run $0,0,0,1,2,5,11,23$ and $0,0,0,1,3,7,14,29$, and $23+29=52$. For $N=4$ the search finds $16$ circles, from $0000100110101111_2=2479$ to $0000111101100101_2=3941$, and $S(4)=51504$. For $N=5$ every code is below $2^{27}$ by Section 1, so $S(5)\lt2^{11}\cdot2^{27}=2^{38}$.

How the Code Works

The C++ program ^[8] starts in main. parse_arguments reads --skip-checkpoints and --n=, default $5$; an unknown argument or a value outside $2$ to $10$ makes main exit with code $1$, though for huge values the digit loop overflows an int before that check. Unless --skip-checkpoints is given, run_checkpoints requires solve(3) to return $52$ and solve(2) to return $3$, else the exit code is $2$; then main prints solve(n).

solve sets edge_count to $2^N$ and node_mask to $2^{N-1}-1$, keeps one byte per block in used_edge and the digits in the vector sequence, which starts with $N$ zeros, and marks block $0$. The lambda dfs, which receives itself as self in order to recurse, is the search of Section 6; its arguments node and used are the current vertex and the number of blocks used. When used reaches edge_count, it returns if node is not $0$, which by Section 7 never happens, and otherwise folds the first $2^N$ digits into a number by shifts, as in Horner's rule, and adds it to the unsigned 64-bit total. Otherwise, for bit $=0,1$, it forms the block ((node << 1) | bit) & (edge_count - 1), which is $(2u+b)\bmod2^N$ because the shift doubles and the AND keeps the last $N$ binary digits; it skips a used block, and else marks it, appends the digit, recurses with the vertex edge & node_mask and used + 1, and undoes both changes. The first call is dfs(dfs, 0, 1).

The Python program has the same structure, with a bytearray, a list of digits and the sum in a one-element list total that the inner function can change; it raises the recursion limit to $2000$, although the search is only $32$ calls deep. The Java program keeps the state in static fields and the digits in an int array with a length counter seqLen, fixes $N=5$ and adds in a long. Neither runs checkpoints.

The option --n= admits $N$ up to $10$, but the 64-bit sum is exact only for $N\le5$: for $N=6$ the $2^{26}$ codes are each at least $2^{57}$, so their sum is at least $2^{83}$, and a test run with --n=6 printed $S(6)$ modulo $2^{64}$; from $N=7$ on even single codes overflow.

Complexity and Verification

Let $T(N)$ be the number of calls, one per node of the search tree. Each call tries at most two blocks and each of the $C(N)$ circles is converted in $2^N$ steps, so the time is proportional to $T(N)+2^N\,C(N)$. For $N=3$, $4$ and $5$ we get $T(N)=23$, $354$ and $92\,636$; for $N=5$ the leaves are $2048$ circles and $11\,562$ dead ends, and the conversions add $65\,536$ steps, while the trial of Section 2 has about $360$ times as many candidates as there are calls. Each program finishes in a fraction of a second; the memory holds $2^N$ flags and at most $2^N+N-1$ digits, and the recursion is $2^N$ calls deep. The calls per circle roughly double with each $N$, about $11$, $22$, $45$ and $82$ for $N=3,\dots,6$, where $T(6)=5\,504\,163\,339$.

Unless --skip-checkpoints is given, the C++ program checks $S(3)=52$ and $S(2)=3$ first. For this article, outside the published solutions, a brute force over all $2^{2^N}$ digit strings for $N\le4$ confirmed the circles and $S(1)$ to $S(4)$; for $N=5$ an independent C program tested all $2^{25}$ candidates of Section 2 and found the $2048$ circles and the same sum as the three published programs, which agree with each other; and for $N\le6$ the counts match $C(N)$ and $t_w$ computed as a determinant, and the test on node never fired.

Footnotes and References

The references supply the background; the forced digits, the argument of Section 7 and all counts are derived or computed in this article.

Project Euler 265 — Binary Circles. The official statement: 2^N binary digits in a circle with all N-digit clockwise subsequences distinct, the codes 23 and 29 for N = 3, S(3) = 52, and the task to find S(5).
Wikipedia — De Bruijn sequence. A cyclic sequence containing every string of length n exactly once, equivalently an Eulerian cycle of the (n − 1)-dimensional de Bruijn graph; there are 2^(2^(n−1) − n) binary ones, such as 00010111 and 11101000 for n = 3, counted by Flye Sainte-Marie in 1894 and by de Bruijn in 1946.
Wikipedia — De Bruijn graph. The vertices are the strings of a fixed length, an edge shifts a string one place left and appends a symbol, every vertex has m edges in and m out, and the graph is Eulerian.
Wikipedia — Eulerian path. A directed graph has an Eulerian circuit, a closed trail through every edge once, if and only if in-degree equals out-degree everywhere and all vertices of nonzero degree lie in one strongly connected component.
Wikipedia — BEST theorem. The number of Eulerian circuits is t_w(G) times the product of the factorials (deg(v) − 1)!, with t_w(G) the number of spanning trees directed towards a root w.
Wikipedia — Backtracking. Candidates are built step by step and abandoned as soon as they cannot be completed; the tree of partial candidates is traversed depth first.
Wikipedia — Horner's method. The nested scheme evaluates a polynomial of degree n with n multiplications and n additions, and it converts numbers between positional numeral systems.
C++ — Euler265.cpp. The linked immutable revision contains parse_arguments, solve with the recursive lambda dfs, and run_checkpoints; it is the implementation record for this article.

Problem 265 source code

C++

#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int n = 5;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--n=", options.n)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.n >= 2 && options.n <= 10;
}

u64 solve(const int n) {
    const int edge_count = 1 << n;
    const int node_mask = (1 << (n - 1)) - 1;

    std::vector<std::uint8_t> used_edge(static_cast<std::size_t>(edge_count), 0U);
    std::vector<int> sequence(static_cast<std::size_t>(n), 0);
    used_edge[0] = 1U;  // The starting N-bit block is all zeros.

    u64 total = 0;

    const auto dfs = [&](auto&& self, int node, int used) -> void {
        if (used == edge_count) {
            if (node != 0) {
                return;
            }
            u64 value = 0;
            for (int i = 0; i < edge_count; ++i) {
                value = (value << 1) | static_cast<u64>(sequence[static_cast<std::size_t>(i)]);
            }
            total += value;
            return;
        }

        for (int bit = 0; bit <= 1; ++bit) {
            const int edge = ((node << 1) | bit) & (edge_count - 1);
            if (used_edge[static_cast<std::size_t>(edge)] != 0U) {
                continue;
            }
            used_edge[static_cast<std::size_t>(edge)] = 1U;
            sequence.push_back(bit);
            self(self, edge & node_mask, used + 1);
            sequence.pop_back();
            used_edge[static_cast<std::size_t>(edge)] = 0U;
        }
    };
    dfs(dfs, 0, 1);
    return total;
}

bool run_checkpoints() {
    if (solve(3) != 52ULL) {
        std::cerr << "Checkpoint failed for S(3)=52 sample" << '\n';
        return false;
    }
    if (solve(2) != 3ULL) {
        std::cerr << "Checkpoint failed for S(2)=3" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.n) << '\n';
    return 0;
}

Python

import sys

# Set recursion limit high enough just in case, though max depth here is 32.
sys.setrecursionlimit(2000)

def solve(n=5):
    edge_count = 1 << n
    node_mask = (1 << (n - 1)) - 1
    
    used_edge = bytearray(edge_count)
    sequence = [0] * n
    used_edge[0] = 1
    
    total = [0]
    
    def dfs(node, used):
        if used == edge_count:
            if node != 0:
                return
            value = 0
            for i in range(edge_count):
                value = (value << 1) | sequence[i]
            total[0] += value
            return
            
        for bit in (0, 1):
            edge = ((node << 1) | bit) & (edge_count - 1)
            if used_edge[edge]:
                continue
            used_edge[edge] = 1
            sequence.append(bit)
            dfs(edge & node_mask, used + 1)
            sequence.pop()
            used_edge[edge] = 0
            
    dfs(0, 1)
    return str(total[0])

if __name__ == '__main__':
    print(solve())

Java

public class Euler265 {
    static long total = 0;
    static byte[] usedEdge;
    static int[] sequence;
    static int seqLen;
    static int edgeCount;
    static int nodeMask;

    static void dfs(int node, int used) {
        if (used == edgeCount) {
            if (node != 0)
                return;
            long value = 0;
            for (int i = 0; i < edgeCount; ++i) {
                value = (value << 1) | sequence[i];
            }
            total += value;
            return;
        }

        for (int bit = 0; bit <= 1; ++bit) {
            int edge = ((node << 1) | bit) & (edgeCount - 1);
            if (usedEdge[edge] != 0)
                continue;
            usedEdge[edge] = 1;
            sequence[seqLen++] = bit;
            dfs(edge & nodeMask, used + 1);
            seqLen--;
            usedEdge[edge] = 0;
        }
    }

    public static String solve() {
        int n = 5;
        edgeCount = 1 << n;
        nodeMask = (1 << (n - 1)) - 1;
        usedEdge = new byte[edgeCount];
        sequence = new int[edgeCount + n + 1];

        for (int i = 0; i < n; ++i)
            sequence[i] = 0;
        seqLen = n;
        usedEdge[0] = 1;

        total = 0;
        dfs(0, 1);
        return String.valueOf(total);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}