Enumeration of autocorrelations, along with their populations.

enum.cpp

// Mivik 2021.1.24
// Inspired by the predicate given in "Periods in Strings" by Guibas and Odlyzko
// See Leo J. Guibas and Andrew M. Odlyzko. Periods in strings. J. of Combinatorial Theory series A, 30:19–42, 1981.

// Enumerated all autocorrelations for n = 400 in less than 30 seconds on my computer (without writing it to file)
// It DOES REQUIRE A LOT OF TIME AND DISK SPACE to save these autocorrelations, please notice
// For example, for n = 200, it could produce a file up to 200MB
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>

const int $n = 60;
const int C = 2;

int n;
struct bit_vector {
	int v[2];
	inline bool test(int i) const { return v[i >> 5] & (1 << (i & 31)); }
	inline void set(int i) { v[i >> 5] |= 1 << (i & 31); }
	inline void reset(int i) { v[i >> 5] &= ~(1 << (i & 31)); }
	inline void reset() { v[0] = v[1] = 0; }
	inline bool contains(const bit_vector &t) const { return (v[0] & t.v[0]) == t.v[0] && (v[1] & t.v[1]) == t.v[1]; }
};
struct info {
	bit_vector vec;
	int nfc;
	uint64_t pop;
	info(bit_vector vec, int nfc, uint64_t pop):
		vec(std::move(vec)), nfc(nfc), pop(pop) {}
};
bit_vector vec;
std::vector<info*> rec;
int req[$n];
inline uint64_t qpow(uint64_t x, int p) {
	uint64_t ret = 1;
	for (; p; p >>= 1, x *= x) if (p & 1) ret *= x;
	return ret;
}
inline int gcd(int x, int y) { while (x %= y) std::swap(x, y); return y; }
void dfs(int o, int lst, int cnt) {
	const int n = ::n - o;
	if (!n) {
		uint64_t pop = qpow(C, cnt);
		for (size_t i = rec.size() - 1; ~i; --i) {
			const auto &info = rec[i];
			if (info->vec.contains(vec)) pop -= info->pop;
		}
		rec.push_back(new info(vec, cnt, pop));
		if (!(rec.size() % 10000))
			std::cerr << rec.size() << " computed\n";
		return;
	}
	int *req = ::req + o; // ATTENTION!!! name shadowing for convenience
	vec.set(o);
	for (int p = 1; p < n; ++p) { // enumerate the minimum non-zero period
		if (p >= lst || p > (n - lst) + gcd(lst, p)) {
			if (p * 2 <= n) { // a small period
				const int r = p * (n / p - 1);
				bool ok = true;
				for (int i = 1; i < r; ++i) // check whether it satisfies previous requirements
					if (req[i] && i % p) { ok = false; break; }
				if (ok) {
					for (int i = 1; i < r; ++i) vec.reset(o + i);
					for (int i = p; i < r; i += p) vec.set(o + i);
					if (r + p != n) ++req[r + p]; // requirements might overlap so we use int instead of bool
					dfs(o + r, p, cnt);
					if (r + p != n) --req[r + p];
				}
			} else {
				vec.set(o + p);
				dfs(o + p, 0, cnt + (p << 1) - n);
			}
		}
		if (req[p]) return;
		vec.reset(o + p);
	}
	// no period exists
	dfs(o + n, 0, cnt + n);
}
int main() {
	freopen("autocorrelations.txt", "w", stdout);
	for (n = 1; n <= $n; ++n) {
		dfs(0, 0, 0);
		std::cerr << "Computation completed, writing to file..." << std::endl;
		// std::cout << "Showing " << rec.size() << " autocorrelations for n = " << n << std::endl;

		std::reverse(rec.begin(), rec.end()); // so it's sorted lexicographically
		for (auto info : rec) {
			std::cout << '|';
			for (int i = 0; i < n; ++i) std::cout << " o"[info->vec.test(i)];
			std::cout << "| " << info->pop << '\n'; // use newline char instead of std::endl to avoid frequent flushing
			delete info;
		}
		vec.reset(); rec.clear();
	}
}