Detailed mathematical approach

Problem Summary

Let \(\tau : \{0,1\}^6 \to \{0,1\}\) be a Boolean truth table on six input bits. The condition in the problem is

$\tau(a,b,c,d,e,f)\land\tau\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr)=0,$

for every 6-bit state \((a,b,c,d,e,f)\). In other words, if we define the state transition

$T(a,b,c,d,e,f)=\bigl(b,c,d,e,f,a\oplus(b\land c)\bigr),$

then no state and its successor under \(T\) are both allowed to receive the value 1. The task is to count how many truth tables satisfy this global constraint.

The key point is that the transition graph on the 64 states is not an arbitrary functional graph. It is actually a permutation, so the whole graph splits into disjoint directed cycles. Once those cycle lengths are known, the Boolean counting problem becomes a product of independent cycle counts.

Mathematical Approach

The entire solution is driven by the structure of the six-bit transition. The implementations do not search over truth tables at all; they first decompose the 64 states into cycles, then count admissible 0/1 labelings on each cycle.

The six-bit transition is a permutation

Write the output of \(T\) as \((u,v,w,p,q,r)\). By definition,

$u=b,\quad v=c,\quad w=d,\quad p=e,\quad q=f,\quad r=a\oplus(b\land c).$

These equations can be inverted immediately:

$a=r\oplus(u\land v),\qquad (b,c,d,e,f)=(u,v,w,p,q).$

So every output state has exactly one predecessor. Therefore \(T\) is a bijection on the 64 states, and every connected component of the directed graph is a pure cycle. There are no trees feeding into a cycle, so a cycle decomposition really is the whole story.

From the Boolean condition to a cycle-labeling problem

Consider one cycle of length \(L\):

$s_0\to s_1\to \cdots \to s_{L-1}\to s_0.$

If we set

$x_i=\tau(s_i)\in\{0,1\},$

then the constraint says

$x_i x_{i+1}=0\qquad\text{for all }i\pmod L.$

So on that cycle we must count binary circular strings with no adjacent 1s. This is the same as counting independent sets of a cycle graph with \(L\) vertices.

Different cycles share no states, so their labelings are independent. If a cycle of length \(L\) contributes \(C_L\) admissible labelings, and the permutation decomposition has cycle lengths \(L_1,L_2,\dots,L_k\), then the total number of valid truth tables is simply

$\prod_{j=1}^k C_{L_j}.$

Counting admissible labelings on one cycle

First count binary strings on a path. Let \(P_n\) be the number of length-\(n\) binary strings with no adjacent 1s. A standard last-position split gives

$P_n=P_{n-1}+P_{n-2},\qquad P_0=1,\quad P_1=2.$

Hence

$P_n=F_{n+2},$

where \(F_0=0\), \(F_1=1\), and \(F_{m+2}=F_{m+1}+F_m\).

Now return to a cycle of length \(L\ge 2\). Split into two cases according to the first position.

If \(x_0=0\), then the remaining \(L-1\) positions form an unrestricted path, contributing \(P_{L-1}\) possibilities.

If \(x_0=1\), then both neighbors \(x_1\) and \(x_{L-1}\) must be 0, leaving a path of length \(L-3\), which contributes \(P_{L-3}\) possibilities.

Therefore

$C_L=P_{L-1}+P_{L-3}=F_{L+1}+F_{L-1}.$

The length-1 case also fits this formula: a 1-cycle forces its only state to be 0, so \(C_1=1=F_0+F_2\).

Worked example: the cycle through \(000001\)

One of the actual cycles generated by \(T\) is

$000001\to 000010\to 000100\to 001000\to 010000\to 100000\to 000001,$

so this is a cycle of length 6. The number of admissible truth-table values on these six states is

$C_6=P_5+P_3=F_7+F_5=13+5=18.$

You can read this directly from the split above: either the first state gets value 0 and the other five positions behave like a path, or the first state gets value 1 and its two neighbors are forced to 0, leaving only three free positions in the middle.

The actual decomposition for Problem 209

Running through all 64 states yields the cycle lengths

$1,\ 2,\ 3,\ 6,\ 6,\ 46.$

So the full count is

$C_1\,C_2\,C_3\,C_6^2\,C_{46}.$

Using \(C_L=F_{L-1}+F_{L+1}\), this becomes

$1\cdot 3\cdot 4\cdot 18^2\cdot \bigl(F_{45}+F_{47}\bigr).$

Since \(F_{45}=1134903170\) and \(F_{47}=2971215073\), the final count is

$15\,964\,587\,728\,784.$

How the Code Works

Extracting the cycle lengths

The C++, Python, and Java implementations encode each 6-bit state as an integer from 0 to 63. For each state they compute the successor by shifting the low five bits left and appending the feedback bit \(a\oplus(b\land c)\). A visited array ensures that every state is processed exactly once.

Because the transition is bijective, starting from any unvisited state and repeatedly applying the transition eventually returns to the starting cycle without encountering a tail. The implementation counts how many states appear before the repetition and records that as one cycle length.

Converting cycle lengths into the answer

For each recorded length \(L\), the implementation builds Fibonacci values up to \(F_{L+1}\) and evaluates \(F_{L-1}+F_{L+1}\). Those factors are then multiplied together in a 64-bit integer accumulator.

All three language versions follow the same mathematical plan: decompose the permutation on the 64 states, turn each cycle into an independent no-adjacent-1 counting problem, and multiply the resulting factors.

Complexity Analysis

The cycle decomposition visits each of the 64 states once, so that phase costs \(O(64)\) time and \(O(64)\) memory. The Fibonacci preparation for a cycle of length \(L\) costs \(O(L)\), and the total of all cycle lengths is also 64.

Therefore the overall complexity is \(O(64)\) time and \(O(64)\) space, which is constant for this fixed problem size. Numerically, the largest cycle has length 46, so even the Fibonacci step is tiny.

Footnotes and References

1. Project Euler problem page: Project Euler 209 - Circular Logic
2. Functional graphs: Wikipedia - Functional graph
3. Cycle graphs and their independent sets: Wikipedia - Cycle graph
4. Independent sets: Wikipedia - Independent set
5. Fibonacci numbers: Wikipedia - Fibonacci number