Stapled sequences and stapling coverings of natural numbers

Irene Gassko

The electronic journal of combinatorics, Tome 3 (1996) no. 1

Résumé

A stapled sequence is a set of consecutive positive integers such that no one of them is relatively prime with all of the others. The problem of existence and construction of stapled sequences of length $N$ was extensively studied for over 60 years by Pillai, Evans, Brauer, Harborth, Erdős and others.Sivasankaranarayana, Szekeres and Pillai proved that no stapled sequences exist for any $N < 17$. We give a new simple proof of this fact.There exist several proofs that stapled sequences exist for any $N \geq 17$. We show that existence of stapled sequences is equivalent to existence of stapling coverings of a sequence of $N$ consecutive natural numbers by prime arithmetic progressions such that each progression has at least two common elements with the sequence and discuss properties of stapling coverings. We introduce the concept of efficiency of stapling coverings and develop algorithms that produce efficient stapling coverings. Using the result by Erdős, we show that the greatest prime number used in stapling coverings of length $N$ can be made $o(N)$.

Détail

DOI : 10.37236/1257

Classification : 11B50, 11A07, 11Y16, 11Y55, 68R05, 11B75
Mots-clés : stapled sequences, stapling coverings of a sequence, prime arithmetic progressions, algorithms, efficient stapling coverings, congruences