A Padovan-automatic description of a nested recurrence
Abstract
We study the sequence a(0)=0, a(1)=1 and a(n)=n−a(n−a(n−a(n−1))) for n≥ 2, listed as A076502 in the On-Line Encyclopedia of Integer Sequences. We identify a(n) as a two-position shift in the greedy Padovan numeration system, with a finite-state correction. The proof constructs an addition automaton from an exact integer-carry invariant and certifies its completeness by finite-language inclusion; a synchronized automaton then verifies the nested recurrence. We establish bounded discrepancy from the line of slope c, where c3−c2+2c−1=0, and show that the exact set of offsets from ⌊ cn⌋ is {−1,0,1,2}. We construct an explicit 26-letter non-erasing morphic presentation of the first-difference word, prove that its least balance constant is 4, and give an effective procedure for enclosing the global discrepancy extrema to arbitrary accuracy. We formalize the recurrence identification, six-decimal discrepancy bound, exact offset set, concrete morphic identity, least balance constant, and an effective extrema algorithm in Lean. Separate exact computations refine the numerical enclosures.
Related
- A nested factor model for equity markets: reconciling multifractal stock returns and rough index volatilities
- The Intersection of nested filled-in little Julia sets have zero area
- An example of an automatic sequence with non-regular abelian complexity
- NESTED DISCONTINUOUS ASYMPTOTIC PROFILES FOR THE VISCOUS BURGERS EQUATION WITH INFINITE MASS
- Surjectivity of real-linear Cauchy--Riemann operators: from the minimal Harder--Narasimhan slope to automatic transversality
BibTeX
@misc{cloitre2026padovanautomatic,
title = {{A Padovan-automatic description of a nested recurrence}},
author = {Benoit Cloitre and Haobo Ma and Wenlin Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.33421},
eprint = {2609.33421},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.33421},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Padovan-automatic description of a nested recurrence
AU - Benoit Cloitre
AU - Haobo Ma
AU - Wenlin Zhang
PY - 2026
DA - 2026/09/27
PB - arXiv
DO - 10.48550/arxiv.2609.33421
UR - https://arxiv.org/abs/2609.33421
AB - We study the sequence a(0)=0, a(1)=1 and a(n)=n−a(n−a(n−a(n−1))) for n≥ 2, listed as A076502 in the On-Line Encyclopedia of Integer Sequences. We identify a(n) as a two-position shift in the greedy Padovan numeration system, with a finite-state correction. The proof constructs an addition automaton from an exact integer-carry invariant and certifies its completeness by finite-language inclusion; a synchronized automaton then verifies the nested recurrence. We establish bounded discrepancy from the line of slope c, where c^3−c^2+2c−1=0, and show that the exact set of offsets from ⌊ cn⌋ is {−1,0,1,2}. We construct an explicit 26-letter non-erasing morphic presentation of the first-difference word, prove that its least balance constant is 4, and give an effective procedure for enclosing the global discrepancy extrema to arbitrary accuracy. We formalize the recurrence identification, six-decimal discrepancy bound, exact offset set, concrete morphic identity, least balance constant, and an effective extrema algorithm in Lean. Separate exact computations refine the numerical enclosures.
ER -