Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The difference records of OEIS A166944 are unbounded

Proved
A166944Research.difference_records_unbounded

by tara_sooo · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

integer-sequencesnumber-theoryoeisprime-numbersrecurrence

Let aaa be the Rowland-type recursion of OEIS A166944,

a0=0,a1=2,an+2={an+1+gcd⁡(n+2, an+1),n+2 even,an+1+gcd⁡(n, an+1),n+2 odd,a_0=0,\qquad a_1=2,\qquad a_{n+2}=\begin{cases} a_{n+1}+\gcd(n+2,\,a_{n+1}), & n+2 \text{ even},\\[2pt] a_{n+1}+\gcd(n,\,a_{n+1}), & n+2 \text{ odd},\end{cases}a0​=0,a1​=2,an+2​={an+1​+gcd(n+2,an+1​),an+1​+gcd(n,an+1​),​n+2 even,n+2 odd,​

with first differences dn=an−an−1d_n=a_n-a_{n-1}dn​=an​−an−1​. Call RRR a difference record if dn=Rd_n=Rdn​=R for some n≥2n\ge2n≥2 and dk<Rd_k<Rdk​<R for every 2≤k<n2\le k<n2≤k<n: a strict running maximum of (dn)(d_n)(dn​), attained.

The theorem asserts that these records are unbounded:

∀M∈N    ∃R∈N,    M<R  ∧  R is a difference record.\forall M\in\mathbb{N}\;\; \exists R\in\mathbb{N},\;\; M<R \;\wedge\; R \text{ is a difference record}.∀M∈N∃R∈N,M<R∧R is a difference record.

Equivalently, for every threshold MMM there is an index at which the difference sequence exceeds MMM for the first time. The proof is effective: the witness satisfies R=M+O(M1+ε)R=M+O(M^{1+\varepsilon})R=M+O(M1+ε) uniformly, because the argument bounds the index of the next record above MMM by an explicit least common multiple.

This is the monotone half of the A166944 conjecture and it is the step that turns the conjecture into a statement about primality alone. The conjecture itself,

∀R,  5<R⇒(R is a difference record)⇒(R and R−2 are both prime),\forall R,\; 5<R \Rightarrow \bigl(R \text{ is a difference record}\bigr) \Rightarrow \bigl(R \text{ and } R-2 \text{ are both prime}\bigr),∀R,5<R⇒(R is a difference record)⇒(R and R−2 are both prime),

is open; this theorem removes the combinatorial part of it and leaves only the arithmetic part. It is the natural first lemma for anyone approaching the conjecture, and the companion theorem unbounded_greater_twin_primes_of_target records that the conjecture would imply arbitrarily large twin-prime pairs.

Formalization Note Indices are restricted to ≥2\ge2≥2 throughout, the range in which d is the true difference rather than a truncated subtraction. R is the value of the record, not its index; the index is bounded separately by recordHorizonBound.

Preamble
import Definitions.Def_a166944_record_core

open A166944Research
Formal statement
namespace A166944Research

theorem difference_records_unbounded (M : Nat) :
    ∃ R : Nat, M < R ∧ IsDifferenceRecord R := by sorry

end A166944Research
Source
OEIS Foundation, sequence A166944, https://oeis.org/A166944. Machine-checked statement and proof: https://github.com/tara-sooo/A166944-Lean/blob/a05fb69fa826efed102c141a5be901bbcfaa9f9f/A166944/RecordBarrier.lean (theorem difference_records_unbounded; the bound on the record index is recordHorizonBound). The open primality half is the target `OeisA166944.conjecture` in google-deepmind/formal-conjectures@8323e878b83fcd7f4a448256069352a265460d75, FormalConjectures/OEIS/166944.lean.

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me