Boolean Chains

In section 7.1.2 The Art of Computer Programming Volume 4A Knuth describes and analyzes boolean chains, which are defined for functions of \(n\) variables \(x_1, x_2, ... x_n\) as a sequence of operations \(x_i = x_{j(i)} \circ_i x_{k(i)}\) for \(n+1 \leq i \leq n + r\), with \(1 \leq j(i) < i, 1 \leq k(i)\) and \(\circ_i\) being any binary operation. He shows that it is sufficient to consider the binary operations \(\land\), \(\lor\), \(\oplus\), \(<\) (bitwise), \(>\) (bitwise).

In Synthesizing a good chain he discusses finding short boolean chains for given target functions, using the example of a 7-segment display for hexadecimal digits; each segment is controlled by a boolean functions of the four inputs of a 4-bit hexadecimal digit.

In order to find a reasonably short boolean chain Knuth describes Algorithm L and Algorithm U, an extension of Algorithm L, which tracks a footprint for each possible function. The footprint is a set of “first operations” that can be achieved with \(n\) input variables and that are part of the shortest chains generating a target function. This footprint can used as a heuristic to greedily pick the next operation. The resulting chain including the new operation can be used as an input for Algorithm U again, resulting in the next operation to pick, etc., until the chain contains all target functions.

This approach generates a boolean chain of length 22 for the 7-segment decimal digit display. Knuth also mentions that David Stevenson found a 21-step chain by picking \(x_{10}\) non-greedily.

I was interested in trying to find an even shorter chain for the display.

I started by using Algorithm L and Algorithm U from exercise 7.1.2-11, but instead of greedily picking the best instruction according to the footprint heuristic for a given chain of length \(l\), I consider the top \(k_l\) best instructions and recurse for each of them in a depth-first search with a maximal depth. As the chain length grows, \(k_l\) becomes gradually smaller. I call this hungry search, because it starts taking big bites, then smaller and smaller bites until it is done.

The idea is that the first few instructions are less likely to be optimal when chosen greedily, so we want to try more of them. But as the chain gets longer the greedy algorithm does a good job of identifying the best next step, so we try fewer and fewer alternatives at every length. This makes the search space manageable.

The question then becomes: how do we sort the instructions at every step to determine the “top \(k_l\)” ones to try? I’ve considered three criteria in order of relevance:

1. The minimal cost of all target functions containing the instruction in the footprint. Lower is better, assume infinity if the instruction is not part of the footprint for any target function.
2. The number of target function footprints that contain the instruction. Higher is better.
3. The index of the instruction based on the order Algorithm U generated them in. Some generation orders might be better than others, this could be a heuristic in its own right, but I haven’ investigated this. I’ve used the order from Algorithm U in the book.

The book greedily picks the instruction that appears in most target footprints, preferring a lower minimal cost. I experimented with ordering by minimal cost first and then prefer a higher number of matching footprints. To break ties I also ordered by the negative of the index of generated instructions. That index depends on the order in which the instructions are generated; so this criterion really only makes the order deterministic.

Here’s pythonesque pseudo-code to illustrate the general approach. The complete() function yields True if all target functions are fulfilled. And the sort() function orders the instructions as outlined above.

# the first 4 are irrelevant, as x1, x2, x3, x4 are given
BYTE_SIZE = [0, 0, 0, 0, 5, 5, 5, 5, 5, 3, 3, 3, 3, 1, 1, 1, ...]

def hungry_search(chain):
    if complete(chain):
        print(chain)
        return

    next_instructions, footprints, minimal_costs = algorithm_U(chain)
    sort(next_instructions, footprints, minimal_costs)
    for i in range(BITE_SIZE[len(chain)]):
         hungry_search(chain + [next_instructions[i]])

hungry_search([x1, x2, x3, x4])

There are some ways to reduce the search space further, namely by providing a maximal length and bailing out whenever it becomes clear that a solution can’t be found on the path we’re on, but those are orthogonal improvements.

With bite sizes 5, 5, 5, 5, 5, 3, 3, 3, 3, 1, 1, … this approach generated several chains of length 20, one step shorter than the previously shortest chain in the book, the first one:

Let’s use that chain as an example for the algorithm:

For the first step the following instructions are possible and ordered as described, the top 10 are shown. The numbers in brackets are:

1. minimal cost of target functions containing the instruction in their footprint
2. number of target footprints containing the instruction
3. the index in the array of all generated next instructions

  * x5 = x2 ^ x3 = 0011110000111100 [4 4 19]
    x5 = x3 > x4 = 0010001000100010 [4 2 27]
    x5 = x2 > x4 = 0000101000001010 [4 2 22]
    x5 = x1 ^ x3 = 0011001111001100 [5 4 9]
    x5 = x2 & x3 = 0000001100000011 [5 3 15]
    --- bite size ---
    x5 = x1 < x4 = 0101010100000000 [5 3 11]
    x5 = x3 < x4 = 0100010001000100 [5 2 26]
    x5 = x2 < x4 = 0101000001010000 [5 2 21]
    x5 = x2 | x3 = 0011111100111111 [5 2 18]
    x5 = x1 ^ x4 = 0101010110101010 [5 2 14]
    ...

Of that list we’ll consider the top 5, because 5 is the bite size for that chain length. The top instruction has a minimal cost of 4, and of the instructions that have minimal cost of 4 it also appears in 4 target function footprints. In this case is the greedy algorithm also picks the same instruction, because in its ordering it also ends up on top.

Having chosen the first instruction (indicated by the *) we recurse and enumerate the next possible instructions, ordering them as before.

  * x6 = x1 | x5 = 0011110011111111 [3 3 18]
    x6 = x3 > x4 = 0010001000100010 [3 1 31]
    x6 = x2 > x4 = 0000101000001010 [3 1 26]
    x6 = x1 < x4 = 0101010100000000 [4 4 11]
    x6 = x2 < x4 = 0101000001010000 [4 2 25]
    --- bite size ---
    x6 = x1 ^ x2 = 0000111111110000 [4 2 4]
    x6 = x3 < x4 = 0100010001000100 [4 1 30]
    x6 = x4 ^ x5 = 0110100101101001 [5 3 38]
    x6 = x4 & x5 = 0001010000010100 [5 3 34]
    x6 = x2 ^ x4 = 0101101001011010 [5 3 28]
    ...

Here we already see the hungry search diverge from the greedy search due to different ordering. The greedy search would have chosen the 4th instruction \(x_6 = x_1 < x_4\), because it appears in 4 target footprints, in fact it’s the only one. However, three instructions beat it on the minimal cost, so in this heuristic we’ll look at them first.

We take the first one again and recurse.

    x7 = x3 > x4 = 0010001000100010 [2 2 35]
    x7 = x2 > x4 = 0000101000001010 [2 2 25]
  * x7 = x4 ^ x5 = 0110100101101001 [4 3 45]
    x7 = x4 & x5 = 0001010000010100 [4 3 41]
    x7 = x1 < x4 = 0101010100000000 [4 3 11]
    --- bite size ---
    x7 = x1 ^ x3 = 0011001111001100 [4 3 9]
    x7 = x3 & x6 = 0011000000110011 [4 2 38]
    x7 = x2 < x6 = 0011000011110000 [4 2 29]
    x7 = x2 < x4 = 0101000001010000 [4 2 24]
    x7 = x1 ^ x2 = 0000111111110000 [4 2 4]
    ...

Here we again picked the first one, recursed, searched for solutions, at some point came back to this point, tried the second instruction, and finally picked the third instruction, which turned out to be the one in which we found the solution, so let’s pick that one and move on to the next step.

    x8 = x3 > x7 = 0001001000010010 [2 3 52]
    x8 = x3 > x4 = 0010001000100010 [2 2 45]
  * x8 = x2 > x7 = 0000011000000110 [2 2 40]
    x8 = x2 > x4 = 0000101000001010 [2 1 30]
    x8 = x3 & x6 = 0011000000110011 [3 1 47]
    --- bite size ---
    x8 = x1 ^ x3 = 0011001111001100 [3 1 9]
    x8 = x3 < x7 = 0100100001001000 [4 3 51]
    x8 = x3 & x7 = 0010000100100001 [4 3 50]
    x8 = x2 < x7 = 0110000001100000 [4 3 39]
    x8 = x1 < x4 = 0101010100000000 [4 3 11]
    ...

Again we try the first two, find nothing, try the third, and so on. Here are the lists at every chosen step that lead to the given solution. I’ve also added [target] whenever the result is a target function. It’s interesting that the first instruction of the next step would’ve been a target function, but it was not the step that yielded the solution, likely because it the instruction chosen here would’ve been outside of the bite size window in the next step, which drops to 3 after this step. [Note: this chain would not have been found with the culling after target functions, see under improvements. Which is a data point against that optimization.]

    x9 = x6 | x8 = 0011111011111111 [1 1 84] [target]
    x9 = x3 & x6 = 0011000000110011 [3 1 51]
    x9 = x1 ^ x3 = 0011001111001100 [3 1 9]
  * x9 = x3 < x7 = 0100100001001000 [4 3 55]
    x9 = x3 & x7 = 0010000100100001 [4 3 54]
    --- bite size ----
    x9 = x1 < x4 = 0101010100000000 [4 3 11]
    x9 = x1 ^ x2 = 0000111111110000 [4 3 4]
    x9 = x6 & x7 = 0010100001101001 [4 2 78]
    x9 = x3 > x7 = 0001001000010010 [4 2 56]
    x9 = x2 < x7 = 0110000001100000 [4 2 44]
    ...

As mentioned, the bite size drops to 3 at this point.

  * x10 = x6 | x8 = 0011111011111111 [1 1 99] [target]
    x10 = x1 ^ x2 = 0000111111110000 [3 3 4]
    x10 = x5 | x9 = 0111110001111100 [3 2 91]
    --- bite size ---
    x10 = x4 ^ x9 = 0001110100011101 [3 2 86]
    x10 = x1 ^ x9 = 0100100010110111 [3 2 33]
    x10 = x6 > x9 = 0011010010110111 [3 1 103]
    x10 = x3 & x6 = 0011000000110011 [3 1 61]
    x10 = x1 ^ x3 = 0011001111001100 [3 1 9]
    x10 = x1 < x4 = 0101010100000000 [4 2 11]
    x10 = x5 ^ x9 = 0111010001110100 [4 1 92]
    ...

  * x11 = x1 ^  x2 = 0000111111110000 [3 3 4]
    x11 = x5 |  x9 = 0111110001111100 [3 2 100]
    x11 = x4 ^  x9 = 0001110100011101 [3 2 92]
    --- bite size ---
    x11 = x1 ^  x9 = 0100100010110111 [3 2 33]
    x11 = x9 < x10 = 0011011010110111 [3 1 118]
    x11 = x6 >  x9 = 0011010010110111 [3 1 112]
    x11 = x3 & x10 = 0011001000110011 [3 1 76]
    x11 = x3 &  x6 = 0011000000110011 [3 1 65]
    x11 = x1 ^  x3 = 0011001111001100 [3 1 9]
    x11 = x1 <  x4 = 0101010100000000 [4 2 11]
    ...

  * x12 =  x5 |  x9 = 0111110001111100 [2 2 108]
    x12 = x10 & x11 = 0000111011110000 [3 2 149]
    x12 =  x6 & x11 = 0000110011110000 [3 2 127]
    --- bite size ---
    x12 =  x1 <  x4 = 0101010100000000 [3 2 10]
    x12 =  x9 & x11 = 0000100001000000 [3 1 144]
    x12 =  x9 < x10 = 0011011010110111 [3 1 141]
    x12 =  x6 > x11 = 0011000000001111 [3 1 128]
    x12 =  x6 >  x9 = 0011010010110111 [3 1 124]
    x12 =  x4 ^ x11 = 0101101010100101 [3 1 103]
    x12 =  x4 ^  x9 = 0001110100011101 [3 1 95]
    ...

  * x13 = x11 < x12 = 0111000000001100 [1 1 170] [target]
    x13 =  x4 & x12 = 0101010001010100 [3 2 113]
    x13 = x11 & x12 = 0000110001110000 [3 1 169]
    --- bite size ---
    x13 = x10 & x11 = 0000111011110000 [3 1 165]
    x13 =  x9 & x11 = 0000100001000000 [3 1 160]
    x13 =  x9 < x10 = 0011011010110111 [3 1 157]
    x13 =  x8 | x12 = 0111111001111110 [3 1 155]
    x13 =  x7 > x11 = 0110000000001001 [3 1 146]
    x13 =  x6 > x11 = 0011000000001111 [3 1 138]
    x13 =  x6 & x11 = 0000110011110000 [3 1 137]

  * x14 =  x4 & x12 = 0101010001010100 [3 3 126]
    --- bite size ---
    x14 = x11 & x12 = 0000110001110000 [3 1 206]
    x14 = x10 & x11 = 0000111011110000 [3 1 200]
    x14 =  x9 & x11 = 0000100001000000 [3 1 192]
    x14 =  x9 < x10 = 0011011010110111 [3 1 189]
    x14 =  x8 | x13 = 0111011000001110 [3 1 187]
    x14 =  x8 | x12 = 0111111001111110 [3 1 182]
    x14 =  x7 > x13 = 0000100101100001 [3 1 174]
    x14 =  x7 < x13 = 0001000000000100 [3 1 173]
    x14 =  x7 & x13 = 0110000000001000 [3 1 172]
    ...

  * x15 = x13 ^ x14 = 0010010001011000 [2 1 234]
    --- bite size ---
    x15 = x11 | x14 = 0101111111110100 [2 1 231]
    x15 = x10 > x14 = 0010101010101011 [2 1 223]
    x15 =  x6 > x14 = 0010100010101011 [2 1 175]
    x15 =  x6 > x11 = 0011000000001111 [2 1 168]
    x15 =  x1 & x14 = 0000000001010100 [2 1 44]
    x15 =  x9 & x11 = 0000100001000000 [3 1 207]
    x15 =  x4 ^  x9 = 0001110100011101 [3 1 127]
    x15 =  x1 <  x4 = 0101010100000000 [3 1 10]
    x15 = x13 | x14 = 0111010001011100 [infinity 0 233]

  * x16 =  x7 > x15 = 0100100100100001 [1 1 215] [target]
    --- bite size ---
    x16 = x11 | x14 = 0101111111110100 [2 1 267]
    x16 = x10 > x14 = 0010101010101011 [2 1 259]
    x16 =  x6 > x14 = 0010100010101011 [2 1 197]
    x16 =  x6 > x11 = 0011000000001111 [2 1 191]
    x16 =  x1 & x14 = 0000000001010100 [2 1 44]
    x16 =  x9 & x11 = 0000100001000000 [3 1 240]
    x16 =  x4 ^  x9 = 0001110100011101 [3 1 142]
    x16 =  x1 <  x4 = 0101010100000000 [3 1 10]
    x16 = x13 | x14 = 0111010001011100 [infinity 0 272]
    ...

  * x17 = x11 | x14 = 0101111111110100 [2 1 295]
    --- bite size ---
    x17 = x10 > x14 = 0010101010101011 [2 1 285]
    x17 =  x6 > x14 = 0010100010101011 [2 1 218]
    x17 =  x6 > x11 = 0011000000001111 [2 1 213]
    x17 =  x1 & x14 = 0000000001010100 [2 1 44]
    x17 =  x9 & x11 = 0000100001000000 [3 1 264]
    x17 =  x5 ^ x16 = 0111010100011101 [3 1 201]
    x17 =  x4 | x16 = 0101110101110101 [3 1 178]
    x17 =  x4 ^  x9 = 0001110100011101 [3 1 156]
    x17 =  x1 >  x9 = 0000000010110111 [3 1 30]

  * x18 =  x6 > x17 = 0010000000001011 [1 1 246] [target]
    --- bite size ---
    x18 =  x1 & x14 = 0000000001010100 [2 1 44]
    x18 =  x9 & x17 = 0100100001000000 [3 1 313]
    x18 =  x9 & x11 = 0000100001000000 [3 1 298]
    x18 =  x5 ^ x16 = 0111010100011101 [3 1 217]
    x18 =  x4 | x16 = 0101110101110101 [3 1 191]
    x18 =  x4 ^  x9 = 0001110100011101 [3 1 169]
    x18 =  x1 >  x9 = 0000000010110111 [3 1 30]
    x18 =  x1 <  x4 = 0101010100000000 [3 1 10]
    x18 = x16 ^ x17 = 0001011011010101 [infinity 0 357]
    ...

  * x19 =  x1 & x14 = 0000000001010100 [2 1 44]
    --- bite size ---
    x19 =  x9 & x17 = 0100100001000000 [3 1 330]
    x19 =  x9 & x11 = 0000100001000000 [3 1 315]
    x19 =  x5 ^ x16 = 0111010100011101 [3 1 228]
    x19 =  x4 | x16 = 0101110101110101 [3 1 199]
    x19 =  x4 ^  x9 = 0001110100011101 [3 1 177]
    x19 =  x1 >  x9 = 0000000010110111 [3 1 30]
    x19 =  x1 <  x4 = 0101010100000000 [3 1 10]
    x19 = x16 ^ x18 = 0110100100101010 [infinity 0 385]
    x19 = x16 | x18 = 0110100100101011 [infinity 0 384]
    ...

  * x20 = x9 ^ x19 = 0100100000011100 [1 1 356] [target]
    --- bite size ---
    x20 = x9 & x17 = 0100100001000000 [3 1 348]
    x20 = x9 & x11 = 0000100001000000 [3 1 333]
    x20 = x7 & x17 = 0100100101100000 [3 1 292]
    x20 = x7 & x11 = 0000100101100000 [3 1 277]
    x20 = x5 ^ x16 = 0111010100011101 [3 1 238]
    x20 = x4 > x19 = 0101010100000001 [3 1 216]
    x20 = x4 | x16 = 0101110101110101 [3 1 208]
    x20 = x4 ^  x9 = 0001110100011101 [3 1 186]
    x20 = x2 ^ x19 = 0000111101011011 [3 1 120]
    ...

  * x21 = x10 ^ x20 = 0111011011100011 [3 2 395]
    --- bite size ---
    x21 = x17 & x20 = 0100100000010100 [3 1 460]
    x21 = x16 ^ x20 = 0000000100111101 [3 1 458]
    x21 = x14 ^ x20 = 0001110001001000 [3 1 439]
    x21 = x14 > x20 = 0001010001000000 [3 1 438]
    x21 = x12 > x20 = 0011010001100000 [3 1 425]
    x21 = x12 ^ x16 = 0011010101011101 [3 1 419]
    x21 = x10 ^ x14 = 0110101010101011 [3 1 387]
    x21 =  x9 & x17 = 0100100001000000 [3 1 373]
    x21 =  x9 & x11 = 0000100001000000 [3 1 358]
    ...

  * x22 = x17 > x21 = 0000100100010100 [2 2 517]
    --- bite size ---
    x22 = x14 ^ x21 = 0010001010110111 [2 1 484]
    x22 = x19 < x21 = 0111011010100011 [infinity 0 524]
    x22 = x18 ^ x21 = 0101011011101000 [infinity 0 523]
    x22 = x18 | x21 = 0111011011101011 [infinity 0 522]
    x22 = x18 ^ x20 = 0110100000010111 [infinity 0 521]
    x22 = x18 | x20 = 0110100000011111 [infinity 0 520]
    x22 = x18 | x19 = 0010000001011111 [infinity 0 519]
    x22 = x17 ^ x21 = 0010100100010111 [infinity 0 518]
    x22 = x17 & x21 = 0101011011100000 [infinity 0 516]
    ...

  * x23 = x14 ^ x22 = 0101110101000000 [1 1 522] [target]
    --- bite size ---
    x23 =  x2 ^ x22 = 0000011000011011 [1 1 146] [target]
    x23 = x20 ^ x22 = 0100000100001000 [infinity 0 570]
    x23 = x20 | x22 = 0100100100011100 [infinity 0 569]
    x23 = x19 ^ x22 = 0000100101000000 [infinity 0 568]
    x23 = x19 | x22 = 0000100101010100 [infinity 0 567]
    x23 = x19 < x21 = 0111011010100011 [infinity 0 566]
    x23 = x18 | x22 = 0010100100011111 [infinity 0 565]
    x23 = x18 ^ x21 = 0101011011101000 [infinity 0 564]
    x23 = x18 | x21 = 0111011011101011 [infinity 0 563]
    ...

  * x24 =  x2 ^ x22 = 0000011000011011 [1 1 151] [target]
    --- bite size ---
    x24 = x21 ^ x23 = 0010101110100011 [infinity 0 628]
    x24 = x20 ^ x23 = 0001010101011100 [infinity 0 627]
    x24 = x20 | x23 = 0101110101011100 [infinity 0 626]
    x24 = x20 < x23 = 0001010101000000 [infinity 0 625]
    x24 = x20 ^ x22 = 0100000100001000 [infinity 0 624]
    x24 = x20 | x22 = 0100100100011100 [infinity 0 623]
    x24 = x19 ^ x23 = 0101110100010100 [infinity 0 622]
    x24 = x19 ^ x22 = 0000100101000000 [infinity 0 621]
    x24 = x19 | x22 = 0000100101010100 [infinity 0 620]
    ...

After some more optimizations of the code, based on the program for the exhaustive search (see below), bigger bite sizes were feasible. The hungry search with bite sizes 10, 9, 8, 7, 6, 5, … found several chains of length 19. The first solution of that kind was:

The instruction \(x_5 = x_3 < x_4\) is the 7th instruction in the order of the heuristic heuristic, that’s why it wasn’t considered for a bite size of 5. This illustrates that good solutions can easily be missed, if the “right” instruction is just outside of the bite size window, which can happen at any chain length in the hungry search.

With infinite bite sizes at every step the hungry search would become an exhaustive search and find all optimal solutions. But as the bite sizes increase, the search space increases rapidly, which in combination with the expensive Algorithm U makes large bite sizes computationally infeasible.

A faster exhaustive search is described below, it doesn’t use any heuristic, because it looks at all relevant instructions anyway. That allows it to traverse much larger search spaces.

The search space for these chains grows rather quickly, but we can reduce it in a few ways:

1. We estimate the length of the minimal chain to be just one or two more than the best chain we already found for the display with one less digit; call this maximal length \(m\).
2. Let \(t = 7\) be the number of target functions and \(w\) the number of target functions not yet contained in the chain we’re currently looking at, then as soon as we see a chain of length \(c\) with \(c + w > m\) we can stop pursuing this branch, because any chain fulfilling the remaining targets would exceed length \(m\).

3. A lot of equivalent chains can be found in different orders, which wastes a lot of computation. I consider two chains equivalent if the set of the functions they generate are equal. There are chains for which one or more functions can be derived with two or more instructions based on previous functions, but those variants can easily be generated from the set of functions.

   It is sufficient to apply every function \(f\) only at the shortest length it is found in the current branch. That means if we are at \(c = 3\) and encounter, say, \(f =\) 0110 1001 0110 1010 for the first time, then we apply it and recurse to \(c + 1\). If we afterwards pick a different function at the same length \(c\) and down the line \(f\) reappears, then we ignore it. Even if the function results from a different instruction at that time, we could’ve just chosen \(f\) at length \(c\) and done the same steps afterwards for the same complete chain length.

   Once we backtrack to length \(c-1\), however, we must forget about all \(f\) we’ve applied at that length in this branch, because they might re-appear in a different branch for the first time (in that branch) and there result in different chains.

   This property makes it very easy to maintain all new instructions in a single, shared array, to which we only ever add at each level of recursion and then move the length back on backtracking. We also can simply start at the instruction following the last instruction applied at the previous recursion level, automatically ensuring that we’re not duplicating work.

   A side effect of this is that the number of relevant branches at every chain length usually goes down as we try more and more instructions at that length. This is a minor challenge in trying to generate roughly equal chunks for parallelization.

4. Newly generated instructions at every length will still duplicate some functions we’ve seen before, e.g. if we chose \(x_4 = x_1 \oplus x_2\), then \(x_4 \oplus x_1\) and \(x_4 \oplus x_2\) would be new instructions at the next length, but they’d duplicate \(x_2\) and \(x_1\) respectively. The same is true for any function derived on a different path in the previous chain.

   To ignore those duplicates we can maintain a bit set of all the functions we’ve already seen in the chain up to that point, and it turns out this can be the same set we use for 3. to avoid revisiting functions down the line.

5. If we encounter a target function at any length, then we can try that one and recurse, but after that the entire branch for that length can be culled. The reason is that the target function we tried in the last loop now can’t ever be used again in other chains along this branch, making a complete chain impossible. This is due to point 3.

   Note: this optimization is dangerous for hungry search, because of the bite sizes, but for the exhaustive search it is safe.

This algorithm generates all unique boolean chains for inputs \(x_k\), \(1 \leq k \leq n\), \(n \geq 2\) up to a maximum length of \(m\) in order to find boolean chains that contain target functions \(f_k\), \(1 \leq k \leq t\). Let the inputs be distinct from the target functions, otherwise just remove them from the target functions.

The algorithm generates all relevant boolean chains in depth-first manner, but all the data can be shared across the different lengths of the chain.

Let \(c\) be the length of the current chain at any time, including the \(n\) inputs.

\(I(c)\) is a 0-based array of available functions that can be generated with the instructions based on the functions in the chain so far for the current chain of length \(c\). \(N(c)\) is the relevant length of that array.

\(C(i)\) is a 0-based array of indexes into \(I\), for each step \(0 \leq i < c\) of the current chain of length \(c\). Therefore \(I(C(0))\), \(I(C(1))\), \(I(C(2))\), … is the actual chain.

\(S\) is a set of functions we’ve seen already and don’t need to try again in this branch.

\(F = \{f_k \, | \, 1 \leq k \leq t\}\) is the set of target functions.

Finally, \(w(c)\) is the number of target functions not yet in the current chain of length \(c\).

S1. [Initialize.] Set \(c \leftarrow n\) and \(w(c) \leftarrow |F|\) to count all the target functions we have yet to discover. Also set \(I(k) \leftarrow x_{k+1}\), and \(C(k) \leftarrow k\) for \(0 \leq k < n\).

Build possible instructions of all combinations of the first \(n-1\) inputs. The instructions involving the \(n\text{-th}\) input will be added by the main loop. First we set \(S \leftarrow \emptyset\) and \(N(0) \leftarrow n\) then for \(1 \leq k < n\) we add new instructions with Algorithm A with input \(k\).

S2. [Cull search?] If \(c + w > m\) we can’t win anymore, stop this branch and go to S8.

S3. [Found solution?] If \(w(c) = 0\) we have found a solution, print it. Go to S8.

S4. [Add new possible instructions.] Run Algorithm A with input \(c\).

S5. [Prepare looping on the next instruction.] Set \(C(c) \leftarrow C(c-1)\), because we don’t need to try any instructions we already tried during the last step.

S6. [Pick the next instruction.] Set \(C(c) \leftarrow C(c) + 1\). If \(C(c) \geq N(c)\) go to S7. Otherwise if \(C(c) \in F\) then we have found a new target function, set \(w(c+1) \leftarrow w(c) - 1\) otherwise \(w(c+1) \leftarrow w(c)\). Finally set \(c \leftarrow c + 1\) and go to S2.

S7. [Clean up function set.] Set \(S \leftarrow S - \{ I(j) \, | \, N(c-1) \leq j < N(c)\}\) to forget about all the functions we’ve seen at this chain length in this branch.

S8. [Backtrack.] Set \(c \leftarrow c - 1\). If \(c < n\) terminate the algorithm, otherwise go to S6.

This adds new possible instructions to the array \(I\) for a given chain \(C\) with length \(l\), which is the input to the algorithm, given all the arrays set up in Algorithm S.

A1. [Initialize.] Set \(N(l) \leftarrow N(l-1)\).

A2. [Loop on instructions.] Set \(h \leftarrow I(C(l))\) and for \(0 \leq j < l\), set \(g \leftarrow I(C(j))\) and do step A3 for \(f = g \, \& \, h\), \(f = g \, | \, h\), \(f = g \oplus h\), \(f = \overline{g} \, \& \, h\), and \(f = g \, \& \, \overline{h}\).

A3. [Add instruction if new.] If \(f \not\in S\) set \(S \leftarrow S \cup \{f\}\), \(I(N(l)) \leftarrow f\), and \(N(l) \leftarrow N(l) + 1\).

The latest version of this program generates around 510-530 million chains per second on my MacBook Air 15" (M2, 2023). On AWS Batch with Fargate capacity on 1 vCPU it generates around 200-230 million chains per second; so about 51-59 thousand million chains per second across 256 jobs.

The program might be suitable for the GPU, but I have no experience with GPU programming.

Note: the runs of 14 digits and the first 10% of the 15 digits on AWS ECS use the version that didn’t yet stop the branch after finding a target function; that version generated about 70-80% more chains than the newer version.

Thanks to BOINC Central for providing computing capacity for this search!

With bite sizes 15, 14, 13, 12, 11, 10, 2, 2, 2, 2, 2, 2, 1, …

With bite sizes 15, 15, 13, 13, 10, 10, 8, 8, 6, 6, 3, 3, 1, …

With bite sizes 10, 9, 8, 7, 6, 5, 4, 3, 3, 2, 2, 2, 1, …

Note: the 15 digits search for length 18 is noticeably faster than the one for length 17, this is because the one for length 18 already employed the optimization of avoiding Algorithm U if the next step must be a target function. The same is true for the 16 digits search of length 18, its version was more efficient than the one for length 19.

With bite sizes 31, 31, 31, 11, 5, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 3, 3, 2, 1.

No chains were found for those bite sizes. I think that’s a strong indicator that there are no solutions of length 18, because the first 4 bite sizes were pretty big and would’ve found all the optimal solutions for lower number of digits. Nonetheless this is no proof, I’m still trying to do an exhaustive search for 16 digits, see above.

I tracked some statistics on the number of new instructions encountered at different lengths and the number of chains generated. For the decimal display for 13 digits, searching to a maximal length of \(m=19\) the program looked at 15,586,512,093,540 chains, The exact number depends on the order in which instructions are generated, and the following table provides some statistics on the number of newly added instructions at every length.

The main takeaway is that the branching factor doesn’t grow much as the chains get longer, because so many instructions result in the same functions and we ignore different orders of the same set of functions. The table is slightly misleading, however, as the number of actual branches will be roughly the sum of these newly added instructions up to that length, e.g. at length 8 on average \(30+8+10+11+12 = 71\).

That the numbers go down again after length 12 is due to the algorithm stopping at a max length of 19 and bailing out once a chain has no hope of generating all 7 target functions by length 10 anymore (12 = 19 - 7 target functions). So fewer and fewer branches make it to those higher lengths.

All 40 unique optimal chains of length 11: chains-10-15.txt

All 1,079 unique optimal chains of length 12: chains-11-16.txt

All 75 unique optimal chains of length 14: chains-12-18.txt

All 4 unique optimal chains of length 15: chains-13-19.txt

This chain almost solves the 15 or even 16 digit case, with the top-left segment missing from the E and the top segment of the F slipped to the top-right. So close!

All 71 unique optimal chains of length 16: chains-14-20.txt

1 unique optimal set of functions of length 17: chains-15-21.txt

428 unique chains of length 18 that the hungry search found: chains-15-22.txt.

A chain of length 19 found by the hungry search:

11 unique chains of length 19 that the hungry search found: chains-16-23.txt, not exhaustive. The exhaustive search for a chain of length 18 proves these chain lengths are optimal.

Total chains generated: 934,236,665,700

Number of unique optimal sets of functions: 1270

The minimal length is 13, one step shorter than the solution known in the book.

Here is the first one found:

Hungry search found chains of length 15, two steps shorter than the one in the book, but no guarantees that it is minimal.

Here is the first one found: