Compute OEIS A005434
Rust, n ≈ 660



use std::collections::HashMap;
use std::iter::once;
use std::rc::Rc;

type Memo = HashMap&lt;(u32, u32, Rc&lt;Vec&lt;u32&gt;&gt;), u64&gt;;

fn f(memo: &amp;mut Memo, mut n: u32, p: u32, mut s: Rc&lt;Vec&lt;u32&gt;&gt;) -&gt; u64 {
    debug_assert!(p != 0);
    let d = n / p;
    debug_assert!(d &gt;= 1);
    let r = n - p * if d &gt;= 2 { d - 1 } else { 1 };

    let k = s.binary_search(&amp;(n - r + 1)).unwrap_or_else(|i| i);
    for &amp;i in &amp;s[..k] {
        if i % p != 0 {
            return 0;
        }
    }

    if d &gt;= 3 {
        let o = n - (p + r);
        n = p + r;
        s = Rc::new(s[k..].iter().map(|i| i - o).collect());
    } else if n == p {
        return 1;
    } else if k != 0 {
        s = Rc::new(s[k..].to_vec());
    }

    let query = (n, p, s);
    if let Some(&amp;c) = memo.get(&amp;query) {
        return c;
    }
    let (n, p, s) = query;

    let t = Rc::new(s.iter().map(|i| i - p).collect::&lt;Vec&lt;_&gt;&gt;());
    let c = if d &lt; 2 {
        (1..r + 1).map(|q| f(memo, r, q, t.clone())).sum()
    } else if r == p {
        (1..p + 1)
            .filter(|&amp;q| p % q != 0 || q == p)
            .map(|q| f(memo, r, q, t.clone()))
            .sum()
    } else {
        let t = match t.binary_search(&amp;p) {
            Ok(_) =&gt; t,
            Err(k) =&gt; {
                Rc::new(t[..k]
                            .iter()
                            .cloned()
                            .chain(once(p))
                            .chain(t[k..].iter().cloned())
                            .collect::&lt;Vec&lt;_&gt;&gt;())
            }
        };
        (1..t.first().unwrap() + 1)
            .filter(|&amp;q| p % q != 0 || q == p)
            .map(|q| f(memo, r, q, t.clone()))
            .sum()
    };
    memo.insert((n, p, s), c);
    c
}

fn main() {
    let mut memo = HashMap::new();
    let s = Rc::new(Vec::new());
    for n in 1.. {
        println!("{} {}",
                 n,
                 (1..n + 1)
                     .map(|p| f(&amp;mut memo, n, p, s.clone()))
                     .sum::&lt;u64&gt;());
    }
}


Try it online!

How it works

This is a memoized implementation of the recursive predicate Ξ given in Leo Guibas, “Periods in strings” (1981).  The function f(memo, n, p, s) finds the number of correlations of length n with smallest period p and also each of the periods in the set s.