Structural Theory of Recamán's Sequence and Its Subtraction Indices

Abstract

Recamán's sequence (OEIS A005132) is generated by subtracting the step number when the resulting nonnegative value is new, and adding otherwise. This preprint develops an exact structural theory of its addition/subtraction branch word and of its successful-subtraction indices (OEIS A057166), with explicit connections to the maximal alternating-block lengths recorded as OEIS A119632. The paper proves affine two-track formulas and an obstacle race for alternating runs; infinite forbidden families in the gaps of A057166; collision factorizations, parity restrictions, and a six-step witness-transport law; interval deposits, maximal occupied bands, cumulative band births, and an exact remote rank/select merge rule. Under a hypothetical eventually periodic branch word, it proves positive drift, bounded witness age, exact cyclic coverage, the strict obstruction E < p/3, exclusion of p = 3E + 2, and therefore p >= 3E + 4. It also gives exact strip, descent-depth, ordered-excursion, and subset-envelope reductions for the remaining periodic problem. These results do not prove that every nonnegative integer occurs, do not prove non-eventual periodicity, and do not establish an unbounded canonical-memory lower bound. The deposit includes the 34-page preprint, an AI-readable Markdown edition, complete LaTeX and TikZ source, theorem-provenance and literature audits, and reproducibility code.