# A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond N4/3

arXiv: https://arxiv.org/abs/2609.29881 · HTML: https://mlsanity.com/paper/2609.29881/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 0 of its 19 references that are in the map.
- First posted on arXiv 24 Sep 2026.

## Abstract (arXiv)

Choosing Shellsort gaps is a well-known open problem. For over sixty years, successful sequences have relied on human-designed formulas, numerical searches, or number-theoretic constructions. Although stronger general bounds exist for dense or mainly theoretical families, the worst-case upper bound for a short, sparse, and practically competitive construction has not advanced beyond N4/3 for decades. We ask whether the sequence itself can instead be learned from execution. We present an RL-driven, self-supervised system that searches over executable gap generators. Every proposal is valid by construction, and executed candidates return exact comparison and move counts; no classical sequence is used as a target. Across five independent searches, the system discovers a common rational-geometric family. A second self-supervised stage tunes only a finite prefix, producing the practical sequence 1,3,8,20,47,116,300,585,1416,3303,ldots. Once frozen, it obtains the lowest equal-task average operation count among seven classical baselines on 25 large tasks with 107<N≤ 108. We complete the learned tail without changing its practical behavior: only beyond 101000, a zero-density set of unit companions hs+1 removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: Omega(N1.024296451657ldots) ≤ T(N) ≤ O(N1.024296451657ldotsoperatornamepolylog N). The lower bound follows from Zang's recent theorem for rational-geometric sequences; our contribution is the matching upper bound. Thus one exact sequence connects self-supervised discovery, large-scale practical performance, and a substantial step below the classical N4/3 bound for sparse practical Shellsort sequences.