The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A090318 a(n) = least positive k such that k, k+1, k+2, ... k+n-1 is a stapled interval of length n, or 0 if no such sequence exists. 7
 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2184, 27829, 27828, 87890, 87890, 171054, 171054, 323510, 127374, 323510, 151062, 151062, 151062, 151061, 151060, 151059, 151058, 7106718, 7106718, 7567747, 7567746, 7567745, 7567744, 7567743, 7567742, 48595315, 48595314, 48595313 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,17 COMMENTS 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. From Max Alekseyev, 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) For n>=17, a(n) < A034386(n-1) = (n-1)#. [From Max Alekseyev, Oct 08 2007] REFERENCES 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. H. L. Nelson, There is a better sequence, Journal of Recreational Mathematics, Vol. 8(1), 1975, pp. 39-43. LINKS Max Alekseyev and William Rex Marshall, Table of n, a(n) for n = 1..103 A. Brauer, On a Property of k Consecutive Integers, Bull. Amer. Math. Society, vol. 47, 1941, pp. 328-331. R. B. Eggleton, Common factors of integers: A graphic view, 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. Irene Gassko, Stapled Sequences and Stapling Coverings of Natural Numbers, Electronic Journal of Combinatorics, Vol. 3, Paper R33. L. Hajdu and N. Saradha, On a problem of Pillai and its generalizations, Acta Arithmetica 144:4 (2010), pp. 323-347. Heiko Harborth, Eine Eigenschaft Aufeinanderfolgender Zahlen, Arch. Math. (Basel), vol. 21, 1970, pp. 50-51. 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. EXAMPLE The shortest possible stapled sequence is [2184, 2185, 2186, 2187, 2188, 2189, 2190, 2191, 2192, 2193, 2194, 2195, 2196, 2197, 2198, 2199, 2200] MATHEMATICA dd = 41; nn = 10^7; Clear[sp, L]; sp[_] = 0; L[_] = 0; For[ i = 0, i < PrimePi[dd], ++i, p = Prime[i + 1]; For[ n = 0, n < nn + dd, n += p, If[sp[n] == 0, sp[n] = p]]]; Print["init done"]; For[ n = 1, n <= nn, ++n, m = 1; For[ d = 0, d < dd, ++d, 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]] ]; Reap[For[ i = 1, i <= dd, ++i, Print["a[", i, "] = ", L[i - 1]]; Sow[L[i - 1]]]][[2, 1]] (* Jean-François Alcover, Mar 26 2013, translated and adapted from Max Alekseyev's program *) PROG (C++) /* 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 #include using namespace std; #include #define D 59 #define N 1000000000ul const uint32_t prime =     { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 }; int main() {     vector sp(N+D);     vector L(D);     for(int i=0; i<16; ++i) {         uint32_t p = prime[i];         for(uint32_t n=0; nd) m = max(m, d+s);             if(d>=m && L[d]==0) L[d]=n;         }     }     for(int i=1; i

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 16 02:14 EDT 2021. Contains 345055 sequences. (Running on oeis4.)