A near-linear upper bound for the Yellowstone permutation: a(n) <= n (ln n)^7 for every n >= 3
Abstract
The Yellowstone permutation (OEIS A098550) is defined by a(1), a(2), a(3) = 1, 2, 3 and, for n >= 4, a(n) is the least positive integer not yet used with gcd(a(n), a(n-2)) > 1 and gcd(a(n), a(n-1)) = 1. Applegate, Havermann, Selcoe, Shevelev, Sloane and Zumkeller (2015) proved that it is a permutation of the positive integers; its growth was described only empirically. We prove the near-linear bound a(n) <= n (ln n)^7 for every n >= 3, and a(n) <= n (ln n)^6 for ln n >= 73.5, as well as the elementary form a(n) <= n 2^(4 ln n / ln ln n) for every n >= 3. The method is a fixed-time iteration: the anchor a(n-2) of a large term determines the term, the primes of the anchor are forced to have many used multiples in a short window below the term, and a Bonferroni count shows that such heavy primes are too few to supply all the anchors. The coprimality input is a self-contained explicit form of Brun's sieve. The explicit constants are computer-assisted: the first 10^8 terms, and a finite list of explicit inequalities checked on cells of ln n in [ln 10^8, 10^40]; beyond ln n = 10^40 the proof is by hand. OEIS Conjecture 7, a(n) <= (pi/2) n ln n, remains open. Manuscript; not submitted to a journal. The results were developed with an AI system (Anthropic Claude) and checked by independent AI referee agents; no human peer review has taken place. A continuation, The Yellowstone permutation, II (doi:10.5281/zenodo.23449375), proves the asymptotic bound a(n) <= (e^gamma/2 + o(1)) n ln n lnlnln n by a different method, and reduces OEIS Conjecture 7 for large n to counting hypotheses. The theorems and constants of this manuscript are unchanged.
Related
- A Linear Lower Bound for Convex Body Chasing in Every ℓp Norm
- A near-linear upper bound for Burr's conjecture
- A linear upper bound for Berge saturation numbers
- A degree-linear upper bound for the Pólya exponent of forms with fixed arity
- Minimal output entropy for the channels that add or remove a box of a Young diagram, and a Pauli principle for every permutation symmetry
BibTeX
@article{haver2026nearlinear,
title = {{A near-linear upper bound for the Yellowstone permutation: a(n) <= n (ln n)^7 for every n >= 3}},
author = {Tomer Haver},
journal = {Zenodo (CERN European Organization for Nuclear Research)},
year = {2026},
month = oct,
doi = {10.5281/zenodo.23437782},
url = {https://doi.org/10.5281/zenodo.23437782},
note = {CC BY},
}
RIS
TY - JOUR
TI - A near-linear upper bound for the Yellowstone permutation: a(n) <= n (ln n)^7 for every n >= 3
AU - Tomer Haver
PY - 2026
DA - 2026/10/17
JO - Zenodo (CERN European Organization for Nuclear Research)
DO - 10.5281/zenodo.23437782
UR - https://doi.org/10.5281/zenodo.23437782
AB - The Yellowstone permutation (OEIS A098550) is defined by a(1), a(2), a(3) = 1, 2, 3 and, for n >= 4, a(n) is the least positive integer not yet used with gcd(a(n), a(n-2)) > 1 and gcd(a(n), a(n-1)) = 1. Applegate, Havermann, Selcoe, Shevelev, Sloane and Zumkeller (2015) proved that it is a permutation of the positive integers; its growth was described only empirically. We prove the near-linear bound a(n) <= n (ln n)^7 for every n >= 3, and a(n) <= n (ln n)^6 for ln n >= 73.5, as well as the elementary form a(n) <= n 2^(4 ln n / ln ln n) for every n >= 3. The method is a fixed-time iteration: the anchor a(n-2) of a large term determines the term, the primes of the anchor are forced to have many used multiples in a short window below the term, and a Bonferroni count shows that such heavy primes are too few to supply all the anchors. The coprimality input is a self-contained explicit form of Brun's sieve. The explicit constants are computer-assisted: the first 10^8 terms, and a finite list of explicit inequalities checked on cells of ln n in [ln 10^8, 10^40]; beyond ln n = 10^40 the proof is by hand. OEIS Conjecture 7, a(n) <= (pi/2) n ln n, remains open. Manuscript; not submitted to a journal. The results were developed with an AI system (Anthropic Claude) and checked by independent AI referee agents; no human peer review has taken place. A continuation, The Yellowstone permutation, II (doi:10.5281/zenodo.23449375), proves the asymptotic bound a(n) <= (e^gamma/2 + o(1)) n ln n lnlnln n by a different method, and reduces OEIS Conjecture 7 for large n to counting hypotheses. The theorems and constants of this manuscript are unchanged.
ER -