OEIS A166944 — the moving-horizon replay: states, steps, paths, and the attained-maximum cap
Definitiona166944_moving_horizonThis bundle fixes the moving-horizon replay of the OEIS A166944 recursion: the dynamical system in which the proofs about difference records are carried out.
Let be the recursion, its first differences and its offset from the identity. A moving-horizon state is a pair with , and : the index together with the horizon at which the offset has arrived. Because is constant along a run of unit increments, the recursion is quiet between states, and a step
records the first index at which the increment is nontrivial, together with the new horizon . The step carries the arithmetic content of the transition: , and the entire interval is a unit tail in which .
A path is a finite chain of such steps, recorded by the relation HasMovingHorizonPathTo s C sf Cf q, which additionally names the terminal state and the number of steps. This is the object the project bounds: the question of how far a replay travels is the question of how large can be, and every quantitative result in the development is a statement about a path.
Finally, is an attained running maximum through index when every difference up to is at most and the value itself occurs. A replay from a difference record is run under this cap, so its steps can never produce an increment exceeding ; this is what makes the dynamics terminate at the next record and what the phrase 'capped replay' refers to.
Together these five declarations are the vocabulary in which the A166944 conjecture is reduced to a single inequality about the terminal index of a path.
Formalization Note The path relation is defined by recursion on the step count, with the base case requiring the named endpoint to be the actual endpoint. The step condition r <= C keeps the event inside the horizon; without it the recurrence could not be jumped to a well-defined next state. Indices are restricted to in IsAttainedPreviousMaximum, the range in which d is a genuine difference. This bundle imports Def_a166944_record_core for the recursion itself, so the two share one vocabulary.
import Mathlib.Data.Nat.Prime.Defs
import Definitions.Def_a166944_record_core
namespace A166944Research
/-- A moving-horizon state: the offset `C = D s` exceeds the index. -/
def IsMovingHorizonState (s C : Nat) : Prop :=
2 ≤ s ∧ D s = C ∧ s < C
/-- One first-event transition, including the unit tail and the next state. -/
def IsMovingHorizonStep (s C r C' : Nat) : Prop :=
IsMovingHorizonState s C ∧ s < r ∧ r ≤ C ∧ 1 < d r ∧
(∀ j : Nat, s < j → j < r → d j = 1) ∧
D (r - 1) = C ∧ C' = D r ∧ C + 2 ≤ C' ∧
IsMovingHorizonState r C'
/-- A finite first-hit path with an explicitly named endpoint. -/
def HasMovingHorizonPathTo (s C sf Cf : Nat) : Nat → Prop
| 0 => s = sf ∧ C = Cf ∧ IsMovingHorizonState s C
| Nat.succ q =>
IsMovingHorizonState s C ∧
∃ r C', IsMovingHorizonStep s C r C' ∧
HasMovingHorizonPathTo r C' sf Cf q
/-- `P` is an attained running maximum through index `k`: every difference up to
`k` is at most `P`, and `P` itself occurs. This is the cap that makes a replay
'capped'. -/
def IsAttainedPreviousMaximum (P k : Nat) : Prop :=
(∀ j : Nat, 2 ≤ j → j ≤ k → d j ≤ P) ∧
∃ r : Nat, 2 ≤ r ∧ r ≤ k ∧ d r = P
end A166944Research