Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Prime-prefix state and block scanner

Definition
ErdosProblems_Erdos251_PaperStreamingCertificateV5

by willcook · Sep 27, 2026 · Mathlib c5ea003 (Lean v4.30.0)

erdos-251formalizationprime-series

Defines the binary Horner accumulator H0=0H_0=0H0​=0, Hn+1=2Hn+pnH_{n+1}=2H_n+p_nHn+1​=2Hn​+pn​, the prime-prefix state, and a scanner over finite integer intervals. At a prime mmm the scanner increments the count and updates AAA to 2A+m2A+m2A+m; at other integers it leaves the pair unchanged. Separate theorems prove the prefix semantics and block-composition rule.

Definition code
import Definitions.Def_ErdosProblems_Erdos251_PrimeGapDyadicTail
import Definitions.Def_ErdosProblems_Erdos251_KernelDenominatorFloor
import Definitions.Def_ErdosProblems_Erdos251_GcdPrimality
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Analysis.SpecificLimits.Normed
import Mathlib.Data.Nat.Factorization.Basic
import Mathlib.Data.Nat.Periodic
import Mathlib.Data.Nat.Prime.Factorial
import Mathlib.Data.Nat.Prime.Nth
import Mathlib.Data.Nat.PrimeFin
import Mathlib.Data.Rat.Lemmas
import Mathlib.NumberTheory.Bertrand
import Mathlib.NumberTheory.PowModTotient
import Mathlib.NumberTheory.PrimeCounting
import Mathlib.NumberTheory.Real.Irrational
import Mathlib.Tactic.FieldSimp
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Ring
import Mathlib.Topology.Algebra.InfiniteSum.NatInt

/-!
# Restartable streaming prime certificate

Unlike primeSumLoop, the integer prefix is accumulated by Horner's rule:
A <- 2*A+p when a prime is encountered.  Fixed-size blocks can be compiled
separately and their endpoint equalities chained.  Generated endpoint
literals are not trusted: each block must succeed with `decide +kernel`.
Neither native_decide nor an external primality oracle is used.  Primality
is decided by `Fast.isPrimeG` (`GcdPrimality`), which equals the
trial-division test `isPrimeTD` and costs one gcd per scanned integer.
-/

open scoped BigOperators
open Finset
namespace ErdosProblems.Erdos251.PaperV5.Streaming

noncomputable def primeHorner : ℕ → ℕ
  | 0 => 0
  | n + 1 => 2 * primeHorner n + prime0 n



def step (m : ℕ) (s : ℕ × ℕ) : ℕ × ℕ :=
  if Fast.isPrimeG m then (s.1 + 1, 2 * s.2 + m) else s

def primePrefix : ℕ → ℕ × ℕ
  | 0 => (0, 0)
  | m + 1 => step m (primePrefix m)




def scanBlock (start length : ℕ) (s : ℕ × ℕ) : ℕ × ℕ :=
  match length with
  | 0 => s
  | length + 1 => scanBlock (start + 1) length (step start s)
termination_by length







end ErdosProblems.Erdos251.PaperV5.Streaming
Source
Pinned Lean definitions: https://github.com/wcook04/plectis-erdos-lean/blob/6e2d392bd294bd9883859fb86c49655e7567086e/ErdosProblems/Erdos251/PaperStreamingCertificateV5.lean#L19-L21; https://github.com/wcook04/plectis-erdos-lean/blob/6e2d392bd294bd9883859fb86c49655e7567086e/ErdosProblems/Erdos251/PaperStreamingCertificateV5.lean#L36-L37; https://github.com/wcook04/plectis-erdos-lean/blob/6e2d392bd294bd9883859fb86c49655e7567086e/ErdosProblems/Erdos251/PaperStreamingCertificateV5.lean#L39-L41; https://github.com/wcook04/plectis-erdos-lean/blob/6e2d392bd294bd9883859fb86c49655e7567086e/ErdosProblems/Erdos251/PaperStreamingCertificateV5.lean#L59-L63

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