Stapled sequences and stapling coverings of natural numbers (Q1379179)

Summary: 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\) has been 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 the existence of stapled sequences is equivalent to the 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)\).