Stapled Sequences and Stapling Coverings of Natural Numbers

Irene Gassko^{∗} irina@cs.bu.edu 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, 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 ≥ 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).

∗Partially supported by NSF grant CCR-9204284

1 Introduction

Consider the following problem: for a given N, does there exist a sequence S_{N} 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 Erdös, 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 [1], Harborth [10, 11] and Evans[2] proved that for any N ≥ 17 there exist stapled sequences of length N, i.e. sequences of consecutive natural numbers, where each element has a common divisor 1 < d ≤ N with the product of all the other elements of the sequence. As shown below, this problem is equivalent to the problem of covering finite sequences of natural numbers by arithmetic progressions with prime differences. The concept of efficiency of such coverings is introduced in this paper and constructions producing efficient stapling coverings are presented.

While Evans’ solution [2] is considered the most elegant proof of the existence of stapling coverings for N > 16, Brauer’s solution [1] is seemingly the most efficient one suggested before this paper. Below we describe algorithms that produce significantly more efficient coverings than those by Brauer. It is also shown that the greatest prime number used in a in stapling covering can be made smaller than δN, for any δ > 0, if N is sufficiently large.

2 Definitions

Definition 2.1. A sequence of successive natural numbers (SSN) S_{N} of length N is called a stapled sequence if for any s ∈ S_{N} ∃s′ ∈ S_{N}, s′ ≠ s, such that the greatest common divisor (s, s′) > 1.

Definition 2.2. An arithmetic progression A_{p}^{a_{p}} = {a_{p} + kp | k ∈ ℤ} (a_{p} ∈ ℤ_{p}) is called a prime congruence if p is prime. (The upper index a_{p} will be omitted whenever it is not essential).

Denote by p_{i} the i-th prime number.

Definition 2.3. Consider a set of congruences W_{I} = {A_{p_{i}}} (I = {i} ⊆ ℕ). The set T = T (S_{N}, W_{I}) = {V_{i} | i ∈ I} where V_{i} = S_{N} ⋂ A_{p_{i}} is called a tiling of S_{N} by W_{I}. If all p_{i} are distinct primes, T is a prime tiling.

Obviously, U = U(S_{N}, W_{I}) = ⋃_{i∈I}(S_{N} ⋂ A_{p_{i}}) ⊆ S_{N}.

Definition 2.4. A tiling T = T (S_{N}, W_{I}) is complete if U = S_{N}. A complete tiling is called also a covering of S_{N} by W_{I}.

Definition 2.5. If in a prime covering T (S_{N}, W_{I})

| S_{N} ⋂ A_{p_{i}} |≥ 2, for any i ∈ I  (2.1)

T is called a stapling covering of S_{N} by W_{I}.

If | S_{N} ⋂ A_{p_{i}} |≥ n, for any i ∈ I, n ≥ 2, T is called an n-stapling covering of S_{N} by W_{I}.

Definition 2.6. Consider S_{N} = (s_{1}, s_{2}, …, s_{N}) and a prime tiling T (S_{N}, W_{I}). If s_{r_{i}} ∈ A_{p_{i}} the number r_{i} is called indicator of A_{p_{i}} in S_{N}. If h_{i} = h(p_{i}) is the least number such that s_{h_{i}} ∈ A_{p_{i}}, h_{i} is the first indicator of A_{p_{i}} in S_{N}. If s_{r} ∈ A_{p} we say that A_{p} (or, simply, p) covers s_{r}.

Obviously, a tiling of S_{N} is uniquely determined by the set of its first indicators {h_{i} | i ∈ I}.

Definition 2.7. Two SSN’s S_{N} and S′_{N} are equivalent with respect to W_{I} (S_{N} ∼ S′_{N} (resp W_{I})), if for any i ∈ I, h_{i} = h′_{i}, where s_{h_{i}} ∈ S_{N}, s_{h′_{i}} ∈ S′_{N}.

Example

The shortest, and, seemingly, the first known example of a stapled sequence is the sequence of length N = 17 which starts with s_{1} = 2184 and ends with s_{17} = 2200 (we denote it by S = [2184, 2200]). Let us use this example to illustrate the notation in Defs. 2.1 to 2.7.

The stapling covering of this sequence is given by a set of congruences W_{I} = {A_{p_{i}}^{0}}, where I = {1, 2, 3, 4, 5, 6}, p_{1} = 2, p_{2} = 3, p_{3} = 5, p_{4} = 7, p_{5} = 11, p_{6} = 13. The first indicators are as follows: h_{1} = h(2) = 1 (which means that s_{1} = 2184 is divisible by 2: s_{1} = 2184 ∈ A_{2}^{0}); h_{2} = h(3) = 1 (s_{1} ∈ A_{3}^{0}); h_{3} = h(5) = 2 (s_{2} = 2185 ∈ A_{5}^{0}); h_{4} = h(7) = 1 (s_{1} ∈ A_{7}^{0}); h_{5} = h(11) = 6 (s_{6} ∈ A_{11}^{0}); h_{6} = h(13) = 1 (s_{1} ∈ A_{13}^{0}).

This stapled sequence is equivalent to the sequence [2184+30030k, 2200+ 30030k], k ∈ ℤ, with respect to the same set of congruences, where 30030 is the least common multiple of 2,3,5,7,11,13.

The same set of first indicators provides stapling covering for any SSN of length N, but, of course, with shifted prime congruences. In particular, stapling covering for the sequence [1,17] is given by A_{2}^{1}, A_{3}^{1}, A_{5}^{2}, A_{7}^{1}, A_{11}^{6}, A_{13}^{1} as shown below

s_{i}  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
p_{1}  2  2  2  2  2  2  2  2  2
p_{2}  3  3  3  3  3  3
p_{3}  5  5  5  5
p_{4}  7  7  7
p_{5}  11  11
p_{6}  13  13

3 Properties of Stapled Sequences

Denote by W_{I}^{0} a set of prime congruences A_{p_{i}}^{0}, such that A_{p_{i}}^{0} = kp_{i}, k ∈ ℤ, i ∈ I, i.e. such that a_{p_{i}} = 0, i ∈ I. Obviously, if T (S_{N}^{0}, W_{I}^{0}) is a stapling covering, then S_{N}^{0} is a stapled sequence.

Lemma 3.1. If S_{N}^{0} is a stapled SSN and T (S_{N}^{0}, W_{I}^{0}) is the corresponding stapling covering, there exists stapling covering T ([1, N], W_{I}) such that s_{h_{I}} = h_{i} = h_{i}^{0} for any i ∈ I.

The example given at the end of the Sec. 2 illustrates this lemma. The position of the first term divisible by p_{i} in a stapled sequence is equal to the first indicator (i.e. to the “shift” a_{p_{i}}) of A_{p_{i}} in the stapling covering for [1, N].

Lemma 3.2. If T (S_{N}, W_{I}) is a stapling covering, then there exists a stapled SSN S_{N}^{0} of length N .

Lemmata 3.1 and 3.2 show that the existence of a stapling covering of the sequence [1, N] = (1, 2, …, N) is the necessary and sufficient condition for the existence of a stapled sequence of length N.

If T ([1, N], W_{I}) is a stapling covering with a set of first indicators {h_{i}}, i ∈ I, then a stapled sequence of length N is S_{N} = (M + 1, …, M + N), where M satisfies equations:

M + h_{i} ≡ 0 mod p_{i}

.

Lemma 3.3. S_{N} ∼ S′_{N} (resp W_{I}) iff s′_{k} ≡ s_{k} ( mod ∏_{i∈I} p_{i}) , for all k ∈

[1, N] = (1, 2, …, N), s_{k} ∈ S_{N}, s′_{k} ∈ S′_{N}.

Proofs of Lemmata 3.1, 3.2 and 3.3 are given in Appendix A.

Lemmata 3.2 and 3.3 show, in particular, that if for a given N there exists one stapled sequence, then there exist infinitely many of them.

Note, that if there exists a stapling covering T (S_{N}, W_{I}), then there exists its “mirror image”, i.e. stapling covering T′(S_{N}, W′_{I}) such that if s_{r} ∈ A_{p} in T then s_{N−r+1} ∈ A_{p} in T′.

Lemma 3.4. A covering T (S_{N}, W_{I}) and its “mirror image” T′(S_{N}, W′_{I}) are always different.

Proof. Let us show that a covering cannot be symmetric, i.e. cannot be identical with its mirror image. Indeed, if N is even then s_{\frac{1}{2} N} and s_{\frac{1}{2} N+1} cannot be covered by the same primes thus breaking symmetry. If N is odd and the stapling covering is symmetric, then s_{\frac{1}{2} (N+1)} must be covered by all A_{p} ∈ W_{I}, where p is odd. Indeed, if both s_{r} and s_{N−r+1} are covered by an odd prime p, then s_{N−r+1} − s_{r} = N + 1 − 2r = 2kp, k ∈ ℤ. Hence, s_{\frac{1}{2} (N+1)} −s_{r} = \frac{1}{2}(N +1−2r) = kp, and s_{\frac{1}{2} (N+1)} is covered by p. Then s_{\frac{1}{2} (N−1)} and s_{\frac{1}{2} (N−3)} are not covered by any odd p. But only one of these numbers can be covered by 2. Thus, symmetric coverings are impossible, which proves the lemma.

Corollary 3.5. The number of different stapling coverings of length N is always even.

Proof. Follows immediatedly from Lemma 3.4.

Lemma 3.6. If S_{2N} is a stapled SSN, then there exist S_{2N+1} and S_{2N−1} which are also stapled.

Proof. • If there exists stapled S_{2N}, it means that there exists a stapling covering T ([1, 2N], W_{I}). If h(2) = 1, then 2N + 1 ∈ A_{2}, and the lemma is proved. If h(2) = 2, then consider W′_{I} = {A′_{p_{i}}} where for each A′_{p_{i}} h′_{i} = h_{i} + 1( mod p_{i}). These progressions form a stapling covering of the sequence (2, …, 2N + 1). Since, obviously, 1 ∈ A′_{2}, ([1, 2N + 1], W_{I}) is a stapling covering, and a stapled S_{2N+1} exists.

• Without loss of generality assume that in ([1, 2N], W_{I}) h(2) = 1. (If h(2) = 2, consider the “mirror image” of the sequence). Then 2N is covered by A_{p}, where p is an odd prime. If p < N, | [1, 2N − 1] ⋂ A_{p} |≥ 2. If p ≥ N, the only r ∈ A_{p}, r ≠ 2N is odd and, hence, r ∈ A_{2} and A_{p} can be removed from W_{I}. Thus, the number 2N can be deleted without violating the stapling condition, and stapled S_{2N−1} exists.

Lemma 3.7. If S_{2N−1} is a stapled SSN and 2N-1 is prime, there exists S_{2N} which is also stapled.

Proof. Consider a stapling covering T ([1, 2N − 1], W_{I}). Then a stapling covering of [1, 2N] is given by W′_{I}, where W′_{I} = W_{I} ⋃{A_{2N−1}}, h(2N − 1) = 1. Thus, a stapled S_{2N} exists.

Theorem 3.8. There exist no stapled SSN of lengths N ≤ 16.

In other words, any SSN of length N ≤ 16 includes a member relatively prime with all other members.

Proof. It follows from Lemmata 3.6 and 3.7 that it is sufficient to prove the theorem for N = 15 and N = 9.

For N = 15, note that if there exists a stapling covering of [1,15] where a_{2} = 2, h(2) = 2, then there exists a stapling covering of [2,16] with a_{2} = 2, h(2) = 1. Thus it is sufficient to show that no such stapling covering of [2,16] exists.

Suppose first that a_{3} = 3. Then each of A_{5}, A_{7}, A_{11} can cover only one of the numbers 5,7,11,13, and A_{13} can cover none. Thus, a_{3} = 5 or a_{3} = 7. Because of “mirror image” symmetry, it is enough to consider a_{3} = 5. Now, 3,7,9,13,15 remain to be covered, and A_{5} must cover two of them. Hence a_{5} = 3. Then neither 7 nor 9 can be covered by A_{11} or A_{13}, and both of them cannot be covered simultaneously by A_{7}, thereby making stapling covering impossible. Thus no stapling covering of length 15 exists.

For N = 9 it is readily seen that A_{2} can cover either four or five numbers. If A_{2} covers four numbers, then A_{3}, A_{5} and A_{7} can cover not more than two numbers, one number, and one number, respectively, out of five remaining numbers, thus, leaving one number not covered. If A_{2} covers five numbers, then the only way to cover two numbers with A_{3} is to choose h(3) = 2. However, since A_{7} cannot cover 4 or 6, again one number is left not covered. Thus, stapling coverings do not exist for N = 9, which completes the proof.

For N = 17 there exist only two different stapling coverings which are mirror images of each other. One is given by first indicators (1,2,1,3,1,4) (i.e., h_{1} = h(2) = 1, h_{2} = h(3) = 2, …, h_{6} = h(13) = 4). The other is given by (1,1,2,1,6,1) (Cf. example in Sec. 2). It follows then, by Lemmata 3.6 and 3.7, that stapling coverings exist for 17 ≤ N ≤ 21. It is remarkable that, as computer calculations show, it is possible to extend the stapling covering given by (1,2,1,3,1,4) to the right in order to construct stapling coverings up to N ≤ 4 · 10^{7}, and, most probably, for all larger N. More exactly, the procedure is the following. We start with stapling covering for S_{17} ∈ [1, 17] given by the set of prime congruences with first indicators (1,2,1,3,1,4). At each step we go from S_{N} = [1, N] to S_{N+1} = [1, N +1] and check whether the last number N + 1 is covered by at least one of the prime congruences used in the stapling covering of S_{N}. If this is not so, we use the smallest unused prime number p < N + 1 to cover N + 1 and add the prime congruence A_{p} to the set W_{I}. This approach, however, does not work if one starts with the set of congruences given by first indicators (1,1,2,1,6,1): this set cannot be extended for N = 25.

In fact, as shown below, stapling coverings exist for all N ≥ 17.

4 Efficient Stapling Coverings

An interesting characteristic of stapling covering is the ratio of the number | I | of primes used for the covering to the total number π(N) of primes not exceeding N.

Definition 4.1. The expense ε(T) of a stapling covering T (S_{N}, W_{I}) is the ratio ε(T) = \frac{|I|}{π(N)}.

Stapling coverings with expense substantially smaller than 1 are called efficient.

Another related characteristic is cutoff.

Definition 4.2. The cutoff u(T) of a stapling covering T (S_{N}, W_{I}) is the ratio of the greatest prime p_{i}, i ∈ I to N.

It is easy to see that the coverings with the small cutoff are efficient. It is an interesting open problem though to show that efficient stapling coverings can always be transformed into coverings of small cutoff.

It is worth to note that the simple approach described in the Sec. 3 yields rather efficient stapling coverings for large N. The expense ε(T) decreases with N from \frac{π(N)−1}{π(N)} = \frac{6}{7} for N = 17 to approximately 0.62 for N = 4 · 10^{7}. However, if N is sufficiently large, stapling coverings with substantialy smaller expense and cutoff become possible. The construction given by Brauer [1] uses a sequence of integers S_{N} which is symmetric with respect to zero and achieves u(T) = 1/2. The use of symmetry, however, may be inconvenient in some related problems. Therefore, we provide a construction that yields u(T) = 1/2 without use of symmetry.

Lemma 4.1. Consider the set Q = {2^{s}3^{t} | s, t ∈ ℕ, 2^{s}3^{t} ≤ N}. Then | Q |≤ \frac{1}{2} log_{2} N(log_{3} N − 1) for any N ≥ 9.

Proof of Lemma 4.1 is given in Appendix B.

Theorem 4.2. There exists a stapling covering T = T (S_{N}, W_{I}) for all N such that

π(⌊\frac{N}{2} ⌋) − π(⌊\frac{N}{4} ⌋) ≥ log_{2} N · log_{3} N  (4.1)

The covering has the property that p_{i} ≤ \frac{N}{2} for all i ∈ I and lim_{N→∞}ε(T) ≤ \frac{3}{8}.

Proof. Let p_{i} be the i-th prime number: p_{1} = 2, p_{2} = 3, etc. Consider the following procedure of covering the sequence S_{N} = (1, 2, …, N).

1. h_{i} = p_{i} for all p_{i} ≤ \frac{N}{4} , p_{i} ≠ 2, 3.

2. h_{1} = h(2) = 1.

3. Denote:

P_{1} = \{p_{i} | 2p_{i} ≡ 1 ( mod 3), \frac{N}{4} < p_{i} ≤ \frac{N}{2} \}

P_{2} = \{p_{i} | 2p_{i} ≡ 2 ( mod 3), \frac{N}{4} < p_{i} ≤ \frac{N}{2} \}

D_{1} = {2^{2k} | k ∈ ℕ, 2k ≤ log_{2} N}

D_{2} = {2^{2k−1} | k ∈ ℕ, 2k − 1 ≤ log_{2} N}

Choose

h_{2} = h(3) = \{ \begin{matrix}1, & if | P_{1} | + | D_{1} |≥| P_{2} | + | D_{2} | \\ 2, & otherwise \end{matrix}

4. h_{i} = p_{i}, if h(3) = 1 and p_{i} ∈ P_{2}, or if h(3) = 2 and p_{i} ∈ P_{1}.

5. Denote: Q = {2^{s}3^{t} | s, t ∈ ℕ, 2^{s}3^{t} ≤ N}

If h(3) = 1, use members of P_{1} to cover as many as possible members of D_{2} ⋃ Q.

If h(3) = 2, use members of P_{2} to cover as many as possible members of D_{1} ⋃ Q.

(It will be shown below that under condition (4.1) it is possible to cover all members of D_{2} ⋃ Q or D_{1} ⋃ Q, respectively).

Note that since p ≤ \frac{N}{2} if p ∈ P_{1} or p ∈ P_{2}, | S_{N} ⋂ A_{p} |≥ 2 for any choice of h(p). As a result, we obtain a prime tiling T (S_{N}, W_{I}), which satisfies the stapling condition (2.1). In this tiling, A_{2} covers all odd numbers, A_{3} covers all even numbers belonging to 2P_{1} ⋃ D_{1}, if h(3) = 1, or to 2P_{2} ⋃ D_{2}, if h(3) = 2. All other even numbers, except members of D_{2} ⋃ Q, if h(3) = 1, or D_{1} ⋃ Q, if h(3) = 2, are covered by “unmoved” prime numbers for which h_{i} = p_{i}. It remains to show that the set P_{1} (respectively, P_{2}) is large enough to cover all members of D_{2} ⋃ Q (respectively, D_{1} ⋃ Q).

Without loss of generality, assume that h(3) = 1 and, thus | P_{1} | + | D_{1} |≥ | P_{2} | + | D_{2} |. Then | P_{1} | − | D_{2} |≥| P_{2} | − | D_{1} |. Since | P_{1} | + | P_{2} |= π(⌊\frac{N}{2} ⌋) − π(⌊\frac{N}{4} ⌋), and | D_{1} | + | D_{2} |= ⌊log_{2} N⌋ , it follows that

| P_{1} | − | D_{2} |≥ \frac{1}{2}[π(⌊\frac{N}{2} ⌋) − π(⌊\frac{N}{4} ⌋) − log_{2} N]  (4.2)

By lemma 4.1,

| Q |≤ \frac{log_{2} N(log_{3} N − 1)}{2}  (4.3)

Now, taking into account (4.1), (4.2) and (4.3), we obtain:

| P_{1} |≥ \frac{1}{2}[π(⌊\frac{N}{2} ⌋) − π(⌊\frac{N}{4} ⌋) − log_{2} N]+ | D_{2} |

≥ \frac{1}{2}(log_{2} N log_{3} N − log_{2} N)+ | D_{2} |≥| Q | + | D_{2} |=| D_{2} ⋃ Q | (4.4)

Thus, condition (4.1) guarantees that the obtained prime tiling is a stapling covering. Since

\frac{1}{2}[π(⌊\frac{N}{2} ⌋) − π(⌊\frac{N}{4} ⌋) − log_{2} N] ≥ \frac{N}{4 ln N}

(cf. [12]), condition (4.1) is fulfilled for sufficiently large N. Furthermore, for large N the expense approaches \frac{3}{8}. Indeed, using the Prime Number Theorem ([12], p.36), we obtain

ε(T) =  \frac{|I|}{π(N)} ≤ \frac{1}{π(N)}[π(⌊\frac{N}{4} ⌋) + \frac{1}{2}(π(⌊\frac{N}{2} ⌋) −
π(⌊\frac{N}{4} ⌋) + log_{2} N log_{3} N)] = \frac{3}{8} + \frac{ln 2}{2 ln N} + O(\frac{ln^{3} N}{N})  (4.5)

It follows from the Prime Number Theorem that inequality (4.1) is fulfilled for all sufficienly large N. Computer test shows that (4.1) is valid for all N ≥ 2098 and the above algorithm works for all N ≥ 1618.

Corollary 4.3. Stapled sequences of natural numbers exist for all N ≥ 17.

Proof. Follows from the results of Sec. 3 and Theorem 4.2.

The construction given in the Theorem 4.2 can be amended by choosing properly indicators for other small prime numbers in order to lower expense and cutoff. However, the same goal can be achieved easier by use of symmetry (somewhat similar to Brauer’s approach).

Lemma 4.4. Let

G = \{x | x = ±2^{s}3^{t}5^{v}, | x |≤ \frac{N}{2} ; s∈ℤ; t, v ∈ℕ ∪ 0; x≡2( mod 3)\} (4.6)

Then

| G |< \frac{1}{3} log_{2} \frac{N}{2} log_{3} \frac{N\sqrt{5}}{2} log_{5} \frac{5N}{2} + 1  (4.7)

Proof of Lemma 4.4 is given in Appendix C.

Theorem 4.5. There exists a stapling covering T = T (S_{N}, W_{I}) for all N such that

π(⌊\frac{N}{4} ⌋) − π(⌊\frac{N}{8} ⌋) ≥ \frac{4}{3} log_{2} \frac{N}{2} · log_{3} \frac{N\sqrt{5}}{2} · log_{5} \frac{5N}{2}  (4.8)

which has the property that p_{i} ≤ \frac{N}{4} for any i ∈ I and lim_{N→∞}ε(T) ≤ \frac{7}{32}.

Proof. Let p be a prime number, p ≤ N. Consider the following procedure of covering the sequence

S_{N} = (−⌊\frac{N − 1}{2}⌋, −⌊\frac{N − 1}{2}⌋ + 1, …, −1, 0, 1, …, ⌊\frac{N}{2} ⌋).  (4.9)

1. Choose: a_{2} = 1; a_{3} = 1.

2. Denote:

P = \{p | \frac{N}{8} < p ≤ \frac{N}{4} \} R_{a_{5}} = \{p | \{2p, −2p\} ⊂ A_{3}^{1} ∪ A_{5}^{a_{5}}, \frac{N}{8} < p ≤ \frac{N}{4} \} Since for any p either 2p or −2p is covered by A_{3}^{1}, and the other element of the pair {2p, −2p} belongs to one of the sets R_{a_{5}} (a_{5} = 1, 2, 3, 4), ⋃_{a_{5}}R_{a_{5}} = P, and, therefore, there exists a_{5} = b, such that

| R_{b} |≥ \frac{1}{4} | P |= \frac{1}{4}[π(⌊\frac{N}{4} ⌋) − π(⌊\frac{N}{8} ⌋)]  (4.10)

Choose a_{5} = b; Note that now all primes belonging to R_{b} are free, that is, all their multiples belonging to S_{N} are covered by other prime congruences. Therefore these primes can be shifted to cover other numbers.

3. Let H = {x | x = ±2^{s}3^{t}5^{v}; s, t, v ∈ ℕ ∪ 0; | x |≤ N/2; x ∉ A_{2}^{1} ∪ A_{3}^{1} ∪ A_{5}^{b}} Members of H remain not covered after 2, 3, and 5 have been shifted. Fortunately, this set is rather small: it is not difficult to show that

| H |≤| G | −1 for any N ≥ 16  (4.11)

Hence, by lemma 4.4,

| H |< \frac{1}{3} log_{2} \frac{N}{2} · log_{3} \frac{N\sqrt{5}}{2} · log_{5} \frac{5N}{2}  (4.12)

Since π(N) ∼ \frac{N}{ln N}, by the Prime Number Theorem, for sufficiently large N,

| R_{b} |≥ \frac{1}{4}[π(⌊\frac{N}{4} ⌋) − π(⌊\frac{N}{8} ⌋)] ≥ \frac{1}{3} log_{2} \frac{N}{2} · log_{3} \frac{N\sqrt{5}}{2} · log_{5} \frac{5N}{2} >| H |

(4.13)

4. Choose D ⊆ R_{b} such that | D |=| H | and let f : D → H be a bijection. Take a_{p} = q, where q = f(p), if p ∈ D, and a_{p} = 0 for all p ≤ \frac{N}{4} , p ∉ D ∪ {2, 3, 5}.

As a result, we have obtained a stapling covering of the sequence S_{N} (4.9) which uses only prime numbers p ≤ \frac{N}{4} .

Since

lim_{N→∞} \frac{| H |}{π(N)} = 0, lim_{N→∞} \frac{| R_{b} |}{π(N)} ≥ \frac{1}{32}, and lim_{N→∞} \frac{π(\frac{N}{4} )}{π(N)} = \frac{1}{4},

it follows that lim_{N→∞} ε(N) ≤ \frac{7}{32}.

As seen from 4.13 this algorithm works for all N such that

π(⌊\frac{N}{4} ⌋) − π(⌊\frac{N}{8} ⌋) ≥ \frac{4}{3} log_{2} \frac{N}{2} · log_{3} \frac{N\sqrt{5}}{2} · log_{5} \frac{5N}{2}  (4.14)

The constructions given in Theorems 4.2, 4.5 can generate exponentially large (in N) number of different stapling coverings.

In the first draft of this paper the author conjectured, that for any δ > 0 there exist stapling coverings that do not use moduli greater than δN. According to P. Erdös [7] this is indeed true and follows from his theorem in [6]. We quote the theorem here:

Theorem 4.6. For a certain positive constant c_{2}, we can find c_{2}p_{n} log p_{n}/(log log p_{n})^{2} consecutive integers so that no one of them is relatively prime to the product p_{1}p_{2} ⋯ p_{n}, i.e. each of these integers is divisible by at least one of the primes p_{1}, p_{2}, ⋯, p_{n}.

(Here log stands for the natural logarithm).

Using this fact it can be readily proved that our conjecture holds, i.e. the following theorem is true:

Theorem 4.7. For every δ > 0 there exists N(δ) such that for any N > N(δ) there is a stapled sequence of length N which has a stapling covering with the largest modulus less than δN.

Proof. Let p_{m} be the smallest prime such that

\frac{(ln ln p_{m})^{2}}{c_{2} ln p_{m}} ≤ \frac{δ}{2}  (4.15)

Denote

⌊\frac{c_{2}p_{m} ln p_{m}}{(ln ln p_{m})^{2}} ⌋ = N(δ)  (4.16)

Let N > N(δ), and p_{n} be the smallest prime such that

\frac{c_{2}p_{n} ln p_{n}}{(ln ln p_{n})^{2}} ≥ N  (4.17)

Then, p_{n} > p_{m}, and, therefore, p_{n−1} ≥ p_{m}. Since \frac{(ln ln p_{i})^{2}}{c_{2} ln p_{i}} decreases monotonically as p_{i} grows, it follows from (4.15) that

\frac{(ln ln p_{n−1})^{2}}{c_{2} ln p_{n−1}} ≤ \frac{δ}{2}  (4.18)

Hence, by (4.17),

p_{n−1} ≤ \frac{δN}{2}

.

As well known, p_{n} < 2p_{n−1}. Thus, p_{n} < δN.

It follows from (4.17) and theorem 4.6 that there exists a sequence S_{N} of N consecutive natural numbers such that each of them is divisible by at least one of the primes p_{1}, p_{2}, …, p_{n}. Thus, S_{N} is a stapled sequence with the cutoff u < δ.

This result, however, does not provide an efficient algorithm for constructing such a sequence.

In fact, it is possible, by a slight modification of the proof (namely, choosing p_{m} such that \frac{(ln ln p_{m})^{3}}{c_{2} ln p_{m}} ≤ \frac{δ}{2}), to prove that p_{n} ≤ O(\frac{N}{ln ln N}).

Corollary 4.8. For any n ∈ ℕ there exists N(n) such that for any N > N(n) there exists an n-stapling covering.

Proof. Take δ = \frac{1}{n}. Then the result follows from Theorem 4.7.

Theorem 4.7 provides a basis for a stronger and more general result obtained in [8].

5 Open Problems

The concepts of stapled sequences and stapling coverings introduced and discussed above lead to some unsolved problems, as follows.

1. What is the exact relationship of cutoff and expense? Can we find a function f(ε) = min_{ε(T)=ε}u(T) and an algorithm that allows us to transform

a stapling covering of a given expense into a stapling covering with the cutoff u(T) = f(ε)?

2. Do there exist constructions for efficient stapling coverings of any cutoff u(T) > 0 that start working for reasonable values of N? For example, the construction obtained using Erdös’ result, even for u(T) = 0.5, starts working only for values of N > 10^{1000}. The algorithm in this paper provides such construction for the values of u(T) = \frac{7}{32} + ε that starts working for N of order of 10^{4}, but its generalization for any u(T) > 0 seems to be cumbersome.

Acknowledgments

The author would like to thank Prof. Paul Erdös and Prof. Ricard K. Guy for providing important references to relevant work. She is also grateful to Prof. Peter Gacs for his invariable support and advice, to Dr. David Bernstein for interest and encouragement, to Prof. Heiko Harborth for his interest in n-stapling coverings, and to Prof. Lev B. Levitin for useful discussions and comments. Special thanks are due to the referee for carefully reading the paper and suggesting thoughtful improvements and to Prof. Herbert S. Wilf for valuable advice.

References

[1] Alfred Brauer On a Property of k Consecutive Integers. Bull. Amer. Math. Society, vol. 47, 1941, pp. 328-331.

[2] Ronald J. Evans On Blocks of N Consecutive Integers. Amer. Math. Monthly, vol. 76, 1969, pp.48-49.

[3] Ronald J. Evans On N Consecutive Integers in an Arithmetic Progression. Acta Sci. Math. Univ. Szeged, vol. 33, 1972, pp. 295-296.

[4] Paul Erdös, personal communication.

[5] Paul Erdös, Some remarks on Number Theory. Israel Journal of Mathematics, vol.3, 1965, pp. 6-12.

[6] Paul Erdös, On the Difference of Consecutive Primes. Quarterly Journal of Mathematics, vol.6, 1935, pp. 124-128.

[7] Paul Erdös, personal communication.

[8] Irene Gassko Stapling Coverings of Natural Numbers Without Small Primes. Preprint.

[9] Ricard K. Guy Unsolved Problems in Number Theory. Springer-Verlag, New-York - Heidelberg - Berlin, 1981.

[10] Heiko Harborth Eine Eigenschaft Aufeinanderfolgender Zahlen. Arch. Math. (Basel), vol. 21, 1970, pp.50-51.

[11] Heiko Harborth Sequenzen Ganzer Zahlen. Zahlentheorie, Berichte aus dem Math. Forschungsinst. Oberwolfach, vol. 5, 1971, pp. 59-66.

[12] A.E. Ingham The Distibution of Prime Numbers. Cambridge University Press, Cambridge, 1990.

[13] S.S Pillai On m Consecutive Integers I, Proc. Indian Acad. Sci., Sect. A, vol. 11, 1940, pp.6-12; MR 1, 199; II ibid., vol. 11, 1940, pp.73-80, III ibid, vol.13, 1941, pp.530-533; MR 3, 66; IV Bull. Calcutta Math. Soc. 36, 1944, pp. 99-101; MR 6, 170.

Appendix

A Proofs of Lemmata 3.1, 3.2, 3.3.

Lemma 3.1. If S_{N}^{0} is a stapled SSN and T (S_{N}^{0}, W_{I}^{0}) is the corresponding stapling covering, there exists stapling covering T ([1, N], W_{I}) such that s_{h_{i}} = h_{i} = h_{i}^{0} for any i ∈ I, s_{h_{i}} ∈ [1, N].

Proof. Let S_{N}^{0} = (s_{1}^{0}, s_{2}^{0}, …, s_{N}^{0}), h_{i}^{0} be the first indicator of A_{p_{i}}^{0} in S_{N}^{0}. Since T (S_{N}^{0}, W_{I}^{0}) is a stapling covering, s_{h_{i}^{0}+p_{i}}^{0} ∈ S_{N}^{0}, hence h_{i}^{0} + p_{i} ≤ N. Consider now W_{I} = {A_{p_{i}}}, where A_{p_{i}} = {h_{i}^{0} + mp_{i}}, m ∈ ℤ. Obviously h_{i}^{0} ∈ A_{p_{i}}, h_{i}^{0} + p_{i} ∈ A_{p_{i}} and h_{i}^{0} + p_{i} ≤ N for any i ∈ I. Moreover, since for any k ∈ [1, N] there exists A_{p_{i}}^{0} such that s_{k}^{0} = s_{r_{i}}^{0} ∈ A_{p_{i}}^{0}, it follows that k = r_{i} ∈ A_{p_{i}}. Thus T ([1, N], W_{I}) is a stapling covering and s_{h_{i}} = h_{i} = h_{i}^{0}, i ∈ I are the first indicators.

Lemma 3.2. If T (S_{N}, W_{I}) is a stapling covering, then there exists a stapled SSN S_{N}^{0} of length N .

Proof. Let A_{p_{i}} = {a_{p_{i}} + mp_{i}}, where a_{p_{i}} ∈ ℤ_{p_{i}}, m ∈ ℤ, i ∈ I. Take number M ∈ ℕ, such that M ≡ −a_{p_{i}} ( mod p_{i}) for any i ∈ I. Such a number exists according to the Chinese Remainder Theorem. Let s_{k}^{0} = s_{k} +M (k ∈ [1, N]) and define S_{N}^{0} as S_{N}^{0} = (s_{1}^{0}, s_{2}^{0}, …, s_{N}^{0}). Obviously, if s_{k} ∈ A_{p_{i}}, then s_{k}^{0} ∈ A_{p_{i}}^{0} for any k ∈ [1, N] and for any i ∈ I. Hence, T (S_{N}^{0}, W_{I}^{0}) is a stapling covering and h_{i} = h_{i}^{0} for any i ∈ I. Thus, S_{N}^{0} is a stapled SSN of length N.

Lemma 3.3. S_{N} ∼ S′_{N} (resp W_{I}) iff s′_{k} ≡ s_{k} ( mod ∏_{i∈I} p_{i}) , ∀k ∈

[1, N] = (1, 2, …, N), s_{k} ∈ S_{N}, s′_{k} ∈ S′_{N}.

Proof. If s′_{k} ≡ s_{k} ( mod ∏_{i∈I} p_{i}) , then, obviously, s_{k} ∈ A_{p_{i}} iff s′_{k} ∈ A_{p_{i}}.

Thus, h_{i} = h′_{i} for any i ∈ I. Conversely, if h_{i} = h′_{i} for any i ∈ I, then s_{h_{i}} ≡ s′_{h_{i}}( mod p_{i}) for any i ∈ I . Since s_{k} − s_{h_{i}} = s′_{k} − s′_{h_{i}} = k − h_{i} for any k ∈ [1, N], it follows that s′_{k} ≡ s_{k}( mod p_{i}) for any i ∈ I, and, therefore,

s′_{k} ≡ s_{k}( mod ∏_{i∈I} p_{i}).

B Proof of Lemma 4.1.

Lemma 4.1. Consider the set Q = {2^{s}3^{t} | s, t ∈ ℕ, 2^{s}3^{t} ≤ N}. Then | Q |≤ \frac{1}{2} log_{2} N(log_{3} N − 1) for any N ≥ 9.

Proof Obviously,

| Q |= ∑_{k=1}^{v}⌊log_{2} \frac{N}{3^{k}} ⌋,  (B.1)

where v = ⌊log_{3} N⌋ Let

log_{2} \frac{N}{3^{k}} − ⌊log_{2} \frac{N}{3^{k}} ⌋ = ε,  (B.2)

and

log_{2} \frac{N}{3^{k+1}} − ⌊log_{2} \frac{N}{3^{k+1}} ⌋ = δ,  (B.3)

where 0 ≤ ε < 1, 0 ≤ δ < 1.

Suppose 2^{m} ≤ \frac{N}{3^{k}} < 2^{m+1}.

Then

log_{2} \frac{N}{3^{k}2^{m}} = ε,

and

δ = log_{2} \frac{N}{3^{k+1}2^{m−h}} = ε − log_{2} 3 + h,

where h is an integer such that 0 ≤ δ < 1. Hence, if ε ∈ [0, log_{2} 3 − 1), then h = 2; if ε ∈ [log_{2} 3 − 1, 1), h = 1. Thus

δ = \{ \begin{matrix}2 + ε − log_{2} 3, & 0 ≤ ε < log_{2} 3 − 1 \\ 1 + ε − log_{2} 3, & log_{2} 3 − 1 ≤ ε < 1 \end{matrix}  (B.4)

It is easy to infer from (B.4) that min_{0≤ε<1}(ε + δ) = 2 − log_{2} 3.

Therefore,

∑_{k=1}^{v}(log_{2} \frac{N}{3^{k}} − ⌊log_{2} \frac{N}{3^{k}} ⌋) ≥ ⌊\frac{v}{2}⌋(2 − log_{2} 3)  (B.5)

On the other hand,

∑_{k=1}^{v} log_{2} \frac{N}{3^{k}} = v(log_{2} N − \frac{v + 1}{2} log_{2} 3)

Denote: log_{3} N − v = α. Then

∑_{k=1}^{v} log_{2} \frac{N}{3^{k}} = \frac{1}{2} log_{2} N log_{3} N − \frac{1}{2} log_{2} N + (\frac{α}{2} − \frac{α^{2}}{2} ) log_{2} 3  (B.6)

But \frac{1}{2} log_{2} 3α(1 − α) ≤ \frac{1}{8} log_{2} 3. Hence,

∑_{k=1}^{v} log_{2} \frac{N}{3^{k}} ≤ \frac{1}{2} log_{2} N(log_{3} N − 1) + \frac{1}{8} log_{2} 3  (B.7)

From (B.5) and (B.7), we obtain:

∑_{k=1}^{v}⌊log_{2} \frac{N}{3^{k}} ⌋ ≤ \frac{1}{2} log_{2} N(log_{3} N − 1) − ⌊\frac{v}{2}⌋(2 − log_{2} 3) + \frac{1}{8} log_{2} 3 (B.8)

Finally, for v ≥ 2, i.e. for N ≥ 9, it follows that

| Q |≤ \frac{log_{2} N(log_{3} N − 1)}{2}  (B.9)

which proves Lemma 4.1. Further analysis of expressions (B.5) and (B.6) allows us to obtain a

stronger inequality:

| Q |≤ \{ \begin{matrix}\frac{1}{2}[log_{2} N(log_{3} N − 2) + log_{3} 2 − log_{2} 3] & if ⌊log_{3} N⌋ is even \\ \frac{1}{2}[log_{2} N(log_{3} N − 2) + log_{3} 2 − log_{2} 3] + 1 & if ⌊log_{3} N⌋ is odd \end{matrix}

C Proof of Lemma 4.4.

Lemma 4.4 Let

G = \{x | x = ±2^{s}3^{t}5^{v}, | x |≤ \frac{N}{2} ; s∈ℕ; t, v ∈ℕ ∪ 0; x≢1 ( mod 3)\} (C.1)

Then

| G |< \frac{1}{3} log_{2} \frac{N}{2} log_{3} \frac{N\sqrt{5}}{2} log_{5} \frac{5N}{2} + 1  (C.2)

Proof Denote Z(n) = {±2^{s}3^{t} | 2^{s}3^{t} ≤ n; n, s, t ∈ ℕ} ∪ Y (n), where Y (n) = {y | y = ±2^{s}, | y |≤ n, s ∈ ℕ, y ≡ 2( mod 3)}.

Since exactly one of two numbers, 2^{s} or −2^{s}, belongs to Y (n), | Y (n) | = ⌊ log_{2} n ⌋. By Lemma 4.1,

| Z(n) |≤ log_{2} n(log_{3} n − 1) + ⌊log_{2} n⌋ ≤ log_{2} n log_{3} n  (C.3)

By Lemma 4.1, (C.3) is valid for n ≥ 9. However, direct checking shows that (C.3) is valid for all n ≥ 3. For n = 2, |Z(2)| − log_{2} 2 log_{3} 2 = 1 − log_{3} 2.

Obviously,

| G |= ∑_{k=0}^{w} | Z(⌊\frac{N}{2 · 5^{k}} ⌋) |≤ ∑_{k=0}^{w} log_{2} \frac{N}{2 · 5^{k}} log_{3} \frac{N}{2 · 5^{k}} + 1 − log_{3} 2, (C.4)

where w = ⌊log_{5} \frac{N}{2} ⌋.

Consider the integral

∫_{0}^{log_{5} \frac{N}{2}} log_{2} 5 log_{3} 5(log_{5} \frac{N}{2} − x)^{2} dx = \frac{1}{3} log_{2} \frac{N}{2} log_{3} \frac{N}{2} log_{5} \frac{N}{2}  (C.5)

On the other hand,

∫_{0}^{log_{5} \frac{N}{2}} log_{2} 5 log_{3} 5(log_{5} \frac{N}{2} − x)^{2} dx = ∑_{k=0}^{w} ∫_{k−1}^{k} \frac{N}{2} log_{2} 5 log_{3} 5(log_{5} \frac{N}{2} − x)^{2} dx +

∫_{w}^{log_{5} \frac{N}{2}} log_{2} 5 log_{3} 5(log_{5} \frac{N}{2} − x)^{2} dx = ∑_{k=0}^{w}[log_{2} \frac{N}{2 · 5^{k}} log_{3} \frac{N}{2 · 5^{k}} + log_{2} 5 log_{3} \frac{N}{2 · 5^{k}}

+\frac{1}{3} log_{2} 5 log_{3} 5 + \frac{1}{3} log_{2} 5 log_{3} 5(log_{5} \frac{N}{2} − w)^{3}  (C.6)

the electronic journal of combinatorics 3 (1996), #R33 20

It follows from (C.3),(C.4), and (C.6), that

| G | ≤ \frac{1}{3} log_{2} \frac{N}{2} log_{3} \frac{N}{2} log_{5} \frac{N}{2} + log_{2} \frac{N}{2} log_{3} \frac{N}{2} − w(log_{3} \frac{N}{2} − \frac{w + 1}{2} log_{3} 5) log_{2} 5
−\frac{w}{3} log_{2} 5 log_{3} 5 − \frac{1}{3} log_{2} 5 log_{3} 5(log_{5} \frac{N}{2} − w)^{3} + 1 − log_{3} 2  (C.7)

Denote log_{5} \frac{N}{2} − w = β; 0 ≤ β < 1. Then

| G | ≤ \frac{1}{3} log_{2} \frac{N}{2} log_{3} \frac{N}{2} log_{5} \frac{N}{2} + \frac{1}{2} log_{2} \frac{N}{2} log_{3} \frac{N}{2} + \frac{1}{6} log_{2} \frac{N}{2} log_{3} 5 −
log_{2} 5 log_{3} 5(\frac{1}{6}β − \frac{1}{2}β^{2} + \frac{1}{3}β^{3}) + 1 − log_{3} 2  (C.8)

It is easy to show that

min_{0≤β<1}(\frac{1}{6}β − \frac{1}{2}β^{2} + \frac{1}{3}β^{3}) = −\frac{1}{36\sqrt{3}}  (C.9)

Thus

| G | ≤ \frac{1}{3} log_{2} \frac{N}{2} log_{3} \frac{N\sqrt{5}}{2} log_{5} \frac{5N}{2} + \frac{log_{2} 5 log_{3} 5}{36\sqrt{3}} + 1 − log_{3} 2
< \frac{1}{3} log_{2} \frac{N}{2} log_{3} \frac{N\sqrt{5}}{2} log_{5} \frac{5N}{2} + 1,  (C.10)

which proves Lemma 4.4.