Finding approximate correlations
Rust, n ≈ 30 or 31 or 32

On my laptop (two cores, i5-6200U), this gets through n = 1, …, 31 in 53 seconds, using about 2.5 GiB of memory, or through n = 1, …, 32 in 105 seconds, using about 5 GiB of memory.  Compile with cargo build --release and run target/release/correlations.

src/main.rs

extern crate rayon;

type S = u32;
const S_BITS: u32 = 32;

fn cat(mut a: Vec&lt;S&gt;, mut b: Vec&lt;S&gt;) -&gt; Vec&lt;S&gt; {
    if a.capacity() &gt;= b.capacity() {
        a.append(&amp;mut b);
        a
    } else {
        b.append(&amp;mut a);
        b
    }
}

fn search(n: u32, i: u32, ss: Vec&lt;S&gt;) -&gt; u32 {
    if ss.is_empty() {
        0
    } else if 2 * i + 1 &gt; n {
        search_end(n, i, ss)
    } else if 2 * i + 1 == n {
        search2(n, i, ss.into_iter().flat_map(|s| vec![s, s | 1 &lt;&lt; i]))
    } else {
        search2(n,
                i,
                ss.into_iter()
                    .flat_map(|s| {
                                  vec![s,
                                       s | 1 &lt;&lt; i,
                                       s | 1 &lt;&lt; n - i - 1,
                                       s | 1 &lt;&lt; i | 1 &lt;&lt; n - i - 1]
                              }))
    }
}

fn search2&lt;SS: Iterator&lt;Item = S&gt;&gt;(n: u32, i: u32, ss: SS) -&gt; u32 {
    let (shift, mask) = (n - i - 1, !(!(0 as S) &lt;&lt; i + 1));
    let close = |s: S| {
        let x = (s ^ s &gt;&gt; shift) &amp; mask;
        x &amp; x.wrapping_sub(1) == 0
    };
    let (ssy, ssn) = ss.partition(|&amp;s| close(s));
    let (cy, cn) = rayon::join(|| search(n, i + 1, ssy), || search(n, i + 1, ssn));
    cy + cn
}

fn search_end(n: u32, i: u32, ss: Vec&lt;S&gt;) -&gt; u32 {
    if i &gt;= n - 1 { 1 } else { search_end2(n, i, ss) }
}

fn search_end2(n: u32, i: u32, mut ss: Vec&lt;S&gt;) -&gt; u32 {
    let (shift, mask) = (n - i - 1, !(!(0 as S) &lt;&lt; i + 1));
    let close = |s: S| {
        let x = (s ^ s &gt;&gt; shift) &amp; mask;
        x &amp; x.wrapping_sub(1) == 0
    };
    match ss.iter().position(|&amp;s| close(s)) {
        Some(0) =&gt; {
            match ss.iter().position(|&amp;s| !close(s)) {
                Some(p) =&gt; {
                    let (ssy, ssn) = ss.drain(p..).partition(|&amp;s| close(s));
                    let (cy, cn) = rayon::join(|| search_end(n, i + 1, cat(ss, ssy)),
                                               || search_end(n, i + 1, ssn));
                    cy + cn
                }
                None =&gt; search_end(n, i + 1, ss),
            }
        }
        Some(p) =&gt; {
            let (ssy, ssn) = ss.drain(p..).partition(|&amp;s| close(s));
            let (cy, cn) = rayon::join(|| search_end(n, i + 1, ssy),
                                       || search_end(n, i + 1, cat(ss, ssn)));
            cy + cn
        }
        None =&gt; search_end(n, i + 1, ss),
    }
}

fn main() {
    for n in 1..S_BITS + 1 {
        println!("{}: {}", n, search(n, 1, vec![0, 1]));
    }
}


Cargo.toml

[package]
name = "correlations"
version = "0.1.0"
authors = ["Anders Kaseorg &lt;andersk@mit.edu&gt;"]

[dependencies]
rayon = "0.7.0"


Try it online!

I also have a slightly slower variant using very much less memory.