Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: Stapled Sequences and Stapling Coverings of Natural Numbers. | Stapled Sequences and Stapling Coverings of Natural Numbers Irene Gassko irina@ Boston University Computer Science Department AMS Subject Classification 11B50 primary 11A07 11Y16 11Y55 68R05 11B75 secondary . Submitted March 30 1996 Accepted October 30 1996 Abstract 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 Erdos 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 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 Erdos we show that the greatest prime number used in stapling coverings of length N can be made o N . __ Partially supported by NSF grant CCR-9204284 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 3 1996 R33 2 1 Introduction Consider the following problem for a given N does there exist a sequence SN of N successive natural numbers such that no element is relatively prime with all the others We call such sequences stapled. This problem was originally suggested by Szekeres 4 and by Pillai 13 . It was extensively studied for over half a century by Erdos Pillai Evans Brauer Harborth and others. Sivasankaranarayana Szekeres and Pillai proved that no stapled sequences exist for any N 17 5 . A simpler proof of this fact is presented in this paper. Pillai 13 Brauer
