Roberto Blanco Gómez posts a proof of the A397711 remainder conjecture

In July 2026 I added a sequence to the OEIS (the Online Encyclopedia of Integer Sequences), A397711, with a pattern in it that I had checked by computer and could not prove, so I listed it as a conjecture. Roberto Blanco Gómez, an independent researcher in Spain, then posted a proof of it as a preprint, not yet refereed. This page is about his proof. Apart from its author, no person, me included, has yet read the core of the argument line by line. My own work, as it stood before it, is on the page linked just below.

The order of events:

July 5, 2026: I submitted the entry, with the conjecture, as its author; an OEIS editor approved it on July 12.
October 7, 2026: his preprint went up on Zenodo, and he submitted a comment to the entry pointing to it.
October 12: an OEIS editor approved his comment; approval means the comment was accepted into the entry, not that the proof was reviewed.
October 24: Claude agents working under my direction ran the checks below.

What the conjecture said

A397711 counts dependency charts: numbered tasks, each waiting on at most two others, with no circular waiting. The same charts are the possible structures of a Bayesian network, a kind of probability model used in machine learning and drawn as a chart of arrows. The arrows say how the model is built: each variable is modeled given its parents, the variables with arrows into it. They are often read causally, as direct influence. Here each variable has at most two parents. Mathematicians call these charts labeled directed acyclic graphs (DAGs) with in-degree at most two. Write a(n) for the number of charts on n tasks, divide it by n, and look at the remainder. When n is prime the remainder is always 1: I proved that with the standard rotation argument, on my earlier page. For other sizes I noticed a rule I could not prove:

for every odd number of tasks from 3 on, the remainder is 1;
for every even number from 4 on, it is one more than half the number of tasks.

With four tasks there are 443 charts, and 443 divided by 4 leaves 3, which is 4/2 + 1. I checked the rule for every size up to tasks and wrote it into the entry as "Conjecture (verified for n <= 100)".

The proof

The preprint is his. Its authorship note says that he chose the target and designed the method of checking, and that the computations, the search for the argument and the drafting were done with Claude (Anthropic) working under his direction. It is titled "Congruences for labeled acyclic digraphs of bounded in-degree: a proof of the conjecture in OEIS A397711" and is on Zenodo under an open licence. It gives a proof of the rule for every size, and of a more general result.

A result for any cap. Let each task wait on at most r others, and count the charts on n tasks. His preprint gives a proof that for every n,

n divides lcm(1, 2, ..., r) × (the count − 1),

where lcm(1, 2, ..., r), the least common multiple, is the smallest number that 1, 2, ..., r all divide: 2 for a cap of two, 6 for a cap of three. He starts from a known formula that builds each chart by repeatedly setting aside the tasks that no other task waits on (the recurrence of Eggeling and co-authors, AISTATS 2019, PMLR 89), and works through it one size at a time to show that the divisibility holds at every size.

Odd sizes. With a cap of two the result says that n divides 2 × (a(n) − 1). When n is odd, n shares no factor with 2, so n divides a(n) − 1 itself: the remainder is 1.

Even sizes. For even n the general result allows two remainders, 1 or n/2 + 1. To decide, he puts the tasks around a circle and, for each of the n turns of the circle, counts the charts that the turn leaves unchanged. A classical counting fact (Burnside's lemma) says that these n counts add up to a multiple of n. The turn by zero places leaves all a(n) charts unchanged, and the other turns, apart from the half-turn, add a predictable amount, so the count for the half-turn decides the remainder. That count settles it at n/2 + 1, as the specialist section below shows.

The general result also fits what I had seen in the companion entry, A397712, where the cap is three: there the odd-size rule fails, first at nine tasks, where the remainder is 7, not 1. With a cap of three the general result forces remainder 1 only for sizes divisible by neither 2 nor 3, and nine is divisible by 3, so it allows that failure.

How he did it

He found my conjecture in a sweep, done with Claude, of the OEIS entries numbered A395000 or higher that contained conjectures. His first programs, in Python, compute the counts and test the steps of the proof on small ranges. His preprint says that before attempting the proof he checked the pattern much further than I had: his second program, in Rust, a faster language, written from scratch, confirmed it up to tasks. He ran negative controls, deliberately wrong versions of the claim that his programs had to reject, and they did. The preprint says a second AI system (not named there) reviewed the text with its own code, and its fixes were taken in. The preprint comes with its programs, so anyone can rerun them, and its acknowledgements thank me for the sequence and the conjecture.

How it was re-checked

On October 24, 2026, Claude agents (Anthropic), working under my direction as part of a research project, re-checked the proof.

Two of the checks do not depend on reading the paper. The counting formula his proof starts from, the 2019 recurrence, reproduces all values in my table, from 0 tasks to 100 (with 0 tasks there is one chart, the empty one). I computed that table in July by a different method, a formula that sorts the tasks into levels, so the match checks one method against the other; it does not check the remainder argument built on top of the recurrence. And new programs counted every chart directly from the definition for four, five and six tasks, along with the charts each turn of the circle leaves unchanged.

The other checks start from the paper's statements. New programs, written without reusing his code, confirmed the remainder pattern for every size up to tasks and checked the general result and the steps of the even case over the ranges listed in the specialist section below. His Python check programs, distributed with the preprint, which test the steps of the proof on small ranges, also passed when rerun. Last, a separate Claude session, starting fresh, read the proof step by step and found no gap. It is the same kind of system that helped write the proof, and the new programs were also written by Claude, so they could share a blind spot with it, for example a misreading of a definition.

For specialists: the proof in outline, from the preprint

Conventions, as in the preprint, whose lemma numbers are used here: an arc u → v means that u is a parent of v (task v waits on task u), and a sink is a vertex that is nobody's parent. Write a_r(n) for the number of DAGs on n labeled vertices with every in-degree at most r, so A397711 is a_2, and L_r = lcm(1, ..., r).

The weighted form. Fix s ≥ 1. On g vertices, let each vertex choose a set of at most r parent slots from s copies of each other vertex, subject to the chart obtained by forgetting the copies being acyclic, and let P_g(s) count these choices; P_g(1) = a_r(g). A vertex may take slots from two or more copies of the same vertex; forgetting the copies then gives a single arc, since the chart has an arc u → v whenever at least one copy of u is among v's slots. With f(m) = sum_{i=0..r} C(sm, i), the number of slot sets drawn from m other vertices, inclusion-exclusion over the set of sinks gives (Lemma 4)

P_g(s) = sum_{k=1..g} (-1)^(k+1) C(g, k) f(g-k)^k P_{g-k}(s),

with P_0(s) = 1 (the empty structure).

Each of the k sinks chooses its slots freely among the copies of the g − k non-sink vertices, which is why the cap on parents factors over sinks; at s = 1 this is the recurrence of Eggeling, Viinikka, Vuoksenmaa and Koivisto (AISTATS 2019, PMLR 89, Corollary 4). Since C(sm, i) = (sm/i) C(sm-1, i-1), the number L_r (f(m) - 1) is divisible by sm (Lemma 5), and induction on g through the recurrence gives sg | L_r (P_g(s) - 1) (Lemma 6). Taking s = 1 is the general result: n | L_r (a_r(n) - 1). For r = 2 and odd n this is the odd case.

Even n ≥ 4, cap two. The rotation i ↦ i + 1 (mod n) acts on the DAGs by relabeling. By Burnside's lemma (the number of orbits, the families of DAGs that the rotations cycle through, is the average number of DAGs fixed by a rotation), the fixed-point counts of the n rotations sum to a multiple of n. A rotation of order d has n/d cycles of length d. A DAG it fixes has all parents of a vertex in other cycles (a parent in the same cycle would force a directed cycle), and recording each parent of one representative per cycle as (cycle, position) is a bijection with the weighted structures above on the n/d cycles with s = d (Lemma 7). So that rotation fixes P_{n/d}(d) DAGs, and φ(d) rotations have order d. Hence, modulo n,

a_2(n) ≡ - sum over d | n, d > 1 of φ(d) P_{n/d}(d).

For d ≥ 3, the weighted version, Lemma 6 with s = d and g = n/d (not the general result, which is its case s = 1), gives n | 2(P_{n/d}(d) - 1); and φ(d) is even for d ≥ 3, so each such term is ≡ φ(d) (mod n); these add to n - 2. The remaining term, d = 2, is the half-turn, which swaps vertex i with vertex i + n/2. Lemma 8 shows that for every g ≥ 2, P_g(2) ≡ g + 1 (mod 2g), that is, (P_g(2) - 1)/g is odd, by running the induction of Lemma 6 modulo 2g. As written above, the recurrence has a term ±1 (from k = g, where P_0 = 1), so it is first rewritten, as in the proof of Lemma 6 (the preprint's equation 3.1): write m = g - k for the vertices left after removing k sinks and E_m = P_m(2) - 1 (with E_0 = E_1 = 0), expand f(m)^k in powers j of f(m) - 1, and use that the signs (-1)^(k+1) C(g, k) add up to 1, so that P_g(2) - 1 becomes a sum of terms built from the E_m and the powers of f(m) - 1. In that form every term is g times an integer, and the parities of those integers add up to (2^(g-1) - 2) + (g - 1) + (2^(g-1) - g), which is odd. The first sum collects the terms that carry a smaller count P_m(2) - 1 with m ≥ 2, of parity C(g-1, k) for 1 ≤ k ≤ g-2; the second, g - 1, is the single term with one vertex left (m = 1) and j = 1; the third collects the terms with m = 1 and j ≥ 2, of parity C(g-1, j) for 2 ≤ j ≤ g-1. Every other term is even. With g = n/2 this gives P_{n/2}(2) ≡ n/2 + 1 (mod n), so a_2(n) ≡ -((n - 2) + (n/2 + 1)) ≡ n/2 + 1 (mod n).

With four tasks: the turns by one and by three places fix only the empty chart, the half-turn fixes 7 charts (7 leaves 3 when divided by 4, as Lemma 8 says), and 443 + 1 + 7 + 1 = 452 = 4 × 113.

Ranges checked by computer, all in one place. His preprint (section 7) reports that his second program, in Rust, checked the conjecture for 3 ≤ n ≤ 2500, Lemma 8 for g ≤ 2500, and Lemma 6 for r ≤ 6, s ≤ 8, g ≤ 80. The programs that Claude agents wrote and ran for me on October 24 checked the conjecture for 3 ≤ n ≤ 400; the general result for r ≤ 6 and n ≤ 150, where for each r the least multiplier that works for every n in that range is exactly L_r, so no proper divisor of L_r would do (the preprint reports this for the same range in section 1, from his programs, and ours re-computed it; it is a numerical finding for that range, not a theorem); Lemma 6 for r ≤ 4, s ≤ 8, g ≤ 40; Lemma 8 for 2 ≤ g ≤ 300, which is the half-turn count for every even n from 4 to 600, since n = 2g; and Lemma 7 by brute force for four, five and six tasks.

The proof is a preprint and has not been refereed. The computer checks cover sizes up to a limit; the argument for every size rests on reading it.

Roberto Blanco Gómez posts a proof of the A397711 remainder conjecture

What the conjecture said

The proof

How he did it

How it was re-checked

How to cite this

See also

What the conjecture said#

The proof#

How he did it#

How it was re-checked#

How to cite this

See also

What the conjecture said

The proof

How he did it

How it was re-checked