Problem 209: Circular Logic

Mathematical Development

The Permutation

Define

This is a bijection on $\{0,1\}^6$, because from the image $(b,c,d,e,f,g)$ we can recover

Constraint as a Cycle Problem

The condition

means that two consecutive states along an orbit of $\sigma$ cannot both be assigned the value 1. Since $\sigma$ is a permutation, the 64 states decompose into disjoint cycles, and the constraint can be solved independently on each cycle.

Independent Sets on a Cycle

For a cycle of length $n$, the valid assignments are exactly the independent sets of the cycle graph $C_n$. Their number is the Lucas number

where $F_n$ is the Fibonacci sequence.

For the fixed-point case $n = 1$, the condition becomes $\tau(x) \wedge \tau(x) = 0$, so only the assignment $\tau(x) = 0$ is allowed; this matches the convention $L_1 = 1$.

Cycle Structure

A direct computation of the permutation on all 64 bit patterns yields the cycle lengths

Therefore the total number of valid truth tables is

Editorial

The Boolean condition becomes much easier once the input tuples are viewed as nodes of a directed permutation graph. Every tuple points to exactly one successor under $\sigma$, and because $\sigma$ is invertible, those successor chains are actually cycles.

On a single cycle, the rule simply says that no two adjacent positions may both receive the value 1. That is the independent-set count for a cycle graph, which is a Lucas number. So the whole problem reduces to finding the cycle decomposition of a 64-state permutation and multiplying the appropriate Lucas counts.

Pseudocode

Define sigma(x) by decoding the 6 bits of x,
shifting them left, and appending a xor (b and c).

Mark all 64 states as unvisited.
cycle_lengths = empty list

For x from 0 to 63:
    If x is already visited:
        continue

    Follow sigma starting from x until the cycle closes,
    marking states visited and counting the length.
    Append that length to cycle_lengths.

Define Lucas(n):
    If n = 1, return 1
    If n = 2, return 3
    Build upward with the recurrence L_n = L_{n-1} + L_{n-2}

answer = 1
For each length in cycle_lengths:
    answer *= Lucas(length)

Return answer

Complexity Analysis

• Time: $O(64)$ to find the cycle decomposition, plus $O(\max \text{ cycle length})$ to build the Lucas numbers.
• Space: $O(64)$.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    // sigma(a,b,c,d,e,f) = (b,c,d,e,f, a XOR (b AND c))
    // Encode (a,b,c,d,e,f) as a 6-bit integer: a*32 + b*16 + c*8 + d*4 + e*2 + f

    auto sigma = [](int x) -> int {
        int a = (x >> 5) & 1;
        int b = (x >> 4) & 1;
        int c = (x >> 3) & 1;
        int d = (x >> 2) & 1;
        int e = (x >> 1) & 1;
        int f = x & 1;
        int new_f = a ^ (b & c);
        return (b << 5) | (c << 4) | (d << 3) | (e << 2) | (f << 1) | new_f;
    };

    // Find cycle structure
    vector<bool> visited(64, false);
    vector<int> cycle_lengths;

    for (int i = 0; i < 64; i++) {
        if (visited[i]) continue;
        int len = 0;
        int cur = i;
        while (!visited[cur]) {
            visited[cur] = true;
            cur = sigma(cur);
            len++;
        }
        cycle_lengths.push_back(len);
    }

    // For each cycle of length n, count independent sets = Lucas(n)
    // Lucas(1) = 1, Lucas(2) = 3, Lucas(n) = Lucas(n-1) + Lucas(n-2)
    // But Lucas(1) should be 1 for self-loops (tau(x) AND tau(x) = 0 => tau(x) = 0)
    // Standard Lucas: L(1)=1, L(2)=3, L(n)=L(n-1)+L(n-2)

    auto lucas = [](int n) -> long long {
        if (n == 1) return 1;
        if (n == 2) return 3;
        long long a = 1, b = 3;
        for (int i = 3; i <= n; i++) {
            long long c = a + b;
            a = b;
            b = c;
        }
        return b;
    };

    long long answer = 1;
    for (int len : cycle_lengths) {
        answer *= lucas(len);
    }

    cout << answer << endl;
    return 0;
}

"""
Problem 209: Circular Logic

Count 6-input truth tables tau such that
tau(a,b,c,d,e,f) AND tau(b,c,d,e,f, a XOR (b AND c)) = 0
for all inputs.

This is equivalent to counting independent sets on the cycle graph
formed by the permutation sigma on {0,1}^6.
The answer is the product of Lucas numbers over all cycle lengths.
"""


def solve():
    def sigma(x):
        a = (x >> 5) & 1
        b = (x >> 4) & 1
        c = (x >> 3) & 1
        d = (x >> 2) & 1
        e = (x >> 1) & 1
        f = x & 1
        new_f = a ^ (b & c)
        return (b << 5) | (c << 4) | (d << 3) | (e << 2) | (f << 1) | new_f

    visited = [False] * 64
    cycle_lengths = []

    for start in range(64):
        if visited[start]:
            continue
        length = 0
        cur = start
        while not visited[cur]:
            visited[cur] = True
            cur = sigma(cur)
            length += 1
        cycle_lengths.append(length)

    def lucas(n):
        if n == 1:
            return 1
        if n == 2:
            return 3
        a, b = 1, 3
        for _ in range(3, n + 1):
            a, b = b, a + b
        return b

    answer = 1
    for length in cycle_lengths:
        answer *= lucas(length)

    return answer


answer = solve()
assert answer == 15964587728784
print(answer)