betaFeedback

WorksMathematics

Small-LCM Distinct Covering Systems via Segmented Local Search

Abstract

We construct distinct covering systems with minimum moduli 8, 9, 10, 11 and least common multiples 20160, 75600, 302400, 3326400, respectively, and conjecture that these values are minimal. For minimum modulus 8, the exclusion computations leave only 10080 and 15120 unresolved below our construction. The constructions use segmented local search: moduli are introduced in increasing blocks, followed by joint reoptimization of selected blocks. We give complete residue lists and an independent integer-arithmetic verifier. Two computational studies, comprising 180 initial runs and 130 follow-up runs, compare initialization orders, revisit rules and seed-bank capacities under fixed scan limits.

Introduction

Covering systems were introduced by Erdős in 1950 [1]. For their history and subsequent developments, see [2, 5]. One basic question concerns the size of the minimum modulus in a distinct covering system. Hough proved that this modulus is bounded above by an absolute constant [3].

A related problem prescribes the minimum modulus and asks for the smallest possible least common multiple. For m≥2m \ge2, let Lmin⁡(m)L_{\min}(m) denote the minimum LCM among distinct covering systems with minimum modulus mm, with Lmin⁡(m)=∞L_{\min}(m) = \infty if no such system exists.

Several small cases are settled. We have Lmin⁡(2)=12L_{\min}(2) = 12; Dalton and Trifonov proved Lmin⁡(3)=120L_{\min}(3) = 120 and Lmin⁡(4)=360L_{\min}(4) = 360 [4 Theorem 5]. Klein established Lmin⁡(5)=1440L_{\min}(5) = 1440 and Lmin⁡(6)=5040L_{\min}(6) = 5040, and gave a covering with minimum modulus 7 and least common multiple 15120 [6 Theorems 3–5]. In previous joint work, my coauthor and I proved that Lmin⁡(7)=10080L_{\min}(7) = 10080 [7].

We give explicit upper bounds for the next four minimum moduli.

Theorem 1. There exist distinct covering systems with minimum moduli 8, 9, 10, 11 and least common multiples 20160, 75600, 302400, 3326400, respectively. Consequently,

Lmin⁡(8)≤20160,Lmin⁡(9)≤75600,Lmin⁡(10)≤302400,Lmin⁡(11)≤3326400.L_{\min}(8) \le20160,\qquad L_{\min}(9) \le75600,\qquad L_{\min}(10) \le302400,\qquad L_{\min}(11) \le3326400.

Proof. For each list in Appendix E, the verifier checks that the moduli are distinct, their minimum and LCM have the stated values, and every integer in 0,…,L−10,\ldots,L-1 is covered. Periodicity then gives coverage of Z\mathbb{Z}.

We conjecture that all four bounds are sharp.

Conjecture 1.

Lmin⁡(8)=20160,Lmin⁡(9)=75600,Lmin⁡(10)=302400,Lmin⁡(11)=3326400.L_{\min}(8) = 20160,\qquad L_{\min}(9) = 75600,\qquad L_{\min}(10) = 302400,\qquad L_{\min}(11) = 3326400.

Theorem 1 proves only the upper bounds. The conjecture requires excluding every smaller candidate LCM; unsuccessful heuristic searches do not provide such exclusions.

Krukenberg’s constructions have L=2532527=50400L = 2^{5}3^{2}5^{2}7 = 50400 for m=8m = 8 and L=2533527=151200L = 2^{5}3^{3}5^{2}7 = 151200 for m=9m = 9, as recorded by Dalton and Trifonov [4 p. 3]. Bosma’s randomized greedy search gives the comparison periods in Table 1. Bickel et al. report 997920 and 21621600 for m=10,11m = 10, 11 [9 pp. 21, 23–25], but both lists use modulus 32 twice. Expanding a repeated class by their “2 trick” introduces modulus 64 [9 Corollary 4]. Since 64 divides neither listed value, neither is the LCM of the expanded distinct system.

mmOur LCMBosma’s greedy construction [8]Smallest prior LCM located (source)
8201606048050400 (Krukenberg; [4 p. 3])
975600151200151200 (Krukenberg; [4 p. 3])
1030240016632001663200 (Bosma [8 p. 5])
113326400——

Table 1. Our LCMs and earlier constructions. The last column gives the smallest earlier LCM located in the cited literature, excluding the author’s work, as of November 1, 2026. It is not an exhaustive record claim; a dash denotes an unresolved comparison.

Integer programming has been used for covering-number tests [10 Appendix B] and maximum coverage [11 Section 6]. Our construction search introduces increasing blocks and joint revisits, using iterated local search [12] and ruin–recreate perturbations [13]. The residue lists establish the bounds independently of these procedures.

Preliminaries and Verification

Definition 1. A covering system is a finite collection {ai(modmi):1≤i≤n}\{a_i \pmod{m_i} : 1 \le i \le n\}, with mi≥2m_i \ge2 and 0≤ai<mi0 \le a_i < m_i, such that

⋃i=1n{x∈Z:x≡ai(modmi)}=Z.\bigcup_{i=1}^{n}\{x \in\mathbb{Z}:x \equiv a_i \pmod{m_i}\}=\mathbb{Z}.

The system is distinct if its moduli are pairwise distinct. After ordering them as m1<⋯<mnm_1 < \cdots< m_n, we call m1m_1 its minimum modulus and write L=lcm⁡(m1,…,mn)L = \operatorname{lcm}(m_1,\ldots,m_n).

Since every modulus divides LL, the union of the classes is LL-periodic. Hence coverage of Z\mathbb{Z} is equivalent to coverage of 0,…,L−10,\ldots,L-1. The verifier checks the moduli, residues, minimum and actual LCM, then marks a,a+d,a+2d,…<La, a+d, a+2d,\ldots< L for each pair (a,d)(a,d). No point remains unmarked in any of the four lists. Appendix § 13 gives the verification command; the program uses only integer arithmetic.

The Search Formulation

The modulus set

Let D={d1,…,dk}D = \{d_1,\ldots,d_k\} be any nonempty finite set of distinct integers at least 2, and put

m=min⁡D,L=lcm⁡(d1,…,dk).m = \min D,\qquad L = \operatorname{lcm}(d_1,\ldots,d_k).

The set DD is fixed throughout the search; only the residues are changed. Every class has period dividing LL, so it is enough to check the integers 0,…,L−10,\ldots,L-1. For every d∈Dd \in D choose one residue ad∈Z/dZa_d \in\mathbb{Z}/d\mathbb{Z}, and write

C(d,ad):={x∈Z/LZ:x≡ad(modd)}.C(d,a_d) := \{x \in\mathbb{Z}/L\mathbb{Z}:x \equiv a_d \pmod d\}.

The maximum-coverage objective, also used in [11 Section 6], is

FD(a):=∣⋃d∈DC(d,ad)∣.(1)F_D(a) := \left\lvert\bigcup_{d\in D} C(d,a_d) \right\rvert. \tag*{(1)}

If FD(a)=LF_D(a)=L, the selected classes cover all of Z\mathbb{Z}. Otherwise, the output is a partial covering, together with its uncovered set

HD(a)={x∈{0,…,L−1}:x≢ad(modd) for every d∈D}.H_D(a)=\{x\in\{0,\ldots,L-1\}:x\not\equiv a_d\pmod d\text{ for every }d\in D\}.

Thus ∣HD(a)∣=L−FD(a)\lvert H_D(a)\rvert=L-F_D(a) counts individual uncovered residues, also called gaps, within one period.

For the least-common-multiple bounds studied here, we instead begin with a minimum modulus mm and a candidate LL divisible by mm, then supply

D=Dm(L):={d:d∣L, d≥m}.D=D_m(L):=\{d:d\mid L,\ d\ge m\}.

to the same search. Using every allowed divisor does not restrict existence: a covering using a subset can be extended by assigning arbitrary residues to the unused divisors. Since mm and LL are included, the resulting system has minimum modulus mm and least common multiple LL. The experiments below use this full-divisor choice of DD.

For m=8m=8, the separate exclusion computations below reduce the smaller candidate LCMs to two unresolved values.

Candidate reduction for m1=8m_1=8

We apply the reciprocal-sum and partial-sum filters from our previous joint work [7 Sections 4–6]. Since 8∣L8\mid L and a construction at L=20160L=20160 is available, it suffices to consider

R8={L∈N:8∣L, 8≤L≤20160}.\mathcal{R}_8=\{L\in\mathbb{N}:8\mid L,\ 8\le L\le20160\}.

Exact enumeration of the necessary condition ∑d∈D8(L)1/d≥1\sum_{d\in D_8(L)}1/d\ge1 leaves 53 candidates. The preliminary exclusions reduce this set to

C8={10080,12600,15120,15840,16800,17640,18480,18720,19800,20160}.\mathcal{C}_8=\{10080,12600,15120,15840,16800,17640, 18480,18720,19800,20160\}.

The preliminary exclusions use the earlier lower bound [7] and partial-sum tests. The supplement gives the elementary lower-range reductions, including 7920→50407920\to5040, and the computation records. Table 2 records the subsequent reductions. Depth kk means that the filter uses the first kk increasing divisors in D8(L)D_8(L).

DepthExcluded LCMsCandidates remaining
2316800, 176408
2518480, 18720, 198005
3012600, 158403

Table 2. Successive exclusions from C8\mathcal{C}_8 for m1=8m_1=8. The last column counts all remaining candidates with L≤20160L\le20160, including the constructed value 20160.

Thus the computations leave

Lmin⁡(8)∈{10080,15120,20160}.L_{\min}(8)\in\{10080,15120,20160\}.

The value 20160 is realized by our construction. For 10080 and 15120, neither a covering nor an exclusion has been established. Consequently, proving the m=8m=8 case of Conjecture 1 reduces to excluding these two values. The exclusion results use Gurobi’s reported bounds and infeasibility decisions; they are distinct from the independently verified covering certificates.

Coordinate updates

Maintain the coverage multiplicity

c(x):=#{d∈D:x≡ad(modd)}c(x) := \#\{d \in D : x \equiv a_d \pmod d\}

for every x∈Z/LZx \in\mathbb{Z}/L\mathbb{Z}. Then

FD(a)=#{x:c(x)>0},UD(a)=L−FD(a)=#{x:c(x)=0}.F_D(a) = \#\{x : c(x) > 0\}, \qquad U_D(a) = L - F_D(a) = \#\{x : c(x) = 0\}.

To update the residue associated with a single modulus dd, first remove its old class and denote the resulting count by c−d(x)c_{-d}(x). The number of newly covered points obtained by assigning residue rr is

gd(r)=#{x:c−d(x)=0, x≡r(modd)}.(2)g_d(r) = \#\{x : c_{-d}(x) = 0,\ x \equiv r \pmod d\}. \tag*{(2)}

We choose a residue maximizing gd(r)g_d(r), breaking ties uniformly at random. If a′a' differs from aa only at dd, with new residue rr, then

FD(a′)−FD(a)=gd(r)−gd(ad).F_D(a') - F_D(a) = g_d(r) - g_d(a_d).

Thus an exact best response cannot reduce coverage. The counts are updated along the removed and inserted arithmetic progressions.

The count array uses O(L)O(L) memory. Computing all gains for one modulus takes O(L)O(L) time; adding or removing its class takes O(L/d)O(L/d) time. A sweep through bb active moduli costs O(bL)O(bL). With TT workers and KK stored uncovered sets, memory use is O((T+K)L)O((T+K)L), excluding temporary candidate pools. Segmentation reduces the active coordinate count but retains the dependence on LL.

Translation and CRT normalization

Global translation preserves coverage: adding the same integer tt to every residue maps a covering to an equivalent covering. More strongly, let P⊆DP \subseteq D be a set of pairwise-coprime moduli. The Chinese remainder theorem gives a translation tt satisfying

ap+t≡−1(modp)(p∈P).a_p + t \equiv-1 \pmod p \qquad(p \in P).

Consequently, one may fix without loss of generality

ap=p−1(p∈P).(3)a_p = p - 1 \qquad(p \in P). \tag*{(3)}

These fixed classes form the CRT prefix. For example, at L=20160L = 20160 we fix residues 8,34,638, 34, 63 modulo 9,35,649, 35, 64. The implementation selects a pairwise-coprime subset among the first hh increasing moduli, maximizing (product, sum, cardinality) lexicographically by dynamic programming on prime-support masks. Appendix § 11 lists the prefixes. Their product need not equal LL; residual translation symmetries may remain.

The Segmented Search

Insertion and freezing

After removing the CRT prefix, order the free moduli as

q1<q2<⋯<qN.q_1 < q_2 < \cdots< q_N.

For a target block length bb, partition them into consecutive blocks

B1,B2,…,Bs,∣Bj∣=b (j<s),s=⌈N/b⌉,B_1, B_2, \ldots, B_s, \qquad|B_j| = b\ (j < s), \qquad s = \lceil N/b \rceil,

with the last block containing the remainder. Alternatively, prescribe a block count ss and put ⌈N/s⌉\lceil N/s\rceil moduli in each of the first N mod sN \bmod s blocks and ⌊N/s⌋\lfloor N/s\rfloor in the others. At insertion stage jj, only Bj\mathcal{B}_j is optimized; the prefix and earlier blocks are fixed, and later blocks are absent. At the end of its trajectory budget the best assignment is retained. Scheduled revisits may then change completed blocks before the next insertion.

If Aj−1A_{j-1} contains the CRT prefix and the classes fixed in the first j−1j-1 blocks, the stage-jj subproblem is

max⁡ad:d∈Bj∣⋃(d,ad)∈Aj−1C(d,ad)∪⋃d∈BjC(d,ad)∣.(4)\max_{a_d:d\in\mathcal{B}_j}\left|\bigcup_{(d,a_d)\in A_{j-1}}\mathcal{C}(d,a_d)\cup\bigcup_{d\in\mathcal{B}_j}\mathcal{C}(d,a_d)\right|. \tag*{(4)}

Each stage has fewer active coordinates than the full problem, but is still solved heuristically. Early blocks cannot anticipate every later choice. Revisits allow their residues to change in the presence of classes added subsequently.

Searching within a block

A trajectory combines randomized greedy initialization, bounded coordinate search and ruin–recreate perturbations. Initialization samples residues whose gain is within max⁡{1,⌊L/(25d)⌋}\max\{1,\lfloor L/(25d)\rfloor\} of the maximum. Coordinate search uses exact best responses in shuffled order, with an additional increasing-order sweep after a no-gain round. Perturbations remove and rebuild selected active classes; bounded worsening moves are allowed while a separate historical best is retained. Independent trajectories compete within each insertion budget.

Appendix § 8.§ 1 gives the stopping, acceptance and perturbation rules. Bounded sweeps do not certify coordinate local optimality: a tied update can enable an improvement at an earlier coordinate. Complete coverage is checked independently of these stopping rules.

Joint Reoptimization

Joint changes of residues

The usefulness of a revisit depends on the positions of the uncovered points, as well as their number. Suppose two gaps remain and the only available modulus is dd. One class modulo dd can cover both gaps precisely when they are congruent modulo dd. Changing an earlier class may move the gaps into a compatible position, even if their number stays the same. A revisit lets the search make such coordinated changes.

A revisit selects a window W⊂{1,…,s}W\subset\{1,\ldots,s\}, unfreezes the blocks in WW, leaves all other blocks fixed, and restarts perturbed coordinate search on

⋃j∈WBj.\bigcup_{j\in W}\mathcal{B}_j.

We use three scales.

Adjacent-block revisits. Reoptimize Bj∪Bj+1\mathcal{B}_j\cup\mathcal{B}_{j+1} to repair artificial block boundaries and permit cross-boundary exchanges.

Subset revisits. Reoptimize pairs, triples, or larger selections of nonadjacent blocks. These windows address long-range interactions while controlling the number of free coordinates.

Global revisits. Unfreeze every free modulus while retaining only the lossless CRT prefix. This activates the largest coordinate set. The historical runs initialize it from a saved assignment; § 6 compares cold-start procedures.

Perturbation schedules and multiple seed assignments

Seeded revisits start from a saved assignment. Appendix § 8.§ 2 gives their trajectory rules and ruin-size schedules.

For the m=9m = 9 completion phase, a seed bank retains multiple assignments. An epoch generates trajectories from the current bank, pools their best states and endpoints with the old bank, and selects the next bank. We use “seed assignment” for a saved assignment and “random seed” for an integer initializing a pseudorandom generator.

The bank selects assignments by coverage and by distances between their residue vectors and uncovered sets. Its trajectories allow bounded worsening moves and retain a historical best. Appendix § 11.§ 1 gives the exact selection thresholds, acceptance probabilities and schedules. The follow-up in § 6.3 changes parent sampling and schedule cycling while holding these trajectory rules fixed within its capacity comparison.

Computational Experiments

The initial experiment

The initial study uses six configurations and ten random seeds on each of (m,L)=(8,20160),(8,30240),(9,75600)(m,L) = (8, 20160), (8, 30240), (9, 75600), giving 180 runs. Instances, random seeds and scan limits were fixed before the batch. Every run starts from the CRT prefix, selected from the first 25 moduli, without an imported assignment. Free-block length 25 gives partitions 25+25+2425 + 25 + 24, 25+25+25+1125 + 25 + 25 + 11, and 25+25+25+25+925 + 25 + 25 + 25 + 9.

Each run has a scan limit Q=240000Q = 240000, an upper bound on the number of best-response gain scans. One scan evaluates the gain vector over all LL points for one modulus; greedy construction and ruin–recreate updates both consume scans. The limit matches full-period scans within an instance, not total operations or elapsed time. The configurations allocate this allowance as follows:

Whole. Use the entire allowance for repeated construction trajectories with all free moduli active.

Segmented. Split the entire allowance equally across insertion blocks, with no revisit.

Adjacent. Use half for insertions and half, divided equally, for reverse and forward passes over adjacent block pairs. Their revisit schedules alternate large-to-small and mixed perturbations.

Global. Use half for insertions and half for three full-set revisit phases, with medium, large-to-small and mixed perturbations in that order.

Bank-1 and Bank-20. Use half for insertions and half, divided equally, for five bank epochs. Both use the same bank trajectory kernel and selection thresholds, with capacity K=1K = 1 or 2020. Here KK is the maximum number of saved seed assignments retained in the bank, not the number actually sampled.

The four half-insertion configurations share insertion random seeds and scan limits. Ordinary revisits restart from a saved assignment; bank trajectories use selected parents. Only the Bank-1/Bank-20 pair isolates capacity; Global/Bank-20 also changes the acceptance kernel.

Runs use one worker, 32 perturbation steps and at most 80 coordinate rounds, stopping at the first covering or the scan limit. All final assignments passed independent checks. Execution details and timing are in Appendix § 14.§ 1.

Initial results

For each row, let NN be the number of runs and a(r)a^{(r)} the complete assignment returned by run rr. We report

Ur=∣HDm(L)(a(r))∣=L−FDm(L)(a(r)),s=#{r:Ur=0}.U_r = \lvert H_{D_{m}(L)}(a^{(r)}) \rvert= L - F_{D_{m}(L)}(a^{(r)}), \qquad s = \#\{r : U_r = 0\}.

The entry s/Ns/N counts successful runs out of all NN runs. “Uncovered residues” gives the median of U1,…,UNU_1,\ldots,U_N, followed by their minimum and maximum in brackets, including successful runs with Ur=0U_r = 0. The brackets are ranges, not confidence intervals; for even NN, the median averages the two central values.

For a successful run, let SrS_r be its cumulative gain-scan count when a covering is first found, including initialization and all preceding stages. “Scans to success” reports median⁡r=0Sr/103\operatorname{median}_{r=0} S_r/10^3, rounded to one decimal place; a dash means s=0s=0. This conditional median excludes failed runs. Actual scans may be fewer than the per-run cap QQ because of early success. These conventions apply to all experimental tables; CPU timings are reported separately in Table 16.

MethodSuccesses s/Ns/NUncovered residues median [min, max]Completed trajectoriesCPU time (s)CPU to success (s)
Whole0/10221.5 [122, 362]301.756—
Segmented0/1060 [12, 102]991.978—
Adjacent0/1032.5 [12, 82]65.51.684—
Global3/1033 [0, 79]571.6991.018
Bank-12/1021 [0, 87]541.6971.187
Bank-202/1029.5 [0, 91]541.6901.208
m=8m = 8, L=30240L = 30240
Whole0/10127.5 [85, 302]252.394—
Segmented8/100 [0, 50]742.1642.108
Adjacent7/100 [0, 96]491.2671.068
Global7/100 [0, 57]491.2651.069
Bank-17/100 [0, 93]491.2681.068
Bank-208/100 [0, 93]491.2681.102
m=9m = 9, L=75600L = 75600
Whole0/101096.5 [633, 1881]206.203—
Segmented7/100 [0, 345]836.1166.087
Adjacent6/100 [0, 423]533.6163.052
Global6/100 [0, 382]51.53.4223.042
Bank-16/100 [0, 397]51.53.4473.046
Bank-206/100 [0, 397]51.53.4203.042

Table 16. Initial-study timing: N=10N = 10 runs per row, each with scan limit Q=240000Q = 240000. Uncovered-residue summaries, completed-trajectory medians and process CPU-time medians use all ten runs. Interrupted trajectories are excluded from the completed counts. CPU to success is the median process CPU time at first coverage over successful runs only, with initialization included; a dash denotes no success. All times are in seconds.

MethodSuccesses s/Ns/NUncovered residues median [min, max]Scans to success median (10310^3)
m=8m=8, L=20160L=20160
Whole0/10221.5 [122, 362]—
Segmented0/1060 [12, 102]—
Adjacent0/1032.5 [12, 82]—
Global3/1033 [0, 79]129.1
Bank-12/1021 [0, 87]153.2
Bank-202/1029.5 [0, 91]153.2
m=8m=8, L=30240L=30240
Whole0/10127.5 [85, 302]—
Segmented8/100 [0, 50]180.0
Adjacent7/100 [0, 96]90.0
Global7/100 [0, 57]90.0
Bank-17/100 [0, 93]90.0
Bank-208/100 [0, 93]90.0
m=9m=9, L=75600L=75600
Whole0/101096.5 [633, 1881]—
Segmented7/100 [0, 345]192.0
Adjacent6/100 [0, 423]96.0
Global6/100 [0, 382]96.0
Bank-16/100 [0, 397]96.0
Bank-206/100 [0, 397]96.0

Table 3. Initial study: N=10N=10 runs per row, each with scan limit Q=240000Q=240000. Uncovered residues are counted in one period 0,…,L−10,\ldots,L-1 and summarized over all runs; scans to success are summarized over successful runs only. A dash denotes no success.

Whole finds no covering. Segmented succeeds on two instances, while Global finds three coverings at L=20160L=20160. At L=30240L=30240 and 7560075600, five successes in each half-insertion configuration occur before revisits begin. Bank-20 has no consistent advantage over Bank-1. These results compare complete procedures: segmentation changes initialization order, active coordinates and work allocation together. The follow-up separates initialization order and tests revised bank sampling.

The follow-up experiment

The original bank restarts parent and schedule indices each epoch. Across its Bank-20 runs, only parent positions 1, 2 and two of the three schedules receive work (Appendix § 14.§ 2). We therefore designed a separate follow-up after inspecting the initial results, fixing its matrix and random seeds before execution:

Initialization order: 30 runs. On the three original instances, Ordered-Whole changes only greedy initialization from shuffled to increasing order, using the same ten random seeds and Q=240000Q=240000.

Bank sampling: 40 runs. On (8,20160)(8, 20160), compare K=1,20K=1,20 at Q=240000,960000Q=240000,960000, ten runs per row. Parent positions are shuffled and visited cyclically; schedule counters continue across epochs. Both capacities retain half-insertion and five-epoch allocation.

Larger periods: 60 runs. On (10,302400)(10, 302400) and (11,3326400)(11, 3326400), compare Ordered-Whole, Segmented and Global at Q=15000,60000Q = 15000, 60000, five runs per row. Since each scan costs O(L)O(L), work is compared within each period.

The machine, build flags and trajectory kernel are unchanged. All 130 final assignments passed independent coverage and accounting checks.

Follow-up results

Increasing the initial modulus order reduces the median number of uncovered residues on all three instances, but neither Whole variant finds a covering (Table 15). Thus ordering alone does not reproduce the Segmented successes.

MethodSuccesses s/Ns/NUncovered residues median [min, max]Scans to success median (10310^{3})
Whole0/10221.5 [122, 362]—
Ordered-Whole0/10151.5 [96, 206]—
Segmented0/1060 [12, 102]—
m=8m = 8, L=20160L = 20160
Whole0/10127.5 [85, 302]—
Ordered-Whole0/1087.5 [35, 142]—
Segmented8/100 [0, 50]180.0
m=9m = 9, L=75600L = 75600
Whole0/101096.5 [633, 1881]—
Ordered-Whole0/10421.5 [168, 528]—
Segmented7/100 [0, 345]192.0

Table 15. Initialization-order control: N=10N = 10 runs per row, each with scan limit Q=240000Q = 240000. Only Ordered-Whole is new; the other rows are initial-study comparators. Uncovered-residue summaries include all runs; scan medians include only successful runs. A dash denotes no success.

Table 4 shows no consistent advantage for capacity 20. All forty runs enter bank search; the larger bank reaches parent positions up to 9 at the lower scan limit and 20 at the higher one, and uses all three schedules. This removes the original sampling restriction without producing a consistent gain in this sample.

Scan limit Q/103Q/10^{3}Seed capacity KKSuccesses s/Ns/NUncovered residues median [min, max]Scans to success median (103)(10^{3})
24013/1027 [0, 82]166.0
240202/1025.5 [0, 78]149.3
96014/102.5 [0, 63]522.8
960204/104 [0, 73]522.8

Table 4. Revised bank sampling on m=8m = 8, L=20160L = 20160, N=10N = 10 per row. The scan limit QQ is per run; KK is the maximum number of retained seed assignments. Uncovered-residue summaries include all runs; scan medians include only successful runs.

In the larger-period tests (Table 14), no method succeeds at Q=15000Q = 15000, or at Q=60000Q = 60000 for m=10m = 10. At m=11m = 11, Q=60000Q = 60000, Ordered-Whole, Segmented and Global succeed in 1/5, 5/5, 2/5 runs. Both Global successes occur during insertion, so revisits rescue none of its remaining runs. These small samples do not establish a general ranking. Different total scan limits change stage allocations, so their trajectories are not nested truncations of one run.

MethodScan limit Q/103Q/10^{3}Successes s/Ns/NUncovered residues median [min, max]Scans to success median (10310^{3})
m=10m = 10, L=302400L = 302400
Ordered-Whole150/53741 [2780, 6390]—
Segmented150/5639 [561, 4917]—
Global150/51880 [576, 4745]—
Ordered-Whole600/52780 [1431, 3169]—
Segmented600/5775 [541, 1871]—
Global600/5826 [631, 1714]—
m=11m = 11, L=3326400L = 3326400
Ordered-Whole150/512765 [215, 23453]—
Segmented150/51014 [33, 4479]—
Global150/53814 [330, 4352]—
Ordered-Whole601/5712 [0, 1462]33.9
Segmented605/50 [0, 0]41.6
Global602/51228 [0, 2295]26.6

Table 14. Exploratory larger-period tests, N=5N = 5 per row. Uncovered-residue summaries include all runs; scan medians include only successful runs, with a dash for no success. The scan limit QQ is per run. Equal scan counts at different LL do not represent equal arithmetic work.

Conclusion

The four residue lists establish the upper bounds in Theorem 1. For m=8m = 8, the exclusion computations leave only L=10080L = 10080 and 1512015120 below the constructed value 20160; both remain unresolved. Matching lower bounds in Conjecture 1 are still open. The experiments support using segmented initialization on the tested instances, while the benefits of revisits and larger seed banks depend on the configuration.

Segmented Search Pseudocode

The abstract framework accepts a prescribed set DD; the recorded implementation constructs D=Dm(L)D = D_m(L). Choose the prefix before partitioning, so that D=P∪˙B1∪˙⋯∪˙BsD = P \mathbin{\dot\cup} B_1 \mathbin{\dot\cup} \cdots\mathbin{\dot\cup} B_s. An optional complete initial assignment, as used for m=9m = 9, bypasses fresh insertions and enters the revisit phase. Search budgets bound every optimization call.

Input: D, prefix-selection and partition rules, budgets,
       revisit schedules, optional complete initial assignment
L <- lcm(D)
P <- pairwise-coprime subset selected from D
fix a[p] <- p-1 for every p in P
partition D minus P into B[1..s]
initialize counts from the prefix

if a complete initial assignment is supplied:
    check its moduli, residues, and prefix; recompute counts
    elite <- initial assignment
else:
    for j <- 1,...,s:
        add B[j]; optimize it within the insertion budget
        keep the best assignment for the completed blocks
        run scheduled revisits of completed blocks
        independently recompute and save the checkpoint
        if coverage is complete:
            assign arbitrary residues to all unused moduli
            break
    elite <- the resulting complete assignment on D

if elite is not a covering and revisit budget remains:
    run configured joint revisits, retaining the historical best
if seed-bank search is enabled and elite is not a covering:
    initialize the bank from elite and any supplied complete seeds
    for each budgeted epoch:
        generate perturbed trajectories; retain best and endpoints
        select the bank by quality, deduplication, and distances
        update elite and save a recomputed checkpoint
        stop if elite is a covering
recompute elite’s coverage and uncovered set over 0,...,L-1
return elite and its uncovered set

Insertion trajectory kernel

A trajectory is one initialization followed by bounded coordinate search and a specified number of perturbation steps. The retained implementation uses the following rules.

S1. Randomized greedy initialization. Visit the active moduli in random order. For modulus dd, sample uniformly among residues with gain at least max⁡rgd(r)−δd\max_r g_d(r) - \delta_d, where

δd=max⁡{1,⌊L/(25d)⌋}.\delta_d = \max\{1, \lfloor L/(25d) \rfloor\}.

Previously unassigned moduli have no old class to remove.

S2. Coordinate search. Use exact best responses in a random coordinate order, for at most 80 rounds. After a round with no gain, try one additional sweep in increasing coordinate order; stop if that sweep also gives no gain. Tie choices remain random in both sweeps. This is a bounded heuristic stopping rule, not a certificate of coordinate local optimality: a later tied update can enable improvement at an earlier coordinate. Every exact best-response update is nevertheless nondecreasing.

S3. Ruin–recreate perturbations. For a nonempty active set, select uniformly between min⁡(2,b)\min(2,b) and min⁡(6,b)\min(6,b) coordinates, remove them, rebuild in random order using the same greedy tolerance, and repeat coordinate search. Retain a separate historical best. Accept a new current state if its score does not decrease; on every eighth step, also accept a loss of at most two points relative to the current score. On a rejected twelfth step, restore the historical best. Step counts refer to one-based perturbation indices.

Independent random initializations are attempted within each insertion budget, and the highest-scoring assignment is retained. A sweep or trajectory limit may stop before all coordinate improvements have been exhausted. A local-optimality certificate, if desired, requires checking every coordinate against the same unchanged final state; it is not needed to verify a complete covering.

Ordinary revisit schedules

Seeded revisits begin with coordinate search on the saved assignment, followed by perturbations. The ordinary revisit kernel uses the acceptance and historical-best rules of Appendix § 8.§ 1. Its large-to-small schedule linearly decreases a ruin size between specified limits, rounds to an integer, adds a uniform jitter in {−1,0,1}\{-1,0,1\}, and clips to those limits. Its mixed schedule chooses a small or large ruin range with probability 1/21/2 each and samples uniformly within the selected range. The limits and number of steps are configuration parameters, rather than consequences of the block partition.

The smallest LCM case

For completeness, the classes 00 (mod 22), 11 (mod 33), 33 (mod 44), 55 (mod 66), and 99 (mod 1212) establish Lmin⁡(2)≤12L_{\min}(2) \le12. Any smaller candidate is an even integer. For L=2,4,8,10L=2,4,8,10, the sum of 1/d1/d over divisors d≥2d \ge2 of LL is less than 1. For L=6L=6 the sum equals 1, but classes modulo 2 and 3 necessarily intersect once in a period. Even with a class modulo 6, their union has size at most 3+2−1+1=53+2-1+1=5. No smaller candidate therefore admits a distinct covering.

Exploratory Block-Length Runs

Smaller blocks use fewer coordinates in each initial stage, but create more boundaries and possible revisit windows. With ss blocks, considering every subset of sizes 2 through rr would involve

∑i=2min⁡(r,s)(si)\sum_{i=2}^{\min(r,s)} \binom{s}{i}

windows per enumeration. The recorded runs use specified adjacent or subset schedules. Selecting windows from measured compatibility with uncovered points is a possible extension, not a procedure evaluated here.

Recorded runs for m=8m=8

Table 5 lists single saved outcomes for m=8m=8, L=15120L=15120, with prefix 16, 27, 35 and 70 free moduli. The recorded insertion allowance is 1200 trajectories per worker and 18 perturbation steps, with ten workers; each scheduled revisit has 160 trajectories per worker and 18 steps. The three- to five-block runs include all pairs and triples, whereas the six-block run includes subset sizes two through six. The one- and two-block launch script enables subset refinement: only the two-block case has a subset of size at least two. These schedules entail different amounts of work despite matching per-call allowances. All six checkpoints assign all 73 allowed moduli; none is an exclusion certificate.

BlocksActual block sizesCoveredUncovered
17015019101
235 + 351502694
324 + 23 + 231504377
418 + 18 + 17 + 171502793
514 + 14 + 14 + 14 + 141505268
612 + 12 + 12 + 12 + 11 + 111502793

Table 5. Individual saved outcomes at m=8m = 8, L=15120L = 15120. These are not equal-budget estimates of block-count effects.

The five-block run has the fewest uncovered points among these saved assignments. This observation alone does not identify an optimal block length or a generally superior schedule.

Table 6 gives individual outcomes for fixed target block lengths at two other periods. Every listed L=30240L = 30240 run completed a covering; among the listed L=27720L = 27720 runs, target length 25 left the fewest points uncovered. These observations do not estimate success probabilities or sensitivity across independent repetitions.

Target lengthL=27720L = 27720L=30240L = 30240
CoveredUncoveredCoveredUncovered
1527148572302400
1727133587302400
2027147573302400
2227147573302400
2527205515302400

Table 6. Saved outcomes for fixed target lengths, with m=8m = 8. Each final assignment contains all 89 allowed moduli.

At L=20160L = 20160, a saved target-length-15 state covers 20083 points but contains only the prefix and four blocks of 15 free moduli, or 63 classes in total. The last 14 free moduli have not been inserted. It is therefore an incomplete construction state and is not compared with the complete assignment as a block-length benchmark.

Recorded Construction Paths

The following paths document successful historical searches. They are not controlled comparisons and are not needed for the certificate proofs. “After insertion” denotes the state before its subsequent revisits; “after revisits” denotes the state used for the next insertion. Final certificate restrictions need not reproduce earlier states, since revisits can change their residues. Appendix § 11 summarizes the recovered configurations.

m=8,L=20160m=8,L=20160: three blocks and a cross-block revisit

The CRT prefix is

8(mod9),34(mod35),63(mod64),8 \pmod{9}, \qquad34 \pmod{35}, \qquad63 \pmod{64},

where 9, 35, 64 are pairwise coprime and have product 20160. The remaining 74 moduli are divided into blocks of sizes 25 + 25 + 24. Table 7 distinguishes the coverage immediately after an insertion from the coverage after a revisit.

StageCoveredUncoveredDescription
CRT prefix + block 1184391721first block contains 25 smaller free moduli
Insert block 219923237block 1 frozen while block 2 is optimized
Revisit blocks 1 and 219962198jointly reopen 50 moduli; gain 39 points
Insert block 3201600final 24 moduli complete the cover

Table 7. Key stages for m=8,L=20160m = 8, L = 20160.

In this recorded path, reopening the first two blocks increases coverage by 39 points, and the following insertion completes the covering. This trace does not show that a comparable search without that revisit would fail.

m=9,L=75600m=9,L=75600: projected seeds and joint revisits

The CRT prefix is 25, 27, 56, and the 109 free moduli are partitioned as 19 + 18 + 18 + 18 + 18 + 18. This run resumes a full assignment projected from a saved L=151200L = 151200 construction. The projection retains classes whose moduli divide 75600, translates the inherited residues to agree with the target prefix, and greedily fills missing moduli. It then performs up to three sweeps on newly filled coordinates. A preserve variant leaves other inherited coordinates fixed; a relaxed variant additionally performs up to three sweeps on all free coordinates. A sweep with no gain ends either sweep loop early.

The saved projection summary records 87 inherited and 25 missing moduli and translation 0 modulo 37800. The preserve and relaxed checkpoints cover 74104 and 75077 points, respectively. The successful run starts from the relaxed checkpoint and also supplies the preserve checkpoint to the later seed bank. Thus its initialization includes information from an earlier construction. The supplementary projection_m9 directory now includes the source 151200 assignment, projection program, both target checkpoints, and a reconstructed command that reproduces both checkpoints byte for byte. This establishes the saved-data chain, not the original executable build or total upstream search cost. In contrast, the initial experiment in § 6 finds covers in seven of ten fresh Segmented runs on this instance without projection or a bank.

Two rounds of adjacent revisits bring coverage to 75173. Global revisits then give

75173⟶75558⟶75594.75173 \longrightarrow75558 \longrightarrow75594.

The bank starts with two seeds. Its target capacity is 20, reached at the end of the first epoch. The best numbers of uncovered points after epochs 1, 2, 3 are 6, 4, 0, respectively. Each epoch has a nominal allowance of 10000 trajectories, but the third stops early when a covering is found. The historical file records 30000 by multiplying the epoch index by its allowance; this is not an actual executed-trajectory count. The exact total is not recovered, and no comparison of runtime or success probability is drawn from this run.

m=10,L=302400m=10,L=302400: nine balanced blocks

The prefix is 25, 32, 63; the 156 free moduli form three blocks of 18 and six of 17. Table 8 separates insertions from the intervening adjacent revisits. In particular, insertion of block 8 leaves 101 points uncovered, its revisit reduces that number to 84, and insertion of block 9 completes the covering.

m=10m = 10, L=302400L = 302400m=11m = 11, L=3326400L = 3326400
BlockInsertionRevisitsInsertionRevisits
122822422822424739862473986
227025727319729229242922999
328873328904631143583117758
429578829592132095123210660
529894229915132565133259369
630096830099832933053294892
730188630189433085043309727
830229930231633178123318872
930240030240033226373322922
10——33257513325788
11——33263963326400

Table 8. Coverage immediately after each insertion and after its subsequent adjacent revisits. A dash denotes a stage beyond the end of the m=10m = 10 construction. The m=11m = 11 covering is already complete after the block-11 revisit.

m=11,L=3326400m=11,L=3326400: completion after block 11

The prefix is 11, 27, 32, 35. The 322 free moduli are partitioned into sixteen blocks of 18 and two of 17, so eighteen blocks are planned. After insertion of block 11, four points remain uncovered.

Reoptimizing blocks 10 and 11 then covers all four. This is the first complete covering in the saved path; block 12 does not cause completion. Blocks 12–18 are subsequently added to retain the full-divisor output with 326 classes.

Recorded Configurations

Table 9 gives partitions and completion operations. A block partition alone is not a complete run specification. The detailed rules in the text describe the retained implementation; a source snapshot and historical executable have not been tied to a verified original build. The provenance file distinguishes recorded settings from missing information.

mmLLPrefix moduliFree-block sizesCompletion operation
8201609, 35, 6425 + 25 + 24first-two-block revisit, then third insertion
97560025, 27, 5619 + 5 × 18projected seeds, global revisits, third bank epoch
1030240025, 32, 633 × 18 + 6 × 17ninth insertion, following adjacent revisits
11332640011, 27, 32, 3516 × 18 + 2 × 17revisit of blocks 10 and 11

Table 9. Partitions and completion operations of the four recorded constructions.

For m=9m = 9, the retained launch script specifies prefix depth 25, ten workers, 200 trajectories per worker for each revisit schedule, 32 perturbation steps, two reverse/forward adjacent-revisit rounds, and final global refinement. The bank capacity is 20, with a nominal 500 trajectories per target seed slot per epoch and at most four epochs. It stops after three. The base random seed is 20260814075600. The initial bank has two supplied states, so its first epoch allocates the nominal 10000 trajectories across those states rather than across twenty pre-existing seeds.

For the bank’s 109 free coordinates, trajectory indices cycle through three schedules. The medium schedule samples a ruin size uniformly from 7 to 24. The large-to-small schedule decreases from 54 to 2, with rounding and uniform jitter in {−2,−1,0,1,2}\{-2,-1,0,1,2\}, clipped to that range. The mixed schedule chooses a uniform size from 27 to 54 with probability 0.6, otherwise from 2 to 7. All use 32 perturbation steps and the bank acceptance rule in § 5. These are implementation settings, not fitted success-rate estimates.

The m=11m = 11 successful run belongs to the extended candidate queue. Its log records 200 nominal trajectories for each insertion and 50 per adjacent revisit schedule across all workers. The matching script specifies ten workers, 32 perturbation steps for insertions and revisits, prefix depth 20, and base seed 20260815110000 + 3326400. It reaches full coverage during the first trajectory reported for the block-10–11 large-to-small revisit. These local allowances do not supply total discovery cost. Hardware details and actual stopping counts are not filled from defaults of unrelated launch scripts.

Seed-bank trajectory and selection rules

The following rules define the retained bank kernel used in the historical m=9m = 9 completion and both experimental batches. Parent sampling is a separate rule: the initial batch restarts its parent and schedule indices each epoch, whereas the follow-up shuffles parent positions and carries its schedule index across epochs.

For assignments a,a′a, a' on the same free moduli, define

dR(a,a′)=#{d:ad≠ad′},dH(a,a′)=∣HD(a)△HD(a′)∣.d_R(a,a') = \#\{d : a_d \ne a'_d\}, \qquad d_H(a,a') = |H_D(a)\mathbin{\triangle}H_D(a')|.

Candidate seed assignments are ordered by decreasing coverage, then lexicographically by their uncovered sets and residue vectors. After removing duplicate residue vectors and candidates more than 15 points below the best, reject a candidate if some retained assignment satisfies both dH<8d_H < 8 and dR<12d_R < 12. Stop at the configured capacity: 20 in the historical run, and 1 or 20 in the experiments. If fewer survive, fill the remaining positions from the same quality-filtered pool of distinct vectors, irrespective of the distance thresholds.

The bank’s trajectory kernel differs from ordinary revisits. For a proposed score v<vcurv < v_{\mathrm{cur}}, it permits acceptance only if v≥vbest−12v \ge v_{\mathrm{best}} - 12, and then with probability

exp⁡((v−vcur)/θt),θt=max⁡{0.75,12(1−0.75t)}.\exp((v-v_{\mathrm{cur}})/\theta_t), \qquad\theta_t = \max\{0.75, 12(1-0.75t)\}.

where tt is fractional progress through the perturbation steps. A rejected tenth step restores the historical best. Nondecreasing moves are accepted, and the best score is stored separately. Appendix D specifies the ruin ranges used for this run.

Complete Constructions

Each entry a (d)a\ (d) denotes the residue class x≡a(modd)x \equiv a\pmod d. Entries are ordered by increasing modulus, read from left to right across each row. The four lists below preserve the full-divisor assignments produced by the searches. They contain all data needed to verify Theorem 1.

Minimum modulus 8

The least common multiple is L=20160L = 20160.

Entries are a (d)a\ (d), meaning x≡a(modd)x \equiv a\pmod d
3 (8)3\ (8)8 (9)8\ (9)6 (10)6\ (10)1 (12)1\ (12)2 (14)2\ (14)
3 (15)3\ (15)7 (16)7\ (16)2 (18)2\ (18)0 (20)0\ (20)19 (21)19\ (21)
9 (24)9\ (24)10 (28)10\ (28)12 (30)12\ (30)15 (32)15\ (32)34 (35)34\ (35)
29 (36)29\ (36)10 (40)10\ (40)22 (42)22\ (42)23 (45)23\ (45)21 (48)21\ (48)
46 (56)46\ (56)24 (60)24\ (60)28 (63)28\ (63)63 (64)63\ (64)14 (70)14\ (70)
41 (72)41\ (72)77 (80)77\ (80)4 (84)4\ (84)32 (90)32\ (90)45 (96)45\ (96)
13 (105)13\ (105)52 (112)52\ (112)30 (120)30\ (120)112 (126)112\ (126)54 (140)54\ (140)
5 (144)5\ (144)61 (160)61\ (160)136 (168)136\ (168)104 (180)104\ (180)159 (192)159\ (192)
202 (210)202\ (210)95 (224)95\ (224)189 (240)189\ (240)70 (252)70\ (252)74 (280)74\ (280)
77 (288)77\ (288)239 (315)239\ (315)287 (320)287\ (320)220 (336)220\ (336)230 (360)230\ (360)
414 (420)414\ (420)415 (448)415\ (448)285 (480)285\ (480)466 (504)466\ (504)18 (560)18\ (560)
479 (576)479\ (576)448 (630)448\ (630)127 (672)127\ (672)365 (720)365\ (720)790 (840)790\ (840)
95 (960)95\ (960)298 (1008)298\ (1008)895 (1120)895\ (1120)952 (1260)952\ (1260)31 (1344)31\ (1344)
509 (1440)509\ (1440)298 (1680)298\ (1680)1183 (2016)1183\ (2016)671 (2240)671\ (2240)1642 (2520)1642\ (2520)
2399 (2880)2399\ (2880)1631 (3360)1631\ (3360)2527 (4032)2527\ (4032)802 (5040)802\ (5040)2591 (6720)2591\ (6720)
7871 (10080)7871\ (10080)6431 (20160)6431\ (20160)

Table 10. Complete covering for m=8m = 8, L=20160L = 20160.

Minimum modulus 9

The least common multiple is L=75600L = 75600.

2 (9)2\ (9)0 (10)0\ (10)1 (12)1\ (12)7 (14)7\ (14)6 (15)6\ (15)
3 (16)3\ (16)14 (18)14\ (18)12 (20)12\ (20)15 (21)15\ (21)7 (24)7\ (24)
24 (25)24\ (25)26 (27)26\ (27)13 (28)13\ (28)16 (30)16\ (30)3 (35)3\ (35)
5 (36)5\ (36)2 (40)2\ (40)9 (42)9\ (42)13 (45)13\ (45)43 (48)43\ (48)
4 (50)4\ (50)44 (54)44\ (54)55 (56)55\ (56)48 (60)48\ (60)54 (63)54\ (63)
45 (70)45\ (70)23 (72)23\ (72)19 (75)19\ (75)62 (80)62\ (80)81 (84)81\ (84)
88 (90)88\ (90)64 (100)64\ (100)24 (105)24\ (105)17 (108)17\ (108)27 (112)27\ (112)
22 (120)22\ (120)33 (126)33\ (126)116 (135)116\ (135)18 (140)18\ (140)59 (144)59\ (144)
84 (150)84\ (150)39 (168)39\ (168)69 (175)69\ (175)28 (180)28\ (180)8 (189)8\ (189)
114 (200)114\ (200)87 (210)87\ (210)71 (216)71\ (216)184 (225)184\ (225)102 (240)102\ (240)
201 (252)201\ (252)8 (270)8\ (270)98 (280)98\ (280)34 (300)34\ (300)138 (315)138\ (315)
123 (336)123\ (336)294 (350)294\ (350)118 (360)118\ (360)89 (378)89\ (378)214 (400)214\ (400)
258 (420)258\ (420)395 (432)395\ (432)34 (450)34\ (450)327 (504)327\ (504)219 (525)219\ (525)
89 (540)89\ (540)58 (560)58\ (560)214 (600)214\ (600)305 (630)305\ (630)494 (675)494\ (675)
58 (700)58\ (700)658 (720)658\ (720)737 (756)737\ (756)798 (840)798\ (840)784 (900)784\ (900)
332 (945)332\ (945)75 (1008)75\ (1008)144 (1050)144\ (1050)858 (1080)858\ (1080)414 (1200)414\ (1200)
978 (1260)978\ (1260)1034 (1350)1034\ (1350)198 (1400)198\ (1400)359 (1512)359\ (1512)1419 (1575)1419\ (1575)
538 (1680)538\ (1680)1278 (1800)1278\ (1800)683 (1890)683\ (1890)618 (2100)618\ (2100)1142 (2160)1142\ (2160)
2458 (2520)2458\ (2520)359 (2700)359\ (2700)338 (2800)338\ (2800)1115 (3024)1115\ (3024)894 (3150)894\ (3150)
978 (3600)978\ (3600)1817 (3780)1817\ (3780)1038 (4200)1038\ (4200)4679 (4725)4679\ (4725)4618 (5040)4618\ (5040)
4814 (5400)4814\ (5400)6078 (6300)6078\ (6300)7487 (7560)7487\ (7560)6498 (8400)6498\ (8400)1439 (9450)1439\ (9450)
1979 (10800)1979\ (10800)1878 (12600)1878\ (12600)3707 (15120)3707\ (15120)12239 (18900)12239\ (18900)16578 (25200)16578\ (25200)
31679 (37800)31679\ (37800)25423 (75600)25423\ (75600)

Table 11. Complete covering for m=9m = 9, L=75600L = 75600. Entries are a (d)a\ (d), meaning x≡a(modd)x \equiv a \pmod d.

Minimum modulus 10

The least common multiple is L=302400L = 302400.

8 (10)9 (12)4 (14)5 (15)7 (16)
13 (18)2 (20)17 (21)3 (24)24 (25)
25 (27)8 (28)0 (30)31 (32)21 (35)
1 (36)32 (40)5 (42)10 (45)35 (48)
14 (50)43 (54)20 (56)6 (60)62 (63)
47 (64)26 (70)19 (72)59 (75)12 (80)
29 (84)40 (90)11 (96)54 (100)86 (105)
61 (108)100 (112)96 (120)41 (126)115 (135)
106 (140)125 (144)84 (150)132 (160)137 (168)
119 (175)173 (180)115 (189)15 (192)104 (200)
16 (210)115 (216)123 (224)109 (225)17 (240)
77 (252)70 (270)216 (280)155 (288)294 (300)
146 (315)212 (320)53 (336)194 (350)317 (360)
178 (378)204 (400)286 (420)341 (432)180 (448)
184 (450)143 (480)149 (504)44 (525)413 (540)
156 (560)271 (576)144 (600)346 (630)155 (672)
259 (675)694 (700)137 (720)10 (756)4 (800)
276 (840)485 (864)29 (900)451 (945)527 (960)
221 (1008)394 (1050)593 (1080)532 (1120)689 (1200)
986 (1260)1103 (1344)34 (1350)944 (1400)923 (1440)
665 (1512)1469 (1575)404 (1600)1577 (1680)655 (1728)
389 (1800)136 (1890)1115 (2016)1294 (2100)197 (2160)
52 (2240)239 (2400)1913 (2520)629 (2700)44 (2800)
1403 (2880)1673 (3024)94 (3150)3227 (3360)1289 (3600)
2656 (3780)539 (4032)444 (4200)3977 (4320)4294 (4725)
1679 (4800)1901 (5040)5129 (5400)5204 (5600)917 (6048)
1994 (6300)911 (6720)2939 (7200)233 (7560)7289 (8400)
6137 (8640)7444 (9450)1787 (10080)2789 (10800)1204 (11200)
9557 (12096)3929 (12600)629 (14400)7638 (15120)13979 (16800)
1144 (18900)11573 (20160)16119 (21600)23069 (25200)9557 (30240)
10319 (33600)12329 (37800)22247 (43200)25979 (50400)45017 (60480)
54089 (75600)50939 (100800)47657 (151200)63989 (302400)

Table 12. Complete covering for m=10m = 10, L=302400L = 302400. Entries are aa (dd), meaning x≡a(modd)x \equiv a \pmod d

Minimum modulus 11

The least common multiple is L=3326400L = 3326400.

10 (11)9 (12)12 (14)10 (15)7 (16)
11 (18)16 (20)4 (21)6 (22)3 (24)
17 (25)26 (27)2 (28)1 (30)31 (32)
14 (33)34 (35)5 (36)8 (40)18 (42)
2 (44)19 (45)36 (48)2 (50)17 (54)
9 (55)22 (56)13 (60)7 (63)28 (64)

Table 13. Complete covering for m=11m = 11, L=3326400L = 3326400. Entries are aa (dd), meaning x≡a(modd)x \equiv a \pmod d

Continued on the next page

8 (66)48 (70)59 (72)7 (75)45 (77)
64 (80)42 (84)18 (88)49 (90)15 (96)
11 (99)12 (100)73 (105)89 (108)20 (110)
106 (112)43 (120)112 (126)38 (132)34 (135)
6 (140)95 (144)127 (150)136 (154)108 (160)
125 (165)150 (168)97 (175)84 (176)0 (180)
106 (189)60 (192)176 (198)32 (200)90 (210)
35 (216)60 (220)162 (224)172 (225)158 (231)
24 (240)154 (252)62 (264)259 (270)97 (275)
268 (280)204 (288)143 (297)37 (300)210 (308)
304 (315)204 (320)320 (330)234 (336)62 (350)
172 (352)240 (360)187 (378)224 (385)86 (396)
272 (400)346 (420)143 (432)40 (440)274 (448)
247 (450)452 (462)463 (480)218 (495)436 (504)
262 (525)68 (528)300 (540)522 (550)184 (560)
498 (576)44 (594)187 (600)92 (616)94 (630)
200 (660)66 (672)547 (675)56 (693)482 (700)
700 (704)104 (720)232 (756)114 (770)716 (792)
332 (800)482 (825)148 (840)696 (864)148 (880)
72 (900)686 (924)79 (945)684 (960)416 (990)
738 (1008)472 (1050)332 (1056)120 (1080)262 (1100)
946 (1120)254 (1155)1142 (1188)1087 (1200)386 (1232)
904 (1260)764 (1320)498 (1344)97 (1350)980 (1386)
1072 (1400)300 (1440)1043 (1485)66 (1512)1148 (1540)
772 (1575)200 (1584)72 (1600)632 (1650)344 (1680)
1128 (1728)1468 (1760)1372 (1800)1772 (1848)394 (1890)
422 (1925)1868 (1980)402 (2016)3 (2079)2072 (2100)
1916 (2112)480 (2160)532 (2200)498 (2240)2174 (2310)
548 (2376)562 (2400)1170 (2464)1672 (2475)28 (2520)
104 (2640)2172 (2700)2350 (2772)72 (2800)562 (2880)
746 (2970)24 (3024)1624 (3080)997 (3150)1042 (3168)
2372 (3300)274 (3360)1767 (3465)1202 (3520)2172 (3600)
920 (3696)1032 (3780)1882 (3850)3104 (3960)3090 (4032)
3594 (4158)672 (4200)3720 (4320)4072 (4400)4412 (4620)
4497 (4725)3432 (4752)2099 (4800)2034 (4928)4092 (4950)
816 (5040)3773 (5280)4438 (5400)2880 (5544)4862 (5600)
336 (5775)3146 (5940)5041 (6048)1904 (6160)4036 (6300)
2721 (6336)2556 (6600)1010 (6720)5897 (6930)886 (7200)
7261 (7392)5605 (7425)3130 (7560)1970 (7700)774 (7920)
6649 (8316)5839 (8400)5981 (8640)4689 (8800)4243 (9240)
7730 (9450)1719 (9504)7105 (9900)6726 (10080)6187 (10395)
8945 (10560)4943 (10800)3786 (11088)5044 (11200)3673 (11550)
9926 (11880)10181 (12096)1274 (12320)8343 (12600)10026 (13200)
11411 (13860)2011 (14400)1552 (14784)8389 (14850)2510 (15120)
15235 (15400)14188 (15840)15253 (16632)10805 (16800)1288 (17325)
1272 (17600)5039 (18480)11887 (18900)979 (19008)17429 (19800)
15730 (20160)12921 (20790)6032 (21600)17906 (22176)2771 (23100)
3380 (23760)23285 (24640)17262 (25200)23334 (26400)20944 (27720)
22244 (29700)7550 (30240)7822 (30800)5560 (31680)27480 (33264)
4057 (33600)28859 (34650)24257 (36960)27555 (37800)6931 (39600)
7422 (41580)26748 (43200)117 (44352)14953 (46200)12869 (47520)
35 (50400)43386 (51975)21190 (52800)8832 (55440)28604 (59400)
51290 (60480)2316 (61600)8436 (66528)33019 (69300)65340 (73920)
36658 (75600)33041 (79200)9471 (83160)16431 (92400)18516 (95040)
6783 (100800)91813 (103950)60518 (110880)59889 (118800)3696 (123200)
62596 (133056)87874 (138600)116975 (151200)34401 (158400)90791 (166320)
53591 (184800)147882 (207900)62786 (221760)197451 (237600)86741 (277200)
64669 (302400)173009 (332640)295599 (369600)47173 (415800)225747 (475200)
414022 (554400)25865 (665280)110190 (831600)1031743 (1108800)1097511 (1663200)
1956368 (3326400)

Table 13 (continued). m=11m = 11, L=3326400L = 3326400. Entries are a (d)a\ (d), meaning x≡a(modd)x \equiv a\pmod d.

Independent Verification

The supplementary program verify.py requires Python 3.9 or later and no external packages. From the paper directory, run

python3 anc/supplementary/verify.py main.tex

It reads the marked certificate blocks, checks distinct moduli, valid residues, minimum modulus and actual LCM, and marks every covered residue in 0,…,L−10, \ldots, L - 1. All four lists pass. Its checks use explicit exceptions and remain active under Python’s optimization option.

The supplement also retains reduced certificates and private-point witnesses. A private point is covered by exactly one class; finding one for every retained class certifies irredundancy. These subsidiary checks are independent of the LCM bounds.

Experimental Details and Supplementary Comparisons

Execution and budget accounting

The kernels use 32 perturbation steps and at most 80 coordinate rounds. Before exceeding a phase allowance, the wrapper interrupts and retains its best state with all active residues assigned, discarding unfinished ruin–recreate proposals. Each insertion phase has a random fallback assignment. At the first covering it stops, assigning arbitrary residues to unused divisors. Thus every output contains the full divisor set. These rules define the new experiments, not the historical executable.

All 180 assignments and phase/trajectory counts passed independent checks: 75 coverings and 105 budget exhaustions. No phase reached the safety cap of 100000 trajectory starts. Complete start, completion and interruption counts accompany the data.

Runs were serial, with one worker, on an Apple M4 MacBook Pro (24 GB, macOS 27.0.1), using Apple Clang 21.0.0 and -std=c++17 -O3 -DNDEBUG -pthread. CPU and wall timers include setup and initialization; the host was not exclusively reserved. The directory supplementary/experiments_20261031 supplies the frozen protocol, source/executable hashes, commands, assignments and logs.

Initial-study attribution and bank diagnostics

At both L=30240L = 30240 and 7560075600, five of ten runs per half-insertion configuration succeed during common insertion. Of the other five at 30240, Adjacent, Global and Bank-1 rescue two each, and Bank-20 rescues three; at 75600, each rescues one. These conditional counts use the same saved states and are not additional independent samples.

Replays of all 30 Bank-20 runs exactly reproduce their assignments and non-timing counters. Maximum bank sizes on the three instances are 13, 11, 9; nonelite parents are used in 9, 4, 4 runs. Replay timings are excluded from Table 16. In same-random-seed pairs, Bank-20 has lower/equal/higher gaps than Bank-1 in 5/4/1, 1/8/1, and 0/10/0 cases. At 20160, one Bank-20 run has 72 extra gaps despite five small paired improvements; the bank medians are 29.5 versus 21. There is no consistent larger-bank advantage.

For 0/10, 3/10 and 8/10, the 95% Wilson intervals are approximately [0, 0.278], [0.108, 0.603] and [0.490, 0.943]. All row-wise intervals and individual gaps are supplied. The small samples do not establish a general ranking; wall-time matching and projected initialization are untested.

The original bank’s exposure audit covers 85 epochs: 79 complete one trajectory and interrupt a second, one completes two including success, and five succeed on their first. Every epoch restarts parent selection, so all 165 starts use positions 1 or 2. Schedule cycling also restarts, never reaching the third, mixed schedule. Retained bank size therefore overstates actual parent exposure; the initial capacity comparison is limited to these rules. § 6.3 tests revised sampling and schedule cycling.

Larger-period comparison

The following table gives every larger-period comparison discussed in § 6.3. All counts and statistics follow the definitions in § 6.

Supplementary comparison tables

Table 15 compares initialization orders; Table 16 reports initial-study timing and trajectory counts. A trajectory consists of initialization, coordinate search and perturbation steps (Appendix § 8.§ 1); only completed trajectories enter the counts. Successful-run timing is conditional on success, not expected time to success. Follow-up timings and per-parent work are supplied in machine-readable form.

Acknowledgements

This work was supported by ShanghaiTech AI Initiative (Grant No. AI2026B16). The author thanks Hao Chen, Lian Duan, Boqing Xue, Jiayu Zhai, and Shiliang Zhang for helpful support, discussions, and encouragement.

J. Zhang, Institute of Mathematical Sciences ShanghaiTech University No. 393 Middle Huaxia Road, Pudong New District, Shanghai, China Email: [email protected]

References

  1. [1]P. Erdős, On integers of the form 2^k + p and some related problems, Summa Brasil. Math. 2 (1950), 113–123.
  2. [2]Š. Porubský and J. Schönheim, Covering systems of Paul Erdős: past, present and future, in Paul Erdős and His Mathematics, I, János Bolyai Math. Soc., Budapest, 2002, pp. 581–627.
  3. [3]B. Hough, Solution of the minimum modulus problem for covering systems, Ann. of Math. 181 (2015), no. 1, 361–382, doi:10.4007/annals.2015.181.6.arxiv.org/abs/1307.0874
  4. [4]J. Dalton and O. Trifonov, Extreme covering systems, J. Integer Seq. 25 (2022), no. 9, Article 22.9.1, 28 pp., https://cs.uwaterloo.ca/journals/JIS/VOL25/Trifonov/trif3.pdf.
  5. [5]P. Balister, Erdős covering systems, in Surveys in Combinatorics 2024, Cambridge University Press, Cambridge, 2024, pp. 31–54.
  6. [6]J. Klein, On a conjecture of Krukenberg and a problem of Dalton and Trifonov, Integers 26 (2026), #A38, doi:10.5281/zenodo.19402698.
  7. [7]S. Zhang and J. Zhang, A distinct covering system with minimum modulus 7 and minimal least common multiple 10080, arXiv:2607.19029 [math.NT], 2026, doi:10.48550/arXiv.2607.19029.DOI
  8. [8]W. Bosma, Some computational experiments in number theory, in W. Bosma and J. Cannon (eds.), Discovering Mathematics with Magma, Algorithms and Computation in Mathematics, vol. 19, Springer, Berlin, Heidelberg, 2006, pp. 1–30, doi:10.1007/978-3-540-37634-7_1.DOI
  9. [9]K. Bickel, M. Firrisa, J. Ortiz, and K. Pueschel, Constructions of coverings of the integers: Exploring an Erdős problem, Summer Math Institute, Cornell University, manuscript, 2008, online manuscript.
  10. [10]N. McNew and J. Setty, On the densities of covering numbers and abundant numbers, arXiv:2507.23041v2, revised February 2026, doi:10.48550/arXiv.2507.23041.arxiv.org/abs/2507.23041
  11. [11]J. Harrington, J. Klein, J. Lowrance, and O. Trifonov, Covering systems where the prime divisors of all moduli are only 2, 3, or 5, arXiv:2605.18644 [math.NT], 2026, doi:10.48550/arXiv.2605.18644.DOI
  12. [12]H. R. Lourenço, O. C. Martin, and T. Stützle, Iterated local search, arXiv:math/0102188 [math.OC], 2001, https://arxiv.org/abs/math/0102188.
  13. [13]G. Schrimpf, J. Schneider, H. Stamm-Wilbrandt, and G. Dueck, Record breaking optimization results using the ruin and recreate principle, J. Comput. Phys. 159 (2000), no. 2, 139–171, doi:10.1006/jcph.1999.6413.DOI

Paper details

vlnc:W_txzc4mkn
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 3

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents