Computational research note · Finch's regularity conjecture
Start with two numbers, say 1 and 2. Build a list: each new number is the smallest one bigger than your last that can be written as the sum of two different earlier numbers on the list — but in only one way.
Starting from 1, 2 you get 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, … — a sequence Stanisław Ulam wrote down in the 1960s, and which still looks patternless today. But start from a different pair and something else can happen: the gaps between consecutive numbers can settle into a block that repeats forever. Sequences like that are called regular, and in 1991 Steve Finch guessed exactly which starting pairs give regular ones. Only two families were ever proved right, and nothing had been added in over thirty years.
The idea that breaks the logjam is almost mechanical: if only finitely many even numbers ever show up, then whether the next odd number joins the list depends only on a short, fixed stretch of numbers just behind it — like a machine reading a tape through a small window. A machine like that, if it ever repeats what it's looking at, must repeat forever after. That turns "does this list eventually repeat" from an endless question into a finite check a computer can settle for good.
Applying the window idea to many starting pairs at once:
Everything below is the technical version. Section 2 has the proof; section 4 has the exceptional family in full.
Let U(a,b) denote the 1-additive (Ulam-type) sequence beginning a < b in which every later term is the least integer exceeding the previous term that has exactly one representation as a sum of two distinct earlier terms. U(a,b) is regular if its sequence of successive differences is eventually periodic. Finch conjectured a precise classification of the regular U(a,b); the only families ever proved regular are U(2,v) for odd v ≥ 5 (Schmerl–Spiegel 1994) and U(4,v) for v ≡ 1 (mod 4), v ≥ 5 (Cassaigne–Finch 1995) — both secondary citations, see section 6.
This note does three things. Theorem 1 reduces regularity of a single U(a,b) to a finite list of conditions checkable in exact integer arithmetic, and makes the reduction self-correcting: the conditions cannot be satisfied with an incomplete set of even elements. Applying it, we certify regularity for 32 sequences, of which 20 lie in cases reported open: U(4,b) for b ≡ 3 (mod 4), b ∈ {7, 11, 19, 23, 27, 35, 39, 43}; U(6,7), U(6,11); U(8,9), U(8,11); U(10,11), U(10,13), U(10,17); U(12,13), U(12,17); U(14,15); U(16,17); U(18,19). The other 12 reproduce Cassaigne–Finch and serve as controls. We also exhibit an exceptional family: for every odd b with 5 ≤ b ≤ 513, the even elements of U(4,b) are exactly {4, 2b+4, 4b+4} — except for the seven values b = 2k−1, k = 3,…,9, where a single further even element appears, at exactly 4b²+2b−4. This is, we believe, the obstruction that stops the Cassaigne–Finch argument at v ≡ 1 (mod 4): their proof is shaped around "U(4,v) has precisely three even terms", and that statement is false for v = 2k−1, all of which are ≡ 3 (mod 4). Nothing here proves Finch's conjecture, and nothing here claims to.
For 0 < a < b, U(a,b) is the increasing sequence with u₁ = a, u₂ = b, and un+1 the least integer > un having exactly one representation ui+uj with i < j ≤ n. Write U for the underlying set. U(a,b) is regular if the difference sequence (un+1−un) is eventually periodic; the fundamental difference is the sum of one period of that sequence, and the period is the number of terms per fundamental difference. If gcd(a,b) = d then U(a,b) = d·U(a/d,b/d), so we take gcd(a,b) = 1; throughout, a is even and b is odd. E denotes the set of even elements of U and W = max E.
Suppose the even elements of U are exactly E, a finite set. Then for every odd x > W,
x ∈ U ⟺ #{e ∈ E : x−e ∈ U} = 1.
Proof. Let x be odd and x = u+v with u < v both in U. Since x is odd, exactly one of u, v is even, so exactly one lies in E. Conversely each e ∈ E with x−e ∈ U yields the representation x = e+(x−e), and its two entries are distinct because one is even and one is odd. Distinct e give distinct unordered pairs. Hence the number of representations of x equals #{e ∈ E : x−e ∈ U}, and x ∈ U iff that count is 1. ∎
The right-hand side reads the indicator of U only on the odd integers in [x−W, x). So the odd part of U is generated by a deterministic automaton whose state is a window of W/2 bits. This is what makes eventual periodicity provable rather than merely observed: if the window state at odd x₁ equals the state at x₁+P, the two futures are identical, forever.
Fix a even, b odd, and a horizon X₀. Compute U ∩ [0,X₀] exactly from the definition and set E := the even elements found, W := max E. Define an auxiliary set U* by U* ∩ [0,X₀] := U ∩ [0,X₀], and for x > X₀: x ∈ U* iff x is odd and #{e ∈ E : x−e ∈ U*} = 1. U* is well defined (the rule reads only smaller integers) and computable. Now consider three conditions.
(P) Periodicity. There are odd X₁ > X₀+W and even P > 0 such that the window states of U* at X₁ and at X₁+P coincide. Set R := {r ∈ ZP : the odd integers ≥ X₁ congruent to r mod P lie in U*}, S := {odd elements of U* below X₁}, B := 2X₁+4P+2W+4.
(C) Residue cover. For every even c ∈ ZP, either there exist r,s ∈ R with r+s ≡ c (mod P), or β(c) := #{u ∈ S : (c−u) mod P ∈ R} ≠ 1.
(F) Finite check. Every even x with X₀ < x ≤ B has a number of representations as a sum of two distinct elements of U* different from 1.
If (P), (C) and (F) hold, then U* = U. Consequently the even elements of U(a,b) are exactly E, the indicator of U on the odd integers ≥ X₁ is periodic with period P, and U(a,b) is regular.
Proof. By strong induction on x > X₀ we show x ∈ U ⟺ x ∈ U*; the base case x ≤ X₀ is the exact computation. Assume U ∩ [0,x) = U* ∩ [0,x).
If x is odd: by the inductive hypothesis and the fact that U* has no even element above X₀, the even elements of U below x are exactly E. Lemma 1 applies verbatim with U* in place of U, and its right-hand side is the rule defining U*. Hence x ∈ U ⟺ x ∈ U*.
If x is even, we must show x has a number of representations ≠ 1. For X₀ < x ≤ B this is (F). So let x > B and split the representations x = u+v, u < v, u,v ∈ U*, by size. Both even: then u,v ∈ E, so x ≤ 2W < B, excluded. Both odd and both ≥ X₁: call the count A(x); since membership of an odd integer ≥ X₁ depends only on its residue mod P, A(x) > 0 iff there are r,s ∈ R with r+s ≡ x (mod P), and when such r,s exist, every u ≡ r (mod P) with X₁ ≤ u < x/2 gives a valid pair, and there are at least ⌊(x/2−X₁)/P⌋ ≥ 2 of them because x > B ≥ 2X₁+4P — so A(x) ≥ 2. Exactly one < X₁: since x > 2X₁, the smaller element ranges over S and the count is exactly β(x mod P). Therefore for x > B, either the first alternative of (C) holds and A(x) ≥ 2, or A(x) = 0 and the total is β(x mod P) ≠ 1 by (C); either way the count is ≠ 1. This closes the induction, so U = U*, whose even elements are exactly E and whose odd part is periodic with period P from X₁ on by (P). A set that is eventually periodic with positive density in each period has an eventually periodic difference sequence, so U(a,b) is regular. ∎
Theorem 1 cannot be fooled by an X₀ chosen too small. If U has an even element Y > X₀, then either Y ≤ B, and (F) fails at x = Y; or Y > B, and the argument above shows Y has ≠ 1 representations in U*, contradicting Y ∈ U, so (C) must fail. This is not hypothetical: the verifier run on U(4,63) with X₀ = 4000 rejects, reporting even-15998-has-exactly-one-rep, and 15998 = 4·63²+2·63−4 is precisely the exceptional even element of section 4. The check is a genuine filter, not a rubber stamp.
Theorem 1 is a proof. Conditions (P), (C), (F) for a specific (a,b) are an exact finite computation. We therefore label Theorem 1 PROVED and each individual regularity result CERTIFIED, and do not describe the computation itself as a proof.
Two independently written programs implement Theorem 1: a Python one (certify.py, hash-table cycle detection) and a C one (verify_cert.c, Brent cycle detection, O(1) memory, written from the statement of the theorem rather than ported). All 32 rows were produced by the C verifier. 23 of the 32 were also produced independently by the Python certifier, and on those 23 the two agree on E, P and |R| exactly — X₁ may legitimately differ, since any valid X₁ proves the theorem. The remaining 9 rows — U(4,7), U(4,43), U(8,11), U(10,11), U(10,17), U(12,17), U(14,15), U(16,17), U(18,19) — rest on the C verifier alone, because the Python implementation's memory use is proportional to the period and could not reach them. That is a real asymmetry in the evidence, flagged as a defect in the conjecture README.
| a | b certified | status |
|---|---|---|
| 4 | 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49 (b ≡ 1 mod 4) | Control Cassaigne–Finch 1995 |
| 4 | 7, 11, 19, 23, 27, 35, 39, 43 (b ≡ 3 mod 4) | New reported open |
| 6 | 7, 11 | New reported open |
| 8 | 9, 11 | New reported open |
| 10 | 11, 13, 17 | New reported open |
| 12 | 13, 17 | New reported open |
| 14 | 15 | New reported open |
| 16 | 17 | New reported open |
| 18 | 19 | New reported open |
Full table with W, X₀, X₁, P, |R|, B for every row: data/certificates.csv.
The even sets found are, in every certified case, exactly {a} ∪ {2jb+a : 1 ≤ j ≤ a/2}, plus for a ≥ 6 a single further element (2a+4)b:
| a | E |
|---|---|
| 4 | {4, 2b+4, 4b+4} |
| 6 | {6, 2b+6, 4b+6, 6b+6, 16b} |
| 8 | {8, 2b+8, 4b+8, 6b+8, 8b+8, 20b} |
| 10 | {10, 2b+10, 4b+10, 6b+10, 8b+10, 10b+10, 24b} |
| 12 | {12, 2b+12, …, 12b+12, 28b} |
| 14 | {14, 2b+14, …, 14b+14, 32b} |
| 16 | {16, 2b+16, …, 16b+16, 36b} |
| 18 | {18, 2b+18, …, 18b+18, 40b} |
Verified for the certified pairs above; CERTIFIED on that range, conjectural beyond it.
For every odd b with 5 ≤ b ≤ 513 — all 255 values, no gaps — the even elements of U(4,b) below 6b²+4000 are exactly {4, 2b+4, 4b+4}, except for b ∈ {7, 15, 31, 63, 127, 255, 511}, where there is exactly one further even element, equal in every case to 4b²+2b−4 (206, 926, 3902, 15998, 64766, 260606, 1045502). See the figure in the opening section.
The seven exceptional values are exactly 2k−1 for k = 3,…,9, and all are ≡ 3 (mod 4). Note the identity 4b²+2b−4 = b·(4b+4) − (2b+4): the new even element is b times the largest generic even element, minus the middle one.
Scope of the claim. This is an exact computation of U(4,b) from the definition up to 6b²+4000; on its own it says nothing about even elements above that bound. For the pairs of section 3 the certificates close the even set absolutely — in particular U(4,7) is certified, so it has exactly four even elements, {4, 18, 32, 206}, and no more, unconditionally, with fundamental difference P = 11,301,098 — about 5000× that of any neighbouring U(4,b) with b ≤ 49. For the remaining b in the scan the statement is range-limited.
U(4,b) has a fourth even element iff b = 2k−1, and then it equals 4b²+2b−4. Supported by 255 values of b; not proved.
Why this matters. Cassaigne–Finch prove regularity for v ≡ 1 (mod 4) via the statement "U(4,v) has precisely three even terms" (secondary). That statement is false for every v = 2k−1, and those v are all ≡ 3 (mod 4). The exceptional family is therefore a concrete obstruction sitting exactly in the residue class their theorem omits — suggesting the missing case is not merely a gap in the write-up but has real content.
For the certified U(4,b), the fundamental difference P obeys, for every tested b ≡ 1 (mod 4) — twelve values, 5 ≤ b ≤ 49 — and for b = 19:
The remaining certified b ≡ 3 (mod 4) violate the law and are markedly wilder: b = 11 → 1318 = 2·659, 23 → 29858 = 2·14929, 27 → 57862 = 2·7·4133, 35 → 5326 = 2·2663, 39 → 620796 = 2²·3·11·4703, 43 → 5632 = 2⁹·11. Where the law holds, P is 2-power-smooth times b+1; where it fails, P carries a large prime factor. b = 19 already shows the naive "iff b ≡ 1 mod 4" reading is wrong.
P(4,b) = 2⌊log₂(b−1)⌋+3(b+1) for all b ≡ 1 (mod 4). This 2-adic shape is the natural place to look for an explanation of Conjecture A: b = 2k−1 is exactly the case where b+1 is a pure power of 2 and the law would degenerate.
The sandbox had no access to the literature. arxiv.org, oeis.org, erdosproblems.com, mathoverflow.net and every other scholarly host were refused at the egress proxy (HTTP 403 on CONNECT); only GitHub was reachable, and only for this repository. Search-engine summaries were available and were used. Every citation below is therefore secondary — no primary source was read — and must be checked before any of this is submitted anywhere.
The basis for our novelty claim: that U(4,v) for v ≡ 3 (mod 4) and all a ≥ 6 are open rests on search-engine summaries only. If a primary source shows otherwise, the twenty "new" rows of section 3 are rediscoveries and must be relabelled — which would not affect their correctness, only their novelty. This is flagged as the single most important thing to check next; the same holds for Conjecture A and the period law of section 5, either of which may already sit in Finch's own table at oeis.org/FinchSadd.html (unreachable this session).