Circular logic


Project Euler problem 209 asks:

How many 6-input binary truth tables, \(τ\), satisfy the formula $$ τ(a, b, c, d, e, f) ∧ τ(b, c, d, e, f, a ⊕ (b ∧ c)) = 0 $$ for all 6-bit inputs \((a, b, c, d, e, f)\)?

Spoilers below.

The formulae are all of the form \(τ(A) ∧ τ(B) = 0\) for two truth table rows \(A\) and \(B\). In other words, any truth table satisfying these formulae must assign true to at most one of \(τ(A)\) and \(τ(B)\). Each formula thus specifies a constraint joining two rows of the truth table. What happens if we plot all 64 truth table rows as nodes in a graph, with the constraints as edges? Each satisfying truth table would correspond to a colouring of the nodes of the graph with the colours black (representing true) and white (representing false), such that no two black nodes are adjacent.

The web site provides a handy way to draw this graph:

def chart_url_209():
    """Return a Ravenbrook Chart URL for the graph generated from Project
    Euler problem 209.

    edges = []
    for i in range(1 << 6):
        a, b, c = i >> 5 & 1, i >> 4 & 1, i >> 3 & 1
        j = (i << 1 & 63) + a ^ (b & c)
        if i != j: # Limitation of (no self edges)
            edges.append('{},{}'.format(i, j))
    return ''.join([''
                    '&chl=', '|'.join(map('{:06b}'.format, range(1 << 6))),
                    '&che=', '|'.join(edges)])

And here’s the graph:

In order to count the number of truth tables in the original problem, we need to count the ways of two-colouring the nodes of this graph such that no two black nodes are adjacent. The graph is made up of six components, and each component can be coloured independently. So the total number of colourings is the product of the number of colourings of each component. You’ll observe that the graph is cyclic, with cycles of length 1, 2, 3, 6, 6, and 46. So the problem reduces to counting the number of ways there are to two-colour a cycle of length \(n\) such that no two black nodes are adjacent.

How to do that? Well, one way to count combinatorial arrangements is to describe a process for building an arbitrary arrangement satisfying all the constraints. The choices made in constructing that arrangement can be used to compute the number of arrangements: in the simplest cases, by multiplying the choices at each step. Here we want to make an arrangement of \(n\) nodes in a cycle, with \(k\) indistinguishable black nodes and \(n−k\) indistinguishable white nodes (where \(0 \le k \le \lfloor {n \over 2} \rfloor\)), such that no two black nodes are adjacent. Here's a procedure for producing such an arrangement:

  1. Place the \(k\) black nodes and \(k\) of the white nodes alternating in a line. There is just one way to do this.
  2. Call each of the \(k\) white nodes in the line a ‘bucket’. Distribute the remaining \(n − 2k\) white nodes among the \(k\) buckets. There are \(n−k−1 \choose k−1\) ways to do this.1
  3. Pick a position in the cycle for the first black object to go. There are \(n\) positions to pick from.

There are \(n {n−k−1 \choose k−1}\) ways to carry out this process. But the process produces each arrangement \(k\) times, because any of the \(k\) black objects in the final arrangement could have been the ‘first’ black object. So the total number of arrangements is \({n \over k} {n−k−1 \choose k−1}\).

def combinations(n, k):
    """Return C(n, k), the number of combinations of k out of n."""
    c = 1
    k = min(k, n - k)
    for i in range(1, k + 1):
        c *= n - k + i
        c //= i
    return c

def cyclic_nonadjacent_combinations(n, k):
    """Return the number of ways to choose k elements from a cycle of
    length n, such that none of the chosen elements are adjacent.

    if n < 0 or k < 0 or n - k < k: return 0
    if k == 0: return 1
    return n * combinations(n - k - 1, k - 1) // k

def cyclic_nonadjacent_two_colourings(n):
    """Return the number of ways to two-colour a cycle of length n such
    that no black nodes are adjacent.

    return sum(cyclic_nonadjacent_combinations(n, k) for k in range(n // 2 + 1))

Let’s check that for some small values of \(n\):

>>> [cyclic_nonadjacent_two_colourings(n) for n in (2, 3, 4)]
[3, 4, 7]

This solves the problem in 125 µs:

def problem209():
    """Return the answer to Project Euler Problem 209."""
    c = cyclic_nonadjacent_two_colourings
    return c(1) * c(2) * c(3) * c(6) ** 2 * c(46)

>>> from timeit import timeit
>>> timeit(problem209)

But is there more to these counts of cyclic nonadjacent two-colourings? Let’s compute a few more values and look them up in the On-Line Encyclopedia of Integer Sequences.

>>> [cyclic_nonadjacent_two_colourings(n) for n in range(1, 16)]
[1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364]

These are are the Lucas numbers starting with 1 and 3 (A000204): in particular, each number is the sum of the previous two. This is because we can adopt the following procedure to generate the cycles of length \(n\). We take each cycle of length \(n-1\), cut it at a distinguished edge, and insert a white node. In these cases the neighbours of the inserted node are not both black (since they were adjacent in the smaller cycle). We also take each cycle of length \(n-2\), duplicate a distinguished node, and insert a node of the opposite colour between the duplicates. In these cases either the inserted node is black, or else it’s white with both neighbours black. (Thus no duplicates arise in the procedure.) The figure below shows how this works in the case of \(n = 4\).

  1.  See here for an explanation for this formula.