Fabian Arevalo

Computational research note · Finch's regularity conjecture

Certificates for regularity in Ulam's 1-additive sequences

32 sequences certified regular — 20 in cases open since 1995 — plus an exceptional family in U(4,b) at b = 2k−1.
August 2, 2026 · code, data & certificates in the companion repository.

Start here — no maths required

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.

Horizontal axis
How many even numbers ever show up, starting from 4 and b. Computed directly, not fitted: for every odd b from 5 to 513 (255 values, no gaps), the count is 3 — except at exactly seven values, where a fourth even number appears. Hover to read off any b. Switch the axis to log₂(b+1): the seven spikes snap onto an evenly spaced integer grid, which is the signature of "b is one less than a power of two" (b = 2k−1 ⟺ log₂(b+1) = k exactly).

What this note adds

Applying the window idea to many starting pairs at once:

  1. A proof that turns "does it repeat" into a finite checklist. Three conditions, checkable in exact whole-number arithmetic, together prove a sequence is regular — and the checklist cannot be tricked by stopping the search too early (it catches its own mistakes; see the box in section 2).
  2. 32 more starting pairs confirmed regular, 20 of them in cases nobody had settled before — including every one of the "4 and b" pairs with b one more than a multiple of 4, which is exactly the gap the 1995 proof left open.
  3. A hidden fourth number. Starting from 4 and b, the list almost always contains exactly three even numbers, ever — except when b is one less than a power of two (7, 15, 31, 63, 127, 255, 511), where a fourth even number always shows up, always given by the same formula. Checked for all 255 odd starting values from 5 to 513.
  4. A concrete culprit. The 1995 proof that covers some of these pairs works by showing there are precisely three even numbers, ever. At b = 7, 15, 31, … there are secretly four — exactly the case that proof does not reach.

Everything below is the technical version. Section 2 has the proof; section 4 has the exceptional family in full.

AbstractSummary of results

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.

Section 1Definitions, and the window rule

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.

Lemma 1 — the window rule

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.

The window rule, run live on U(4,11). Filled cells are odd numbers actually in the sequence (computed directly from the definition, in your browser); empty cells are not. Press Step to watch the rule from Lemma 1 decide each one in turn, using only the three even numbers E = {4,26,48} and the window of earlier decisions — exactly the mechanism Theorem 1 turns into a proof.

Section 2The certificate

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.

Theorem 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. ∎

Remark — self-correction

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.

Section 3Thirty-two certified sequences

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.

ab certifiedstatus
45, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49 (b ≡ 1 mod 4)Control Cassaigne–Finch 1995
47, 11, 19, 23, 27, 35, 39, 43 (b ≡ 3 mod 4)New reported open
67, 11New reported open
89, 11New reported open
1011, 13, 17New reported open
1213, 17New reported open
1415New reported open
1617New reported open
1819New 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:

aE
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.

Section 4The exceptional family in U(4,b)

Result — CERTIFIED

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.

Conjecture A — open

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.

Section 5The 2-adic period law

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:

(⋆)
P = 2⌊log₂(b−1)⌋+3 · (b+1)
CERTIFIED for the 13 values tested (each P comes from a certificate — exact, not a fit). The law itself is conjectural.
The period law, evaluated live (dashed), against the 20 certified periods for a = 4 (measurement). Filled circles obey the law exactly, including b = 19 — a b ≡ 3 (mod 4) case that unexpectedly sits on the b ≡ 1 (mod 4) curve. Hollow diamonds are the six other b ≡ 3 (mod 4) cases: their periods carry a large prime factor and sit far from the dashed curve. U(4,7)'s period is off the top of this comparison entirely. Hover to compare any point against the law's prediction.

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.

Conjecture B — open

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.

Section 6Prior work, and what we could not verify

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).

Section 7Open questions

  1. Prove Conjecture A. The identity 4b²+2b−4 = b(4b+4)−(2b+4) and the 2-adic law of section 5 are the two threads.
  2. Prove regularity of U(4,b) for all b ≡ 3 (mod 4) — the open Cassaigne–Finch case. Conjecture A says the even set is {4,2b+4,4b+4} plus, when b = 2k−1, the single element 4b²+2b−4; with that in hand, a uniform version of Theorem 1 parametrised by b is the natural route.
  3. Certify the remaining exceptional sequences. U(4,7) is certified, at considerable cost (X₁ = 80,188,659, P = 11,301,098 — about 5000× the fundamental difference of any neighbouring U(4,b) with b ≤ 49). U(4,15), U(4,31) and U(4,63) remain uncertified: Brent's algorithm closed no cycle within 1.5·10⁹ automaton steps for any of them, against periods in the thousands for neighbouring b. Whether the exceptional periods grow like b², like 2b, or not at all is open.
  4. Is the converse of Finch's criterion true — does regular imply finitely many even elements? Every source found states only the forward direction.
  5. Extend to a = 12, 14, 16, … and to the conjectured class a odd ≥ 7, b even, where nothing at all is proved.