A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$

Bo Liu

cs.CCSep 24, 2026

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$

Authors: Bo Liu

Organizations: The Chinese University of Hong Kong, Shenzhen

Abstract

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 $N^{4/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 $10^7<N\leq 10^8$ . We complete the learned tail without changing its practical behavior: only beyond $10^{1000}$ , a zero-density set of unit companions $h_s+1$ removes the remaining congruence barriers. The resulting sparse sequence has matching polynomial upper and lower exponents, up to polylogarithmic factors: $Ω(N^{1.024296451657\ldots}) \leq T(N) \leq O(N^{1.024296451657\ldots}\operatorname{polylog} 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 $N^{4/3}$ bound for sparse practical Shellsort sequences.

Figures & tables

Phase	Metric	Result
Search	independent runs	$5/5$ completed $120$ rounds
Search	distinct executed behaviors	$40{,}647$
Learning	replay-buffer capacity reached	$200{,}000$ per run
Learning	best-objective improvement	$3.09$ – $8.58\%$ per run
Exploration	first round of run winner	$13$ – $119$
Discovery	common learned family	$5/5$ rounded-geometric

Table 1: Self-supervised discovery results. Search and tuning use measured execution feedback, with deterministic censoring above the stated budget; Validation and Extrapolation are independent panels.

Sequence	Comparisons	Moves	Total	Reversed total
Ours	$1.1125$	$0.7721$	$1.8907$	$1.2706$
Tokuda	$1.1205$ $\downarrow$ $0.710\%$	$0.7663$ $\uparrow$ $0.764\%$	$1.8922$ $\downarrow$ $0.079\%$	$1.3352$ $\downarrow$ $4.843\%$
Ciura	$1.1138$ $\downarrow$ $0.116\%$	$0.7733$ $\downarrow$ $0.146\%$	$1.8923$ $\downarrow$ $0.086\%$	$1.3234$ $\downarrow$ $3.995\%$
Sedgewick	$1.1576$ $\downarrow$ $3.896\%$	$0.7590$ $\uparrow$ $1.738\%$	$1.9252$ $\downarrow$ $1.793\%$	$1.2865$ $\downarrow$ $1.239\%$
Hibbard	$2.6445$ $\downarrow$ $57.930\%$	$2.1020$ $\downarrow$ $63.267\%$	$4.7848$ $\downarrow$ $60.486\%$	$1.3775$ $\downarrow$ $7.762\%$
Knuth	$2.6698$ $\downarrow$ $58.328\%$	$2.3866$ $\downarrow$ $67.647\%$	$5.0674$ $\downarrow$ $62.690\%$	$1.2447$ $\uparrow$ $2.076\%$

Table 2: Broad Test on 25 tasks with

10^{7}<N\leq 10^{8}

. Raw entries are equal-task geometric-mean operation counts in billions. The adjacent arrow is the change from that row to ours:

\downarrow

fewer ;

\uparrow

more .

Explore similar work

May 18, 2026cs.LG

RL4RLA: Teaching ML to Discover Randomized Linear Algebra Algorithms Through Curriculum Design and Graph-Based Search

Randomized linear algebra (RLA) algorithms are a modern class of numerical linear algebra techniques that play an essential role in scientific computing and machine learning, with broad and growing adoption. However, their discovery remains mostly a manual process that requires deep expert knowledge and inspiration. While Reinforcement Learning (RL) offers a pathway to automation, standard approaches struggle with sparse reward landscapes and vast search spaces inherent to high-performing RLA algorithms. In this paper, we present RL4RLA, a general RL framework that automates the discovery of interpretable, symbolic RLA algorithms. Unlike black-box approaches, our method builds explicit algorithms from basic linear algebra primitives, ensuring verifiable and implementable representations. To enable efficient discovery, we introduce: (1) a numerical curriculum that progressively increments problem difficulty to encode inductive bias specific to the RLA domain; (2) Monte Carlo Graph Search, which optimizes exploration by identifying and merging equivalent partial algorithms. We demonstrate that RL4RLA rediscovers state-of-the-art methods, including sketch-and-precondition solvers, Randomized Kaczmarz, and Newton Sketch, and can be targeted to produce algorithms optimized for specific trade-offs between accuracy, speed, and stability. Code is available at https://github.com/Tim-Xiong/RL4RLA.

Jinglong Xiong, Xiaotian Liu, Ruoxin Wang +4

Pratt School of Engineering, Duke University, Durham, NC, USA · Department of Computer Science, Dartmouth College, Hanover, NH, USA.

Solver Iterations Low-Rank Structure Search Algorithms Offline Reinforcement Learning Riemannian Optimization Curriculum

Ask PDF

Jun 17, 2026cs.LG

Prioritizing Search Space Regions in the Low Autocorrelation Binary Sequences Problem

Low autocorrelation binary sequences problem (LABS) is a hard combinatorial optimization challenge with important applications in communications, signal processing, and satellite navigation. This paper proposes a hybrid search framework that combines Thompson sampling with parallel self-avoiding walks to adaptively allocate computational effort across restriction classes of the LABS search space. By modeling partitions as arms in a multi-armed bandit setting, the proposed method dynamically shifts search resources toward partitions that empirically produce higher merit factors while maintaining exploration of less-sampled regions. The approach is further accelerated through GPU-parallel execution, shared posterior updates, efficient neighborhood evaluation, and a Bloom filter for cycle prevention. In addition, we use a two-stage optimization strategy that first searches constrained partitioned skew-symmetric spaces and then refines the best candidates in the unrestricted space. Experiments on long binary sequences show that the proposed method improves the previously best-known results for 35 sequence lengths in the range

450 \le L \le 527

and for

L=573

. In particular, we report a new longest sequence with merit factor exceeding

8.0

, obtained for

L=451

. The results also show that Thompson sampling effectively prioritizes partitions with better observed performance, confirming the value of online, data-driven resource allocation in LABS optimization. Overall, the proposed framework provides a scalable and effective strategy for high-performance merit factor maximization.

Blaž Pšeničnik, Borko Bošković, Jan Popić +1

Computer Architecture and Languages Laboratory Faculty of Electrical Engineering and Computer Science University of Maribor · Computer Architecture and Languages LaboratoryJun Faculty of Electrical Engineering and Computer Science University of Maribor · Computer Architecture and Languages Laboratory Faculty of Electrical Engineering and Computer Science University of Maribor[cs.LG]

Thompson Sampling Autocorrelations Bits

Ask PDF

Jun 11, 2026cs.CC

The Program Is Still There: A Conservation Law for Program Discovery

Finding the shortest program that generates a sequence is uncomputable, and for six decades that fact has been mistaken for a wall around finding any generating program. It is not a wall but a price, and this paper measures it. For every algorithm that learns about a candidate program only through its score, a class spanning Levin search, evolutionary methods, simulated annealing, and the cross-entropy method, we define the coupling width of a search problem and prove an unconditional worst-case lower bound, exponential in that width with base one less than the domain size. From it follows a conservation law: structural knowledge injected into a search trades one for one against the search it removes, and their sum can never fall below the length of the program sought. Levin's 1973 upper bound and the lower bound proved here are the two ends of one conserved quantity, closing on each other as the instruction set grows. The only escape is to read a candidate's structure rather than its score, and its price, which we prove for generic targets, is incompleteness. A deterministic engine built on this theory recovers a generating program, certified by compressing its data and predicting an unseen continuation, for 2,383 of 3,914 sequences across four independent populations, including 244 of the 256 elementary cellular automata, with measured discovery cost rising along program length more than an order of magnitude inside the score-oracle worst case.

Jorge Miguel Silva

Institute of Electronics and Informatics Engineering of Aveiro (IEETA) and Department of Electronics, Telecommunications and Informatics (DETI), University of Aveiro, 3810-193 Aveiro, Portugal

Search Algorithms Worst-Case Discovery

Ask PDF