Counting universal n-ary logic gates

Question

Background

A classical logic gate is an idealized electronic device implementing a Boolean function, i.e. one that takes a certain number of Boolean inputs and outputs a Boolean. We only consider two-input logic gates in this challenge.

There are \$2^{2 \times 2} = 16\$ distinct two-input logic gates (2×2 input combinations and 2 possible outputs for each input combination). Out of the 16, only two, namely NAND and NOR gates, are universal, in the sense that you can build arbitrary circuits (any Boolean function) by composing the single type of gates. CGCCers might recognize NAND gates because we had a few challenges to build arbitrary circuits out of them.

NAND | 0   1      NOR | 0   1
-----+-------    -----+-------
  0  | 1   1       0  | 1   0
  1  | 1   0       1  | 0   0

We can generalize the concept of logic gates to n-ary inputs and outputs instead of Booleans, for example ternary for \$n=3\$. (Physical three-state circuits are also being studied.)

For ternary logic gates, the allowed states are often written as - 0 +. There are \$3^{3 \times 3} = 19683\$ distinct ternary logic gates in total, and Craig Gidney managed to enumerate 3774 universal ternary logic gates out of the 19683. (Full C# code)

^{Typos in the blog post and an off-by-one error corrected thanks to @AnttiP}

One such logic gate looks like this (named tand in the blog post):

tand | -   0   +
-----+-----------
  -  | 0   +   +
  0  | +   +   +
  +  | +   +   -

Another looks like this: (X can take any value out of -0+. All three gates represented by this pattern are universal.)

  ?  | -   0   +
-----+-----------
  -  | +   -   0
  0  | X   -   -
  +  | +   +   -

On the other hand, Malbolge's Crazy operator is NOT universal.

 crz | -   0   +
-----+-----------
  -  | 0   -   -
  0  | 0   -   +
  +  | +   +   0

For \$n=1\$, there is only one possible logic gate (constant), and it is trivially universal because the one logic gate can build every possible (the only one) logic gate.

Challenge

Given the value of \$n \ge 1\$, compute the number of distinct universal n-ary logic gates.

Standard code-golf rules apply. The shortest code in bytes wins. Note that your code must theoretically calculate the answer for any valid input, when run in an idealized machine (integers and/or floats have unlimited precision) with enough but finite time and memory.

The known values are:

1 -> 1
2 -> 2
3 -> 3774
4 -> 942897552 (first calculated by @AnttiP, needs cross-check)

Answer 1

Python 3.8 (pre-release), 287 282 242 bytes

^{-5 bytes thanks to @Dialfrost}

f=lambda n,g=0,c=0:g<n**len(e:=range(n*n))!=(s:={g,sum(i//n*n**i for i in e),sum(i%n*n**i for i in e)})and f(n,g+1,c+([s:=s|{sum(g//n**(l//n**i%n*n+r//n**i%n)%n*n**i for i in e)}for _ in"a"*n**n**2for l in s for r in s]!=len(s)==n**n**2))or c

Try it online!

Uses a simple integer encoding of the gates, and composes them to depth n**(n*n) which should be sufficient. It's able to calculate up to n=2.

Full disclosure, this python golf is just to qualify this answer as code golf. The rest of this answer will explain how to calculate n=4

Explanation of the algorithm used to calculate n=4

The following algorithm works for all n>=2. In this explanation I refer to gates (also) as functions. f(a,b) denotes the value of gate f with inputs a and b. Gates can be composed just like functions. To keep every function binary, I often use the special functions l(a,b)=a and r(a,b)=b (which just pass the left/right argument).

Core algorithm

Unary completeness

A gate f is said to be unary complete if it's possible to create every unary function using f. Obviously, f has to be unary complete to be functionally complete.

We first check if f is unary complete. If not, then it's not functionally complete. Then we move to the next section.

Functional completeness

Assuming that f is unary complete, we can check if f is functionally complete with the two following tests.

Lonelyness-test

We want to find some symbols a, b, c, d where a≠b and c≠d, so that f(a, c) is distinct from f(a, d), f(b, c) and f(b, d). This means that f is "lonely".

Using these values, and unary functions, we can simulate all of boolean logic.

If there are no such a, b, c, d I claim that f can't be functionally complete.

To see why, let's look at how non-lonely functions compose. Note that the functions l(x,y)=x and r(x,y)=y are not lonely. Assume L and R are non-lonely functions. g(a,b)=f(L(a, b), R(a,b)). In general, L, R and f have the one of the three following "truth" tables, for the relevant inputs:

. a b
c x x
d y y

. a b
c x y
d x y

. a b
c x y
d y x

It should be clear that composing these does not make the resulting function lonely. This is a finitary problem and can be easily proved with brute-force. It is the same reason xor and not are not functionally complete.

In other words, composing non-lonely functions makes non-lonely functions, and since some gates are lonely, a non-lonely gate cannot be universal.

Constructible-test

Again, we assume f is unary complete, and also lonely.

A function f is n+1-constructible if there are some subsets of the alphabet L and R where |L|=|R|=n, |f[L,R]|≥n+1. A function f is constructible iff it is n-constructible for all n≥3 up to the length of the alphabet.

If f is constructible, then it is definitely functionally complete. You can just convert your input to base-2, do whatever calculations you want, and then convert back to the full alphabet.

Now is it possible to not be constructible and still be functionally complete? No.

Let's assume that there is some n so that f is not n-constructible. Note that the functions l(x,y)=x and r(x,y)=y are never n-constructible. Assume L and R are non-n-constructible functions. Then g(a,b)=f(L(a,b),R(a,b)) is also non-n-constructible. Because the image of L and R has cardinality ≤n, so does g. Therefore g is also non-n-constructible

Therefore f has to be constructible to be functionally complete, because again, non-n-constructible gates compose to create non-n-constructible gates and some gates are n-constructible.

Optimizations

Data Format

A duadic function f is represented as a n*n list, so that f(a, b) = list[a*n+b]. This is a bit slow, so for n=4 I use a 32-bit integer. Every function has a unique index. The indices start from 0 and have no gaps. Every monadic function f(a,b)=g(b) has a unique index. It also starts from 0 and has no gaps.

Transposition

A transposition fᵀ is defined as fᵀ(a,b)=f(b,a)

Permutation

p is a permutation of the alphabet. p(x) applies the permutation. p⁻¹(x) applies the inverse. p(p⁻¹(x))=p⁻¹(p(x))=x.

fₚ is defined as fₚ(a,b)=p⁻¹(f(p(a),p(b)))

Theorem 1

Claim: f is functionally complete, iff fᵀ also is.

Proof: You can just swap the arguments lol

Theorem 2

Claim: f is functionally complete, iff fₚ also is (for all permutations p)

Proof: When you do function composition with fₚ, the outer and inner permutations cancel out. So the "meat" of the function doesn't change, just that the alphabet is relabled.

Minimal representation

f is said to be minimal if f≤fₚ and f≤fₚᵀ for all permutations p (here ≤ refers to some total order). By theorem 1 and 2, we only need to consider minimal elements.

Rust code for n=4

main.rs

#![feature(let_else)]
#![feature(map_first_last)]
#![feature(adt_const_params)]
#![feature(generic_const_exprs)]
#![feature(label_break_value)]
use indicatif::{ProgressBar, ProgressStyle};
use itertools::Itertools;
use rand::Rng;
use rayon::prelude::*;
use std::sync::atomic::AtomicBool;
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering::*;
use std::thread;

#[cfg(not(debug_assertions))]
macro_rules! get_unsafe {
    [$a:expr, $i:expr] => {
        *unsafe {$a.get_unchecked($i)}
    };
}

#[cfg(debug_assertions)]
macro_rules! get_unsafe {
    [$a:expr, $i:expr] => {
        *$a.get($i).unwrap()
    };
}

#[cfg(not(debug_assertions))]
macro_rules! get_mut_unsafe {
    [$a:expr, $i:expr] => {
        *unsafe {$a.get_unchecked_mut($i)}
    };
}

#[cfg(debug_assertions)]
macro_rules! get_mut_unsafe {
    [$a:expr, $i:expr] => {
        *$a.get_mut($i).unwrap()
    };
}

trait Function: std::hash::Hash + Clone + std::cmp::Eq + std::fmt::Debug + std::cmp::Ord {
    const N: usize;

    fn impl_eval(&self, a: usize, b: usize) -> usize;

    #[cfg(debug_assertions)]
    fn eval(&self, a: usize, b: usize) -> usize {
        assert!(
            a < Self::N && b < Self::N,
            "Called eval with a={}, b={} but N={}",
            a,
            b,
            Self::N
        );
        self.impl_eval(a, b)
    }

    #[cfg(not(debug_assertions))]
    fn eval(&self, a: usize, b: usize) -> usize {
        use std::hint::unreachable_unchecked;
        if a >= Self::N || b >= Self::N {
            // I am speed
            unsafe {
                unreachable_unchecked();
            }
        }
        self.impl_eval(a, b)
    }

    fn pass_left() -> Self;
    fn pass_right() -> Self;

    fn compose(&self, left: &Self, right: &Self) -> Self;

    fn unary_compose(&self, left: usize, right: usize) -> usize {
        self.compose(
            &Self::from_unary_index(left),
            &Self::from_unary_index(right),
        )
        .unary_index()
    }

    // Used by fuzzers
    fn random<R: Rng>(rng: &mut R) -> Self;

    // Returns true if should be discarded
    fn low_effort_discard(&self) -> bool {
        for n in 0..Self::N {
            if self.eval(n, n) == n {
                return true;
            }
        }
        false
    }

    // Unique, no holes, for r-unary ops
    fn unary_index(&self) -> usize {
        let mut ret = 0;
        for a in (0..Self::N).rev() {
            ret *= Self::N;
            ret += self.eval(a, a);
        }
        ret
    }

    fn from_unary_index(i: usize) -> Self;

    fn is_unary_complete(&self) -> bool
    where
        [(); Self::N.pow(Self::N as u32)]:,
    {
        // Bruteforce-checks if self is a unary-complete function
        // Keeps track of all the visited nodes and has a queue of functions to add
        // A function is popped from the queue and composed with every previous function, plus itself
        // The new compositions are added to the queue

        // visited is a "Linked list" containing the already visited unary functions
        // 0 - not visited
        // n - visited, next visited in n steps (n is possibly negative)
        // Hack - this list can store BOTH the queue AND the already visited nodes
        let mut visited = [0isize; Self::N.pow(Self::N as u32)];
        let vl = visited.len() as isize;
        let mut start = vl;
        let mut queue;

        let pri = Self::pass_right().unary_index();
        get_mut_unsafe![visited, pri] = vl - pri as isize;
        queue = pri as isize;

        while queue != vl {
            let ui = queue as usize;
            // Pop from queue
            queue += get_unsafe![visited, ui];
            // Redundant, visited[ui] will get overwritten anyway
            // visited[ui] = 0;

            // Start iterating
            let mut ptr = start;
            while ptr != vl {
                let add = [
                    self.unary_compose(ptr as usize, ui as usize),
                    self.unary_compose(ui as usize, ptr as usize),
                ];
                // Push to queue
                for x in add {
                    if get_unsafe![visited, x] == 0 {
                        get_mut_unsafe![visited, x] = queue - x as isize;
                        queue = x as isize;
                    }
                }
                // Next visited function
                ptr += get_unsafe![visited, ptr as usize];
            }
            // Self-composition
            let x = self.unary_compose(ui as usize, ui as usize);
            // Push
            if get_unsafe![visited, x] == 0 {
                get_mut_unsafe![visited, x] = queue - x as isize;
                queue = x as isize;
            }

            // Add self
            get_mut_unsafe![visited, ui] = start - ui as isize;
            start = ui as isize;
        }
        visited.iter().all(|&x| x != 0)
    }

    fn is_functionally_complete(&self) -> bool
    where
        [(); Self::N.pow(Self::N as u32)]:,
    {
        let n = Self::N;
        let unary = self.is_unary_complete();
        if !unary {
            return false;
        }
        // Loneliness
        let mut pass = false;
        'a: for a in 0..n {
            for b in 0..a {
                for c in 0..n {
                    for d in 0..c {
                        let ac = self.eval(a, c);
                        let bc = self.eval(b, c);
                        let ad = self.eval(a, d);
                        let bd = self.eval(b, d);
                        let mut arr = [ac, bc, ad, bd];
                        arr.sort_unstable();
                        if arr[0] != arr[1] || arr[2] != arr[3] {
                            pass = true;
                            break 'a;
                        }
                    }
                }
            }
        }

        if !pass {
            return false;
        }

        // k+1 - completeness
        self.is_k_complete()
    }

    fn is_k_complete(&self) -> bool {
        let n = Self::N;
        let mut counter = vec![0; n];
        let mut k = 2;
        'b: while k < n {
            let cmb: Vec<_> = (0..n).combinations(k).collect();
            for l in &cmb {
                for r in &cmb {
                    for &a in l {
                        for &b in r {
                            counter[self.eval(a, b)] = 1;
                        }
                    }
                    let s = counter.iter().sum();
                    counter.fill(0);
                    if s > k {
                        k = s;
                        continue 'b;
                    }
                }
            }
            return false;
        }
        true
    }

    fn from_index(i: usize) -> Self;
    fn to_index(&self) -> usize;

    // If this function is minimal in it's equivalence class, returns the number of functions in the equivalence class
    // Else returns zero
    fn cifminelse0(&self) -> usize;

    // Pretty prints this gate
    fn pretty_print(&self) {
        println!("Gate i={}", self.to_index());
        let pad = " ";
        let space = " ";
        print!("{}?", pad);
        for b in 0..Self::N {
            print!("{}{}",space,b);
        }
        println!();
        for a in 0..Self::N {
            print!("{}{}", pad, a);
            for b in 0..Self::N {
                print!("{}{}",space,self.eval(a,b));
            }
            println!();
        }
    }
}

// Four bit functions
impl Function for u32 {
    const N: usize = 4;
    fn impl_eval(&self, a: usize, b: usize) -> usize {
        *self as usize >> (a * 4 + b) * 2 & 3
    }

    fn pass_left() -> u32 {
        0xFFAA5500
    }

    fn pass_right() -> u32 {
        0xE4E4E4E4
    }

    fn compose(&self, l: &Self, r: &Self) -> Self {
        let mut ret = 0;
        for a in (0..4).rev() {
            for b in (0..4).rev() {
                ret <<= 2;
                ret |= self.eval(l.eval(a, b), r.eval(a, b));
            }
        }
        ret as u32
    }

    fn random<R: Rng>(rng: &mut R) -> Self {
        rng.gen()
    }

    fn to_index(&self) -> usize {
        *self as usize
    }

    fn from_index(i: usize) -> Self {
        i as u32
    }

    fn unary_index(&self) -> usize {
        *self as usize & 255
    }

    fn from_unary_index(i: usize) -> Self {
        let r = i | (i << 8);
        let r = r | (r << 16);
        r as u32
    }

    fn cifminelse0(&self) -> usize {
        const PERM4: [[usize; 4]; 24] = [
            [0, 1, 2, 3],
            [0, 1, 3, 2],
            [0, 2, 1, 3],
            [0, 2, 3, 1],
            [0, 3, 1, 2],
            [0, 3, 2, 1],
            [1, 0, 2, 3],
            [1, 0, 3, 2],
            [1, 2, 0, 3],
            [1, 2, 3, 0],
            [1, 3, 0, 2],
            [1, 3, 2, 0],
            [2, 0, 1, 3],
            [2, 0, 3, 1],
            [2, 1, 0, 3],
            [2, 1, 3, 0],
            [2, 3, 0, 1],
            [2, 3, 1, 0],
            [3, 0, 1, 2],
            [3, 0, 2, 1],
            [3, 1, 0, 2],
            [3, 1, 2, 0],
            [3, 2, 0, 1],
            [3, 2, 1, 0],
        ];

        fn flipped(f: u32) -> u32 {
            f & 0xc0_30_0c_03
                | f << 6 & 0x30_0c_03_00
                | f << 12 & 0x0c_03_00_00
                | f << 18 & 0x03_00_00_00
                | f >> 6 & 0x00_c0_30_0c
                | f >> 12 & 0x00_00_c0_30
                | f >> 18 & 0x00_00_00_c0
        }

        fn permuted(f: u32, p: &[usize; 4]) -> u32 {
            let mut invp = [0, 0, 0, 0];
            for i in 0..4 {
                invp[p[i]] = i as u32;
            }
            let mut r = 0;
            for a in (0..4).rev() {
                for b in (0..4).rev() {
                    r <<= 2;
                    r |= invp[f.eval(p[a], p[b])];
                }
            }
            r
        }

        let mut m = vec![*self; 48];
        m[1] = flipped(*self);
        if m[1] < *self {
            return 0;
        }
        for (i, p) in PERM4.iter().enumerate().skip(1) {
            m[i * 2] = permuted(*self, p);
            m[i * 2 + 1] = flipped(m[i * 2]);
            if m[i * 2] < *self || m[i * 2 + 1] < *self {
                return 0;
            }
        }
        m.sort_unstable();
        m.dedup();
        m.len()
    }
}

impl<const N: usize> Function for [[usize; N]; N] {
    const N: usize = N;
    fn impl_eval(&self, a: usize, b: usize) -> usize {
        self[a][b]
    }

    fn pass_left() -> Self {
        let mut r = [[0; N]; N];
        for a in 0..N {
            r[a] = [a; N];
        }
        r
    }

    fn pass_right() -> Self {
        let mut d = [0; N];
        for b in 0..N {
            d[b] = b;
        }
        [d; N]
    }

    fn compose(&self, l: &Self, r: &Self) -> Self {
        let mut ret = [[0; N]; N];
        for a in 0..N {
            for b in 0..N {
                ret[a][b] = self.eval(l.eval(a, b), r.eval(a, b));
            }
        }
        ret
    }

    fn random<R: Rng>(rng: &mut R) -> Self {
        let mut r = [[0; N]; N];
        for a in 0..N {
            for b in 0..N {
                r[a][b] = rng.gen_range(0..N);
            }
        }
        r
    }

    fn from_index(mut i: usize) -> Self {
        let mut r = [[0; N]; N];
        for a in 0..N {
            for b in 0..N {
                r[a][b] = i % N;
                i /= N;
            }
        }
        r
    }

    fn to_index(&self) -> usize {
        let mut r = 0;
        for a in (0..N).rev() {
            for b in (0..N).rev() {
                r *= N;
                r += self[a][b];
            }
        }
        r
    }

    fn from_unary_index(mut i: usize) -> Self {
        let mut x = [0; N];
        for n in 0..N {
            x[n] = i % N;
            i /= N;
        }
        [x; N]
    }

    fn cifminelse0(&self) -> usize {
        let flip = |i: &Self| i.compose(&Self::pass_right(), &Self::pass_left());
        let permute_self = |p: &[usize]| {
            let mut inv = [0; N];
            for i in 0..N {
                inv[p[i]] = i;
            }
            let mut ret = [[0; N]; N];
            for a in 0..N {
                for b in 0..N {
                    ret[a][b] = inv[self.eval(p[a], p[b])];
                }
            }
            ret
        };

        let mut m = vec![*self; (1..=N).product::<usize>() * 2];
        m[1] = flip(self);
        if m[1] < *self {
            return 0;
        }
        for (i, p) in (0..N).permutations(N).enumerate().skip(1) {
            m[i * 2] = permute_self(&p);
            m[i * 2 + 1] = flip(&m[i * 2]);
            if m[i * 2] < *self || m[i * 2 + 1] < *self {
                return 0;
            }
        }
        m.sort_unstable();
        m.dedup();
        m.len()
    }
}

#[test]
fn test_pass() {
    fn test_pass_g<F: Function + std::fmt::Debug>() {
        let l = F::pass_left();
        let r = F::pass_right();
        for a in 0..F::N {
            for b in 0..F::N {
                assert_eq!(l.eval(a, b), a, "a is {}, b is {}, l is {:?}", a, b, l);
                assert_eq!(r.eval(a, b), b, "a is {}, b is {}, r is {:?}", a, b, r);
            }
        }
    }
    test_pass_g::<u32>();
    test_pass_g::<[[usize; 3]; 3]>();
    test_pass_g::<[[usize; 4]; 4]>();
}

#[test]
fn test_compose() {
    use rand::rngs::SmallRng;
    use rand::SeedableRng;
    fn test_compose_g<F: Function + std::fmt::Debug>() {
        let mut rng = SmallRng::seed_from_u64(42);
        let repeats = 1_000_000;
        for _ in 0..repeats {
            let f = F::random(&mut rng);
            let l = F::random(&mut rng);
            let r = F::random(&mut rng);
            let c = f.compose(&l, &r);
            let a = rng.gen_range(0..F::N);
            let b = rng.gen_range(0..F::N);
            assert_eq!(
                c.eval(a, b),
                f.eval(l.eval(a, b), r.eval(a, b)),
                "a:{} b:{} f:{:?} l:{:?} r:{:?} c:{:?}",
                a,
                b,
                f,
                l,
                r,
                c
            );
        }
    }
    test_compose_g::<u32>();
    test_compose_g::<[[usize; 3]; 3]>();
    test_compose_g::<[[usize; 4]; 4]>();
}

#[test]
fn test_low_effort_discard() {
    use rand::rngs::SmallRng;
    use rand::SeedableRng;
    fn test_low_effort_discard_g<F: Function + std::fmt::Debug>()
    where
        [(); F::N.pow(F::N as u32)]:,
    {
        let mut rng = SmallRng::seed_from_u64(42);
        let repeats = 1_000;
        for _ in 0..repeats {
            let f = F::random(&mut rng);
            assert!(
                !f.low_effort_discard() || !f.is_functionally_complete(),
                "Discarded f:{:?}",
                f
            );
        }
    }
    test_low_effort_discard_g::<u32>();
    test_low_effort_discard_g::<[[usize; 3]; 3]>();
    test_low_effort_discard_g::<[[usize; 4]; 4]>();
}

#[test]
fn test_specifics() {
    // Using the examples from the blog post + = 0, 0 = 1, 1 = 2
    let triplets = [
        ([[0; 3]; 3], false),
        ([[1; 3]; 3], false),
        ([[2; 3]; 3], false),
        ([[0, 1, 2]; 3], false),
        ([[0; 3], [1; 3], [2; 3]], false),
        ([[0, 1, 2], [1, 1, 2], [2, 2, 2]], false), // Min
        ([[0, 1, 2], [0, 1, 1], [0, 0, 0]], false), // Imp
        ([[0; 3], [1; 3], [0; 3]], false),          // Imp composition
        ([[2, 0, 0], [0, 0, 0], [0, 0, 1]], true),  // Tand
        ([[2, 1, 1], [1, 0, 1], [1, 1, 1]], true),  // Modified Tand
        ([[2, 2, 2], [2, 0, 2], [2, 2, 1]], true),  // Modified Tand
        ([[1, 0, 0], [0, 2, 0], [0, 0, 0]], true),  // Modified Tand
        ([[1, 1, 1], [1, 2, 1], [1, 1, 0]], true),  // Modified Tand
        ([[1, 2, 2], [2, 2, 2], [2, 2, 0]], true),  // Modified Tand
        ([[2, 0, 1], [0, 0, 0], [1, 0, 1]], true),  // Pointy Tand
        // Experimentally found
        ([[0, 2, 0], [0, 0, 0], [0, 0, 0]], false),
        ([[1, 2, 0], [0, 0, 0], [0, 0, 0]], true),
        // From the post
        ([[2, 0, 1], [0, 0, 0], [2, 2, 0]], true),
        ([[2, 0, 1], [1, 0, 0], [2, 2, 0]], true),
        ([[2, 0, 1], [2, 0, 0], [2, 2, 0]], true),
        ([[1, 0, 0], [1, 0, 2], [2, 2, 1]], false),
    ];
    for (f, r) in triplets {
        println!("{:?} -> {}", f, r);
        assert_eq!(f.is_functionally_complete(), r);
    }
}

fn smart_method<F: Function>()
where
    [(); F::N.pow(F::N as u32)]:,
{
    let amount = F::N.pow(F::N as u32 * F::N as u32);
    (0..amount).into_par_iter().for_each(|i| {
        let n = F::from_index(i);
        let m = n.cifminelse0();
        if m == 0 {
            return;
        }
        let r = n.low_effort_discard() || !n.is_functionally_complete();
        if !r {
            TC.fetch_add(m, Relaxed);
        } else {
            FC.fetch_add(m, Relaxed);
        }
    });
    CONT.store(false, Release);
}

static TC: AtomicUsize = AtomicUsize::new(0);
static FC: AtomicUsize = AtomicUsize::new(0);
static CONT: AtomicBool = AtomicBool::new(true);

// Change this to [[usize;3];3] for n=3
type T = u32;

fn main() {
    // Fluff
    let start = std::time::Instant::now();
    let amount = T::N.pow(T::N as u32 * T::N as u32);
    let pb = ProgressBar::new(amount as u64);
    pb.set_style(
        ProgressStyle::default_bar().template(
            "{wide_bar:.green/red}\n{pos}/{len} - {percent}% - {per_sec} - {eta} - {msg}",
        ),
    );
    let t = thread::spawn(move || {
        while CONT.load(Acquire) {
            thread::sleep(std::time::Duration::from_millis(100));
            let t = TC.load(Relaxed);
            let f = FC.load(Relaxed);
            pb.set_position(t as u64 + f as u64);
            pb.set_message(format!(
                "Ratio at {}/{} = {:.5}",
                t,
                t + f,
                t as f64 / (t as f64 + f as f64)
            ));
            pb.tick();
        }
    });
    // Call
    smart_method::<T>();
    // Fluff
    match t.join() {
        Err(_e) => {
            println!("Failed to join ui-thread :/");
        }
        _ => {}
    };
    let t = TC.load(Relaxed);
    let f = FC.load(Relaxed);
    println!(
        "Ended with {} universal gates and {} non-universal gates. Ratio is {}/{} = {:.5}",
        t,
        f,
        t,
        t + f,
        t as f64 / (t as f64 + f as f64)
    );
    println!("Took {:?}", start.elapsed());
    // Remember to reset TC, FC and CONT if you want to call again
}

cargo.toml

[dependencies]
itertools = "0.10"
rand = {version="0.8", features=["small_rng"]}
rayon = "1.5"
indicatif = {version = "0.16", features = ["rayon"]}

Takes around 20 minutes on my machine™. The actual code is not that interesting, maybe with the exception of the unary completeness check, which uses a buffer with two non-overlapping linked lists, to form a very efficient deduplicated queue + set data structure.

n=5?

For n=5 you basically need a new idea (or a lot of computing power). Checking each gate individually becomes impractical (if you could do it in one cycle, it would still take two years). If someone manages to calculate n=5, I'm happy to forward Bubblers +500 bounty to them.

Answer 2

JavaScript (Node.js), 194 bytes

f=(n,c=[],k=0)=>k-n?1/c[n*n]?(F=>g=s=>s[n**n*8]?eval(`try{for(A=n;A--;)for(B=n;B--;)eval(s)+~(A<B?A:B)%n&&G;1}catch{}`):[...'AB()F'].some(_=>g(s+_)))(t=>u=>c[t*n+u])``:f(n,c,k+1)+f(n,[...c,k]):0

Try it online!

If a function can express f(x,y)=max(x,y)+1, then it's universal:

• f(x,x)=x+1, therefore we can get x+c for any c
• max(x,x+1,...,x+n-2) is n-1, unless x is zero where the result is n-2
• max(x,max(a,a+1,...,a+n-2,b,b+1,...,b+n-2)+1) is x if either a or b is not 0, and n+1 if a and b are both 0
• Set the value using this

The eval never meet a function that can't fit the exact length:

• The expression built with AB()F is always of odd length (F(A)(B))
• One can write A as ((((A)))) to use even spaces