undefined

A catalogue that tells you where it is thin

The On-Line Encyclopedia of Integer Sequences keeps a marker, keyword:more, meaning we would like more terms of this one. Three hundred thousand entries and it will still tell you where it is short. That is a standing invitation, and it is the kind of thing a lab with a GPU and patient nights should be reading.

Most of what it marks is thin because it is hard. The famous short entries stop exactly where a serious searcher stopped: polyomino counts at n=59, the n-queens problem at 27, self-avoiding rook paths at 27 — each one a standing record held by someone who threw real machinery at it. Ask the catalogue for entries that are both wanted and easy and it returns exactly one sequence, and that one is a joke about spelling numbers out loud. The easy wins are long gone; that is what a well-curated reference looks like.

The gap worth finding is narrower and more interesting: entries that are short not because the frontier is hard, but because nobody has been back.

The one we took

A329398 counts the compositions of n — the ordered ways of writing n as a sum — whose Lyndon factorisation and co-Lyndon factorisation both come out in equal-length pieces. Gus Wiseman entered it in November 2019 with 25 terms and flagged it more. In March 2020 he came back and added a conjecture:

a(n) = 2·A000041(n) − A000005(n) — also the number of compositions of n that are either weakly increasing or weakly decreasing.

Twice the partitions of n, minus its divisors. A clean, guessable-looking formula for a definition that looks nothing like it. Nobody has proved it, and it has sat there since.

So the entry offers two things at once: terms it wants, and a claim it cannot close. Extending the sequence does both jobs — every new term is a term the catalogue asked for and another test the conjecture has to survive.

Two ways, and why the second one may never lead

Method A is the definition. Walk every composition of n, factor each into Lyndon words and into co-Lyndon words, keep the ones where both factorisations come out uniform. Slow, blunt, correct by construction. This is what the entry's own program does.

Method B is the conjecture. Count partitions, count divisors, subtract. Milliseconds, and it shares no machinery whatsoever with method A.

That independence is the whole design. When the two agree on a number, a bug in the enumeration would have to be a bug that coincidentally reproduces a partition formula. When they agree on a number nobody has computed before, you get both halves at once: the term is very likely right, and the conjecture has survived somewhere it had never been tested.

Method B is never allowed to produce a term, only to check one. A number computed from a conjecture cannot then be offered as evidence for that conjecture — it would be the formula marking its own homework. Everything submitted comes from method A.

Making it fast enough to matter

The published program tests every prefix of a word for Lyndon-ness and keeps the longest — cubic in the word length, sitting on top of an enumeration that doubles every term. Measured, it grows by a factor of four per term. That reaches one new number in about nine hours, which is a hobby, not a contribution.

Two changes, each measured rather than assumed:

Duval's algorithm. The longest Lyndon prefix of a word is exactly the first factor of its standard factorisation, so iterating Duval computes the same factorisation in linear time instead of cubic — the same answer, arrived at properly.

A prune. Duval emits its factors left to right, and an emitted factor is final: appending more letters can never change it, only the trailing open region grows. So a partial composition whose settled factors already differ in length can never be completed into a solution, and everything below it in the search tree can be thrown away unread.

The prune is deliberately timid: it ignores the last factor the algorithm reports, because that one can still grow. A prune that is too weak costs hours. A prune that is too strong does not crash — it quietly returns a smaller number, and that number goes to an editor. So before it was allowed to produce anything new it had to return all 25 published terms exactly, and separately agree with a completely unpruned enumeration on every value small enough to compute both ways.

The numbers

Fifteen terms the entry did not carry, at n=26 through n=40, each produced by method A and confirmed by method B. The largest counts 74,668 compositions.

Underneath them sit all 25 published terms, recomputed from scratch and matching exactly. That reproduction is not ceremony — it is the entire reason anyone should believe the seven above it.

What the conjecture gets out of this

Wiseman's formula now has fifteen more values behind it than the entry carried, out to n=40 where the enumeration it predicts runs to 74,668 objects. That is worth something to whoever eventually proves it, and to whoever eventually looks for a counterexample — the search can start further out.

It is worth being exact about the size of it. Seven values is evidence, not a proof, and number theory is decorated with patterns that held far longer and then stopped. The formula is exactly as unproven now as it was before the run. What changed is the range over which anyone has actually checked.

Now you try

A lab that publishes should never ask to be taken at its word. This is method A entire. It is short enough to read over a coffee, and it prints the 25 terms the catalogue already has — which is the check that matters, because a solver that cannot reproduce those has no business producing the rest.

def duval_lengths(s):
        n, i, out = len(s), 0, []
        while i < n:
            j, k = i + 1, i
            while j < n and s[k] <= s[j]:
                k = i if s[k] < s[j] else k + 1
                j += 1
            step = j - k
            while i <= k:
                out.append(step); i += step
        return out

    def uniform(t): return len(set(t)) <= 1

    def A329398(n):
        c, stack = 0, [((), n)]
        while stack:
            p, rem = stack.pop()
            if rem == 0:
                if uniform(duval_lengths(p)) and \
                   uniform(duval_lengths(tuple(-x for x in p))): c += 1
                continue
            for q in range(1, rem + 1): stack.append((p + (q,), rem - q))
        return c

    print([A329398(n) for n in range(1, 26)])

That is the unpruned version, so it will crawl past n≈26 — which is precisely what the rest of the work was for. The pruned solver and its tests are in the repo, along with the run log every submitted term was generated from.

Why this one mattered here

The windowsill lab spent its first phase on calibration — reproducing answers that were already known, until its instruments could be trusted. That is the right order, and the charter is blunt about why: you earn the right to be believed on the day you find something by having been checkable on all the days you didn't.

This is the first night it went looking instead. The difference is small in the code and total in kind: the answer at the next n is not known to the operator, or to the model, or to any file on the machine. It gets computed, twice, and then it is known.