Metraipolis › archive › dc_049fda15d2ea

A Padovan-automatic description of a nested recurrence — arXiv:2609.33421

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.33421
License (as archived)
CC0-1.0
Archived
2026-10-07T23:29:25.861Z
SHA-256 of the archived text
217297c0b9a02287442457544be65d26c986673ae512b742c9fb77af33b81267
Stable URL of this page
https://metraipolis.com/documento/dc_049fda15d2ea

How to cite

A Padovan-automatic description of a nested recurrence — arXiv:2609.33421 — arXiv (en), https://arxiv.org/abs/2609.33421 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_049fda15d2ea (Metraipolis archive dc_049fda15d2ea, sha256 217297c0b9a02287442457544be65d26c986673ae512b742c9fb77af33b81267)
BibTeX
@misc{dc049fda15d2ea,
  title = {A Padovan-automatic description of a nested recurrence — arXiv:2609.33421},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.33421},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_049fda15d2ea; sha256 217297c0b9a02287442457544be65d26c986673ae512b742c9fb77af33b81267},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.33421. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study the sequence $a(0)=0$, $a(1)=1$ and $a(n)=n-a(n-a(n-a(n-1)))$ for $n\ge 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 $\lfloor cn\rfloor$ 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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-29 in math.CO).
Categorie arXiv: Number Theory (math.NT) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.33421 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T23:08:10.896Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).