Covering Set¶

Certify that every term of a modularly periodic integer sequence has a divisor from one finite prime set by covering every index class with a periodic divisibility congruence.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1576
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Number Theory → Mathematics

Core Idea¶

A covering set, in the number-theoretic sense used here, is a finite set of primes that acts as a certificate for an infinite integer sequence: every term of the sequence is divisible by at least one prime in the set. The certificate becomes finite because divisibility of an exponential or recurrence sequence modulo a fixed prime is periodic. Each prime therefore covers one or more residue classes of term indices, and the union of those index classes must cover every index in scope.

How would you explain it like I'm…

Every Number Has a Divider

Imagine a never-ending line of numbers made by a pattern. A covering set is a short list of 'splitter' numbers where every number in the line can be split evenly by at least one splitter. Because the pattern repeats, checking a small part is enough to know it works for the whole endless line.

Primes That Cover Every Term

Some number sequences go on forever, like k × 2ⁿ + 1 for n = 1, 2, 3, and so on. A covering set is a small, finite list of prime numbers that proves every number in such a sequence can be divided evenly by at least one of those primes. The trick is that divisibility by a fixed prime repeats in a pattern: if a prime divides one term, it divides the terms at regular spacings after it too. So each prime takes care of certain positions in the sequence, and together they must take care of every position. If every term is bigger than the primes, then every term has a smaller divisor, so none of them is prime.

Finite Prime Divisibility Certificate

In number theory, a covering set for an infinite integer sequence is a finite set of primes such that every term of the sequence is divisible by at least one of them. It works because, for a sequence like a_n = k b^n + 1 or k b^n - 1, divisibility by a fixed prime p repeats periodically in n. So each prime 'covers' certain positions n, those in particular remainder classes modulo some period m. The certificate is complete only if these remainder classes together include every n. When the terms are bigger than the primes in the set, this proves every term is composite. A covering set needs three layers: the primes, the assignment of every index to a prime, and the modular equations showing each assignment really holds for the specific sequence. It is famously used for Sierpinski and Riesel numbers, such as k = 78557, where the seven primes 3, 5, 7, 13, 19, 37 and 73 show that every k 2^n + 1 is composite.

A covering set is a finite prime certificate that every term of an infinite integer sequence is divisible by at least one member. For a_n = k b^n + ε with ε = ±1, a prime p not dividing b covers the index class n ≡ r (mod m) when k b^r + ε ≡ 0 (mod p) and b^m ≡ 1 (mod p): then b^(r+tm) ≡ b^r, so p divides a_(r+tm) for every t ≥ 0. The certificate has three layers that must all be present: the prime set; the index covering, a family of congruence classes that together contain every permitted n; and the sequence-specific compatibility conditions that make each prime actually divide the assigned terms for the given k, b and ε. When the terms exceed the covering primes in absolute value, this proves every term composite, turning an infinite claim into a finite modular check. Covering sets underlie Sierpiński and Riesel constructions: Sierpiński proved in 1960 that infinitely many odd k make every k·2^n + 1 composite, and Selfridge's k = 78557 uses the primes {3, 5, 7, 13, 19, 37, 73}. The same architecture gives primefree linear recurrences, where periodic zeros modulo chosen primes cover all indices. The term here does not mean geometric covers, set cover, covering codes or a bare covering system of congruences.

Scope of Application¶

The home domain is elementary and computational number theory of exponentially growing or periodically reducible integer sequences.

Sierpiński sequences: certify that \(k2^n+1\) is composite for every index by a finite collection of small prime divisors.
Riesel sequences: apply the corresponding construction to \(k2^n-1\), with sign-adjusted modular compatibility.
Other bases: replace 2 by \(b>1\); the period becomes the multiplicative order of \(b\) modulo each covering prime, provided \(p\nmid b\).
Primefree linear recurrences: exploit periodicity of recurrence states modulo primes so zero-position classes cover every sequence index.

Clarity¶

A clear covering-set claim should be published as a certificate table rather than as a bare list. For every row record the prime \(p\), the index condition \(n\equiv r\pmod m\), the sequence-parameter congruence used, and the resulting divisibility statement. Then state a common modulus \(M=\operatorname{lcm}(m_1,\ldots,m_s)\) and verify all residues \(0,\ldots,M-1\). This exposes both possible defects: a bad row and a gap between rows.

Manages Complexity¶

The covering set compresses an infinite universal claim into three finite objects: a bounded prime list, a bounded residue table, and a bounded common-period coverage check. Instead of factoring ever larger terms, the reasoner works in small residue rings. The certificate is auditable, portable between proof and computation, and cheap to recheck.

Abstract Reasoning¶

The key reasoning move is local-to-global through periodicity and coverage. Each prime supplies a local theorem on one arithmetic progression of indices. Completeness of the union upgrades those local theorems to a global quantifier over all indices. The proof is not induction: it does not propagate truth from \(n\) to \(n+1\). It quotients the infinite index set by a finite common period and checks representatives.

Knowledge Transfer¶

The full abstraction transfers literally within number theory wherever an indexed integer sequence has finite modular state and selected primes cover all zero-position classes. The objects change—exponentials, sign variants, Lucas-type recurrences—but the proof obligations do not: compute periods, bind index classes to primes, cover the domain, and rule out trivial equality.

Useful knowledge transfers between Sierpiński/Riesel work and primefree recurrences. A researcher who sees a modular cycle can search its zero positions; who sees several zero-position progressions can ask whether they cover; who has a cover can solve parameter congruences rather than test parameters blindly.

Relationships to Other Abstractions¶

Current abstraction Covering Set Domain-specific

Parents (2) — outgoing typed relations

Covering Set is a kind of Coverage / Reachability Prime

Covering Set instantiates Coverage / Reachability in a strict number-theoretic form: the required targets are all allowed indices, and each must be reached by at least one prime-divisibility rule.
Covering Set presupposes Periodicity Prime

Covering Set instantiates Coverage / Reachability in a strict number-theoretic form: the required targets are all allowed indices, and each must be reached by at least one prime-divisibility rule.

Hierarchy paths (3) — routes to 3 parentless roots

Covering Set → is a kind of Coverage / Reachability → is a kind of Completeness

Show alternative paths (2)

Neighborhood in Abstraction Space¶

Covering Set sits in a moderately populated region (51^st percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.

Family — Unclustered & Miscellaneous (2769 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25