MINIMAL LENGTH OF FIXED DEGREE S-RICH CHAINS

Abstract

We introduce and study 𝕊-rich fixed-degree addition chains of a fixed index n>1: increasing sequences of positive integers beginning at $1$ in which every term is the sum of at most d earlier terms and which contain all elements of the set 𝕊∩ [1,n] as targets. Our main contribution is a simple constructive upper bound for the minimal length ℓ_n^d(𝕊) of such a chain. Writing the ordered elements of 𝕊 ∩ [1,n] as z₁≤ z₂≤ ⋯ and letting ν_d(·) denote the sum of base-d digits, we show ℓ_n^d(𝕊)≤ ⌊(log n)/(log d) ⌋+ ⌈ ν_d(z₁)/(d−1) ⌉+∑ _i=2^|𝕊_n| ⌈ (ν_d(z_i−z_i−1))/(d−1) ⌉. a bound that generalizes the standard base-expansion construction for single targets and mirrors the digit-sum phenomenon appearing in known lower bounds. The proof is constructive and yields a straightforward algorithm for chain construction; we record corollaries for prime-rich and square-free sets, give illustrative examples, and discuss tightness, and natural open problems about optimal multi-target precomputation.

BOUNDS FOR MINIMAL LENGTH OF FIXED DEGREE CHAINS
Theophilus Agama
HAL20 Sep 2026PreprintCC BY-ND 4.0Full textGeneral mathematicsHAL
COUNTING FIXED DEGREE d ≥ 2 ADDITION CHAINS
Theophilus Agama
HAL20 Sep 2026PreprintCC BY-ND 4.0Full textGeneral mathematicsHAL
On the distribution of the minimal length of addition chains
Jean-Marie De Koninck, Nicolas Doyon, William Verreault
arXiv23 Sep 2026PreprintCC BY 4.0Full textAlgebra & number theory Combinatorics & discrete mathematicsarXiv
Examples of absolutely minimal polyhedral chains in maximum norm spaces
Roger Züst
arXiv21 Oct 2026PreprintarXiv licenceFull textGeometry & topologyarXiv
On the quadratic length of plane Cremona maps of degree 4
Alberto Calabri, Nguyen Thi Ngoc Giao
arXiv30 Sep 2026PreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeX RIS

BibTeX

@misc{agama2026minimal,
  title = {{MINIMAL LENGTH OF FIXED DEGREE S-RICH CHAINS}},
  author = {Theophilus Agama},
  howpublished = {HAL},
  year = {2026},
  month = sep,
  url = {https://hal.science/hal-05756220v1},
  note = {CC BY-ND 4.0},
}

RIS

TY  - UNPB
TI  - MINIMAL LENGTH OF FIXED DEGREE S-RICH CHAINS
AU  - Theophilus Agama
PY  - 2026
DA  - 2026/09/20
PB  - HAL
UR  - https://hal.science/hal-05756220v1
AB  - We introduce and study 𝕊-rich fixed-degree addition chains of a fixed index n>1: increasing sequences of positive integers beginning at $1$ in which every term is the sum of at most d earlier terms and which contain all elements of the set 𝕊∩ [1,n] as targets. Our main contribution is a simple constructive upper bound for the minimal length ℓ_n^d(𝕊) of such a chain. Writing the ordered elements of 𝕊 ∩ [1,n] as z_1≤ z_2≤ ⋯ and letting ν_d(·) denote the sum of base-d digits, we show ℓ_n^d(𝕊)≤ ⌊(log n)/(log d) ⌋+ ⌈ ν_d(z_1)/(d−1) ⌉+∑ _i=2^|𝕊_n| ⌈ (ν_d(z_i−z_i−1))/(d−1) ⌉. a bound that generalizes the standard base-expansion construction for single targets and mirrors the digit-sum phenomenon appearing in known lower bounds. The proof is constructive and yields a straightforward algorithm for chain construction; we record corollaries for prime-rich and square-free sets, give illustrative examples, and discuss tightness, and natural open problems about optimal multi-target precomputation.
ER  -

Abstract

Related

Cite