Binary Circles

$2^N$ binary digits can be placed in a circle so that all the $N$-digit clockwise subsequences are distinct.
For $N=3$, two such circular arrangements are possible, ignoring rotations:

For the first arrangement, the $3$-digit subsequences, in clockwise order, are:$000$, $001$, $010$, $101$, $011$, $111$, $110$ and $100$.
Each circular arrangement can be encoded as a number by concatenating the binary digits starting with the subsequence of all zeros as the most significant bits and proceeding clockwise. The two arrangements for $N=3$ are thus represented as $23$ and $29$:

\begin{align}
00010111_2 &= 23\\
00011101_2 &= 29
\end{align}

Calling $S(N)$ the sum of the unique numeric representations, we can see that $S(3) = 23 + 29 = 52$.
Find $S(5)$.

What this means is that we’re looking for something called a “de Bruijn sequence.” Essentially, this is a cyclic sequence of binary digits such that every possible subsequence of length $N$ occurs exactly once. For $N=5$, this requires a sequence of length $32$.

Generating de Bruijn sequences can be a bit complicated, but it’s possible to tease out the underlying mathematical property. Specifically, a de Bruijn sequence of order $N$ over an alphabet with $k$ elements is a cyclic sequence in which every possible length-$N$ string of the alphabet occurs exactly once. For a binary alphabet ($k=2$), this gives us $2^N / N$ possible sequences (setting aside rotation and reflection).

Unfortunately, it’s not immediately obvious how to find the numeric representations mentioned in the problem, because rotations of a sequence have the same properties but yield different numbers. To solve the question, we can use an algorithm that would generate all the possible de Bruijn sequences for $N = 5$. Given the complexity of this problem, using a computer program or script would be the best approach.

Here’s a simple Python script to compute $S(5)$:

“`
def de_bruijn(k, n):
a = [0] * k * n
sequence = []

def db(t, p):
if t > n:
if n % p == 0:
for j in range(1, p+1):
sequence.append(a[j])
else:
a[t] = a[t – p]
db(t + 1, p)
for j in range(a[t – p] + 1, k):
a[t] = j
db(t + 1, t)
db(1, 1)
return sequence

n = 5
binary_alphabet = 2

# generate the de Bruijn sequence
db_sequence = de_bruijn(binary_alphabet, n)

# find all rotations
rotations = [db_sequence[i:] + db_sequence[:i] for i in range(len(db_sequence))]
# sort them and find the smallest (lexicographically)
smallest_rotation = sorted(rotations)[0]

# convert to a number
S5 = sum(v * 2**i for i, v in enumerate(smallest_rotation[::-1]))

print(S5)
“`

Unfortunately, I don’t have a way to run this code, but it should calculate the required solution – the sum of the unique numeric representations $S(5)$.

This problem is complex because it combines several areas of mathematics including combinatorics, graph theory and even some group theory since we need to eliminate rotations. For such problems, especially when N becomes larger, a computational approach is usually the most feasible method for solving it.

More Answers: