1,17

A finite sequence of n consecutive positive integers is called "stapled" if each element in the sequence is not relatively prime to at least one other element in the sequence. Thus a staple joins two terms of the sequence whose gcd is > 1.

It has been proved that stapled intervals of length n >= 17 exist for all n.

Comments from Max Alekseyev (maxale(AT)gmail.com), Jul 24 2007: (Start)

An interval is stapled if for every element x there is another element y (different from x) such that gcd(x,y)>1.

The shortest stapled interval has length 17 and starts with the number 2184.

It is interesting to notice that the intervals [27829,27846] and [27828,27846] are stapled while the interval [27828,27845] is not.

It is clear that a stapled interval [a,b] may not contain a prime number greater than b/2 (as such a prime would be coprime to every other element of the interval).

Together with Bertrand's Postulate this implies a>b/2 or b<2a. And it follows that

* a stapled interval may not contain prime numbers at all;

* for any particular positive integer a, we can determine if it is a starting point of some stapled interval. (End)

a(58) > 10^9. For n>=17, a(n) < A034386(n-1) = (n-1)#. - Max Alekseyev, Oct 08 2007

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

R. B. Eggleton, Discrete Math. 65 (1987), 141-147.

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

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

I. Gassko, Common factor graphs of stapled sequences, Proceedings of the Twenty-eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1997). Congr. Numer. 126 (1997), 163-173.

I. Gassko, Stapling and composite coverings of natural numbers, Proceedings of the Twenty-seventh Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 1996). Congr. Numer. 118 (1996), 109-116.

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

H. L. Nelson, There is a better sequence, Journal of Recreational Mathematics, Vol. 8(1), 1975, pp. 39-43.

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

Max Alekseyev and William Rex Marshall, Table of n, a(n) for n = 1..103

I. Gassko, Stapled Sequences and Stapling Coverings of Natural Numbers, Electronic Journal of Combinatorics, Vol. 3, 1996, Paper R33.

The shortest possible stapled sequence is [2184, 2185, 2186, 2187, 2188, 2189, 2190, 2191, 2192, 2193, 2194, 2195, 2196, 2197, 2198, 2199, 2200]

(C++ program from Max Alekseyev, Oct 08 2007) For the current parameters it needs ~ 4GB of RAM to run smoothly.

It first precomputes the smallest prime divisor < 59 of each number below 10^9 and stores them in the array sp. Then uses these divisors to grow up from each particular n < 10^9 a stapled interval of the length at most 59. The records found are stored in the array L which is printed out at the end. It uses the following observations:

If a stapled interval contains a number t, then it also contains t-sp(t) or t+sp(t) or both.

If a stapled interval starts with n, n+1, ..., n+k then it must also contain the number m = max{ n + d + sp(n+d) : d=0..k, sp(n+d)>d }

Moreover, if m <= n+k, then the interval [n, n+k] is stapled.

#include <iostream>

#include <vector>

using namespace std;

#include <stdint.h>

#define D 59

#define N 1000000000ul

const uint32_t prime[16] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 };

int main() {

vector<uint32_t> sp(N+D);

vector<uint32_t> L(D);

for(int i=0; i<16; ++i) {

uint32_t p = prime[i];

for(uint32_t n=0; n<N+D; n+=p) {

if( sp[n]==0 ) sp[n] = p;

}

}

clog << "Init done\n";

for(uint32_t n=1; n<=N; ++n) {

uint32_t m = 1;

for(int d=0; d<D; ++d) {

uint32_t s = sp[n+d];

if(s==0) break;

if(s>d) m = max(m, d+s);

if(d>=m && L[d]==0) L[d]=n;

}

}

for(int i=1; i<D; ++i) {

cout << i+1 << "\t" << L[i] << endl;

}

return 0;

}

Cf. A130170, A130171, A130173.

Sequence in context: A067263 A130173 A130170 this_sequence A130171 A107657 A002521

Adjacent sequences: A090315 A090316 A090317 this_sequence A090319 A090320 A090321

nonn,nice

William Rex Marshall (w.r.marshall(AT)actrix.co.nz), Jan 25 2004

Edited by N. J. A. Sloane (njas(AT)research.att.com), Aug 04 2007, Oct 08 2007