windowsill lab · OEIS

A329398

A counting conjecture that sat on an OEIS entry from 2019 until the lab proved it in September 2026. The proof is now part of the approved entry. Everything behind it, including what the lab had to take back about its own claim.

The entry on the OEIS → Run the proof check → The windowsill feed →

Depth 0 · no maths needed

Start from zero

This page climbs from plain words to the full working file. Already know the field? Skip to the entry or the package.

  1. Write a number as a sum, in order

    Take 3. You can write it as 3, or 2+1, or 1+2, or 1+1+1. Order counts, so 2+1 and 1+2 are different. Each of these is called a composition of 3. There are four. For any number n there are 2n−1 of them, so they double every time n goes up by one.

  2. Read each one as a word, and cut it up

    Treat 2+1+3 as the word 213. There is a classic rule, from the 1950s, that cuts any word into pieces in exactly one way, each piece a Lyndon word: a piece that comes strictly first, in dictionary order, among all the ways of rotating it. Flip “smallest” to “largest” and you get a second cut, the co-Lyndon one. Call a cut uniform when every piece has the same length.

  3. Count the ones that come out even both ways

    OEIS A329398 counts the compositions of n whose Lyndon cut and co-Lyndon cut are both uniform. Starting at n = 1 the counts go 1, 2, 4, 7, 12, 18, 28, 40, 57… The OEIS is the On-Line Encyclopedia of Integer Sequences, the reference library mathematicians use to look up a list of numbers they have run into. A329398 is this list’s entry number.

  4. A guess sat on the entry for nearly seven years

    Gus Wiseman added the sequence in November 2019, and with it a conjecture: these are exactly the compositions that only ever step up, or only ever step down. If that is true, the count has a short formula. Compositions that only step up match the ways to split n into parts with order ignored (its partitions, p(n)), the same for stepping down, and the ones that do both are the constant ones, one for each divisor of n. So a(n) = 2·p(n) − d(n). For n = 6: 2·11 − 4 = 18. The terms agreed as far as anyone computed them. Nobody had shown it always holds.

    The 8 compositions of 4 drawn as bar charts. 7 of them only step up or only step down and are lit; one, 1+2+1, goes up and then down and is left dark. 41+32+23+11+1+21+2+12+1+11+1+1+1
    All 8 ways to write 4 as an ordered sum. 7 only go up or only go down, and a(4) = 7. Drawn from the definition, not by hand.

  5. Only up-or-down survives

    A Lyndon piece of two or more letters starts lower than it ends. A co-Lyndon piece starts higher than it ends. Both cuts begin at the same first letter. If both cuts used pieces longer than one letter, that first letter would have to be both below and at-or-above the same later letter, which cannot happen. So one of the two cuts is into single letters, and a cut into single letters only happens when the word never steps up (or, for the other cut, never steps down). The other direction is short too. That is the whole proof, and it fits in one comment on the entry.

  6. Checked by machine, then by people

    The windowsill lab took it on as part of its OEIS track, C03. A script checked every step of the proof against every composition of every n up to 16, all 65,535 of them. A separate program, written by an agent that was not allowed to read the lab’s code, counted up to n = 26 straight from the definition and matched. The proof, new terms, a 1,000-term table and a Python program went to the OEIS on 2026-09-18. Three editors worked the draft that evening, asked for more terms, and tidied it. The entry is now approved, with the proof in its comments and the conjecture’s formula in its formula field.

    The working, all public: the proof check, the independent count, the entry itself.

  7. Where the credit sits

    The sequence and the conjecture, set-equality and all, are Wiseman’s. What is new here is the proof. OEIS editors accepted it into the entry; no journal has refereed it, and it is not written in a proof assistant. It is short and elementary enough that someone who knows the Lyndon-word literature may recognise it as already known, and that would not be surprising.

Depth 1 · the entry, each field with a plain reading

The entry, in brief

Name
A329398compositions of n with uniform Lyndon and co-Lyndon factorizations
Formula
2·A000041(n) − A000005(n)twice the partitions of n, minus its divisors
Data
a(1)–a(46), last 21111246 terms on the entry; the b-file runs to n = 1000
Keyword
nonn, easywas “more” (needs terms); now “easy”: every term follows from the formula
Author
Gus Wiseman, Nov 13 2019who added the sequence and the conjecture
Extensions
a(26)–a(46), Sep 18 2026from Benjamin Schippers, after a(19)–a(25) from Robert Price in 2021

What it is. A proof that a composition has both a uniform Lyndon factorization and a uniform co-Lyndon factorization exactly when it is weakly increasing or weakly decreasing. Wiseman’s formula a(n) = 2·p(n) − d(n) follows by counting, so every term is now arithmetic.

What is solid. Each lemma and both directions were checked by exhaustive search over every composition with n ≤ 16. Three routes that share no code (enumeration from the definition, the closed form, and a direct count of the increasing ones) agree on every term computed both ways. An enumerator written without sight of the lab’s code reproduced the 25 published terms and a(26) = 4868.

What is not. The general argument is prose. The machine checks cover finitely many cases; the argument covers every n.

How it went in. The package below offered 40 terms, then 50 at an editor’s request, and said the editors might already have settled on their own line, which it could not confirm at the time. Read on 2026-10-13, the entry’s data ends at a(46) = 211112: the editors’ line, which agrees with the closed form. The 50-term line was never pasted, as §10a advised.

Words on this page, in plain language
OEIS, A-number
The On-Line Encyclopedia of Integer Sequences, founded by Neil Sloane in 1964 and now run by a foundation with volunteer editors. Every sequence has an A-number; A329398 is this one’s.
Composition
A way to write n as an ordered sum of positive whole numbers. 2+1 and 1+2 are different compositions of 3.
Partition, p(n), A000041
A way to write n as a sum when order does not matter. p(n) counts them; p(6) = 11. A000041 is that sequence’s entry.
d(n), A000005
The number of whole numbers that divide n evenly. d(6) = 4, from 1, 2, 3 and 6.
Lyndon word
A word strictly smaller, in dictionary order, than every one of its proper endings. 113 is one; 131 is not.
Lyndon factorization
Every word splits in exactly one way into Lyndon words that never go up in dictionary order (Chen, Fox and Lyndon, 1958). The co-Lyndon factorization is the same with the order reversed.
Uniform
All the pieces of a factorization have the same length.
Weakly increasing, weakly decreasing
Never steps down (equal neighbours allowed), or never steps up.
Conjecture, theorem
A conjecture is a statement believed true but not shown. A theorem is one with a proof.
Inclusion–exclusion
Counting two overlapping groups by adding both and taking away the overlap once.
DATA, b-file
DATA is the short line of terms at the top of an entry. A b-file is a longer table of terms linked from it.
Keyword nonn, easy, more
OEIS tags. nonn: no negative terms. easy: terms are simple to compute. more: the entry needs more terms. The editors swapped more for easy once the formula was proved.
Editor, approved
Any registered user may propose an edit; volunteer editors review it, and an edit goes live only when one approves it. “Approved” is the entry’s status on oeis.org.
Duval’s algorithm
A fast way to compute the Lyndon factorization, in time proportional to the word’s length. The Python on the entry uses it.

Depth 2 · the submission package

What follows is the lab’s own package as it went to the editors, unedited, including the parts they then changed and the narrowing of its own novelty claim. A good order for everyone else: §0, the result, then §3, the proof as it reads on the entry, then §8, what is not claimed, then §10, the editors.

Number of compositions of n with uniform Lyndon factorization and uniform co-Lyndon factorization.

Offset 1. Entry by Gus Wiseman, Nov 13 2019. 25 terms, keyword: more, unchanged since revision #15 (2021-06-20).

What this submission carries changed on 2026-09-18. It was 15 new terms plus a numerical check of Wiseman's conjectured formula. It is now a proof of that conjecture, which supersedes the terms: with the closed form established, every term of the sequence follows from p(n) and d(n), and the 15 new terms are a corollary rather than the contribution.

0 · The result

Theorem. A composition has a uniform Lyndon factorization and a uniform co-Lyndon factorization if and only if it is weakly increasing or weakly decreasing.

Corollary (Wiseman's conjecture). a(n) = 2·A000041(n) − A000005(n) for all n.

The two sets are not merely equinumerous — they are the same set, composition by composition. That is what makes the proof short.

Credit where it is due: Wiseman conjectured this, set-equality and all. The live entry's comment reads "Conjecture: Also the number of compositions of n that are either weakly increasing or weakly decreasing. Hence a(n) = 2A000041(n) - A000005(n)"* (read on oeis.org, 2026-09-18). So the characterisation is his, the derivation of the formula from it is his, and the only thing new here is the proof. An earlier draft of this file read as though noticing the set-equality were part of the contribution; it was noticed independently, which is not the same as first. The comment as submitted says "This proves Wiseman's conjecture", which is the correct claim.

Proof, with every lemma machine-checked over all 65,535 compositions of n ≤ 16: scripts/a329398_proof_check.py in this repository. The proof is reproduced in §3 below in the form it should go into the entry.

Independent support that predates the proof and still stands: the terms n = 26..40 were produced by brute-force enumeration under a conservative prune (method A, src/lab/a329398.py), which reproduces all 25 published terms exactly, and agree with the formula (method B) at every n. A third-party agent, forbidden to read this repository, wrote its own enumerator from the OEIS definition alone and reproduced all 25 published terms and a(26) = 4868 by direct enumeration of all 2²⁵ compositions (A329398-independent-bruteforce.py).

1 · DATA — paste this whole line, replacing what is there

Extended 2026-09-18 at Andrew Howroyd's request (see §10). He noted the 40-term line was 216 characters against a usual length of ~260 and asked for ten more terms. Ten more is a(50), at 295 characters — past the 260 he cited, so both lines are given. Paste the first one; the second is the fallback if he asks for something inside 260.

a(1)-a(50) — what was asked for (295 chars):

1, 2, 4, 7, 12, 18, 28, 40, 57, 80, 110, 148, 200, 266, 348, 457, 592, 764, 978, 1248, 1580, 2000, 2508, 3142, 3913, 4868, 6016, 7430, 9128, 11200, 13682, 16692, 20282, 24616, 29762, 35945, 43272, 52026, 62366, 74668, 89164, 106340, 126520, 150344, 178262, 211112, 249506, 294536, 347047, 408446

a(1)-a(45) — the strict-260 version (255 chars), only if he objects to length:

1, 2, 4, 7, 12, 18, 28, 40, 57, 80, 110, 148, 200, 266, 348, 457, 592, 764, 978, 1248, 1580, 2000, 2508, 3142, 3913, 4868, 6016, 7430, 9128, 11200, 13682, 16692, 20282, 24616, 29762, 35945, 43272, 52026, 62366, 74668, 89164, 106340, 126520, 150344, 178262

Every term is computed by three independent routes that share no machinery: definition-based enumeration of all 2^(n-1) compositions (n ≤ 24), the proved closed form 2*A000041(n) - A000005(n), and a dynamic program counting weakly increasing compositions directly. All three agree, and rows 1..50 of the b-file in §7 match. Terms past n = 24 rest on the theorem rather than on enumeration — that is what the proof buys, and it is the reason the proof should go in with them.

2 · Extensions field

a(26)-a(50) from _Benjamin Schippers_, Sep 18 2026

This replaces the a(26)-a(40) line already in the draft — it is the same unpublished edit, so it stays one line with its original date rather than becoming two. Use a(26)-a(45) if you paste the shorter DATA line.

3 · The comment that matters — the conjecture, proved

Replace nothing; add this. The entry's existing conjecture comment stays where it is, and this sits under it.

Theorem: a composition has a uniform Lyndon factorization and a uniform co-Lyndon factorization if and only if it is weakly increasing or weakly decreasing. This proves Wiseman's conjecture a(n) = 2*A000041(n) - A000005(n).

Proof. Write w for the composition. Recall that a Lyndon word l satisfies l[1] = min(l), and that if |l| >= 2 then l[1] < l[|l|] (otherwise the one-letter suffix would be a proper prefix of l and hence smaller than l). The mirror statements hold for co-Lyndon words: r[1] = max(r), and r[1] > r[|r|] when |r| >= 2.

Suppose the Lyndon factorization of w has all factors of length d and the co-Lyndon factorization has all factors of length e, and suppose d >= 2 and e >= 2. The first Lyndon factor is w[1..d], so w[1] < w[d]; the first co-Lyndon factor is w[1..e], so w[1] > w[e]. If d = e these contradict. If d < e then w[d] lies inside the first co-Lyndon factor, so w[d] <= w[1], contradicting w[1] < w[d]. If d > e then w[e] lies inside the first Lyndon factor, so w[1] <= w[e], contradicting w[1] > w[e]. Hence min(d,e) = 1. If d = 1 the Lyndon factorization is into single letters, whose defining non-increasing order reads w[1] >= w[2] >= ...: w is weakly decreasing. If e = 1 the mirror argument gives w weakly increasing.

Conversely let w be weakly increasing. If w is constant both factorizations are into single letters. Otherwise w is Lyndon: for a proper suffix s = w[i+1..], each s[j] = w[i+j] >= w[j], and s is not a prefix of w (that would force w constant), so w < s at the first strict inequality; then the Lyndon factorization is the single factor w and the co-Lyndon factorization is into single letters. Mirror for weakly decreasing. QED

The corollary follows by inclusion-exclusion: weakly increasing compositions of n are in bijection with the partitions of n, likewise weakly decreasing, and a composition that is both is constant, one for each divisor of n, giving p(n) + p(n) - d(n).

If an editor wants it shorter, the first paragraph alone is the statement, and the rest can go to a Links entry.

4 · FORMULA field

a(n) = 2*A000041(n) - A000005(n). [Proved; see the theorem in COMMENTS.]

5 · PROG — the enumeration, which is now the check rather than the source

(Python)
def duval_lengths(s):
    # standard Lyndon factorization, O(len)
    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, 41)])

A note for the PROG comment, if you want one: the longest Lyndon prefix of a word is the first factor of its standard Lyndon factorization, so iterating Duval's algorithm gives the same factorization the entry's Mathematica computes by testing every prefix — and does it in O(len) rather than O(len^3).

6 · Keywords

keyword: more should come off — the theorem makes every term computable. Leave that edit to the editor and say so in the comment box rather than doing it yourself; changing someone else's keywords in the same edit that adds a proof is how a submission acquires an argument it did not need.

7 · Optional — the b-file

A329398-bfile-b329398.txt in this directory holds n = 1..1000, one term per line in OEIS b-file format. Every row comes from the proved closed form, and rows 1..30 were additionally cross-checked against the independent enumeration before the file was written.

Send it only if you send the proof. A 1000-term b-file backed by an unproved conjecture would be exactly the overclaim this package exists to avoid; backed by the theorem it is just arithmetic. If an editor takes the terms but not the proof, drop the b-file and keep the 45-term DATA line.

8 · What is NOT claimed

9 · The submission itself (a human does this)

  1. Register / log in at https://oeis.org (upper right).
  2. Go to https://oeis.org/A329398 and click edit.
  3. Replace the DATA section with the line in §1.
  4. Add the FORMULA line in §4, the comment in §3, the Extensions line in §2 (with your name and today's date), and the PROG in §5.
  5. In the edit-summary box, write one sentence: "Adds a proof of the conjectured formula; the 15 new terms follow from it. keyword: more can probably come off."
  6. Save changes, then "These changes are ready for review by an OEIS editor".

10 · Editor correspondence — 2026-09-18

The draft went to review and came back the same day.

who what
Alois P. Heinz Proposed the changes for review (three times across the evening).
Andrew Howroyd "See edit screen. (usual length is 260 chars counting spaces and commas). This is currently at 216, so space for a few more terms."
Andrew Howroyd Proposed for review and commented: "Can you add another 10 terms. This is still short of the usual length."
Jianing Song Proposed for review and commented: "Easy since A000041 and A000005 both are."

Three editors are now on it, and none of them has raised the proof, the formula or the comment. The only explicit ask is length. That is a good sign and not a verdict: a draft is proposed for review many times before an editor accepts it.

Song's comment is the interesting one, and it is not about length. It argues for keyword: easy — the terms are easy to compute because A000041 (partitions) and A000005 (number of divisors) both are. That argument only works through a(n) = 2*A000041(n) - A000005(n), which until this submission was a conjecture on the entry. Reading the sequence's difficulty off that formula treats the formula as established, so Song's remark is, implicitly, the proof being used. It is not an acceptance of the proof and should not be reported as one — but it is the first sign a reviewer is reasoning from the theorem rather than about the term count.

It also settles the keyword question in the direction §6 predicted, from the other side: easy going on and more coming off are the same observation, that every term is now computable in closed form.

The one thing to notice. Howroyd's 216-character count for the 40-term line is exactly reproduced by counting the DATA string with its commas and spaces, so his convention and the one used in §1 are the same. Ten more terms therefore lands at 295 characters, which is over the 260 he named. The likeliest reading is that he wants it longer and 260 was a rough target rather than a ceiling — both his comments push the same direction — so §1 leads with the 50-term line. The 45-term line exists so that a length objection costs a paste, not a round trip.

10a · The editors may have already done it — 2026-09-18, later

A report reaching this branch says that within about 80 minutes the editors made the change themselves: Heinz extended DATA to a(46) and set EXTENSIONS to a(26)-a(46), Song swapped more for easy, Howroyd trimmed the FORMULA and COMMENT wording, and Heinz added Cf. A000005, A000041.

This is unverified from here. The OEIS draft page is not fetchable in this session, and the published entry still shows 25 terms, which proves nothing either way because a draft is not merged until an editor accepts it. So it is recorded as a report, not as fact.

If it is accurate, §1 is superseded and must not be pasted — the 50-term line would revert three editors' edits in one save, which is the fastest way to lose the goodwill this draft currently has. The check is the last number on the DATA line: 211112 means 46 terms and the editors have it; 74668 means 40 and §1 still applies; 408446 means the 50-term line already went in.

a(46) = 211112 agrees with the closed form, the enumeration route and the b-file in §7, so if the editors' line ends there, their terms are right and there is nothing to correct.

What this vindicates. §6 said to leave keyword: more to the editor and say so in the comment box rather than editing it. Song removed it unprompted. The editors also wrote the terms themselves rather than waiting — which is the normal way an OEIS draft converges, and a reason not to race them.

Still nobody's call but the editors'. keyword: more coming off, keyword: easy going on, whether the b-file is wanted, and whether the proof is accepted are all theirs. Do not argue any of them into the edit summary — and in particular, do not reply to Song to point out that his argument presupposes the theorem. If he is right, the keyword lands on its own; saying it out loud reads as claiming credit for someone else's edit.