A090318 - OEIS

%I #51 May 16 2023 07:08:28

%S 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2184,27829,27828,87890,87890,171054,

%T 171054,323510,127374,323510,151062,151062,151062,151061,151060,

%U 151059,151058,7106718,7106718,7567747,7567746,7567745,7567744,7567743,7567742,48595315,48595314,48595313

%N 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.

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

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

%C From _Max Alekseyev_, Jul 24 2007: (Start)

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

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

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

%C 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).

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

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

%C * we can determine whether any particular positive integer a is a starting point of some stapled interval. (End)

%C For n >= 17, a(n) < A034386(n-1) = (n-1)#. - _Max Alekseyev_, Oct 08 2007

%D 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.

%D 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.

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

%H Max Alekseyev and William Rex Marshall, <a href="/A090318/b090318.txt">Table of n, a(n) for n = 1..103</a>

%H Ethan Berkove and Michael Brilleslyper, <a href="http://math.colgate.edu/~integers/w47/w47.pdf">Subgraphs of Coprime Graphs on Sets of Consecutive Integers</a>, Integers (2022) Vol. 22, #A47, see p. 8.

%H A. Brauer, <a href="http://dx.doi.org/10.1090/S0002-9904-1941-07455-0">On a Property of k Consecutive Integers</a>, Bull. Amer. Math. Society, vol. 47, 1941, pp. 328-331.

%H R. B. Eggleton, <a href="http://dx.doi.org/10.1016/0012-365X(87)90136-1">Common factors of integers: A graphic view</a>, Discrete Math. 65 (1987), 141-147.

%H R. J. Evans, <a href="http://www.jstor.org/stable/2316790">On Blocks of N Consecutive Integers</a>, Amer. Math. Monthly, vol. 76, 1969, pp. 48-49.

%H R. J. Evans, <a href="http://www.math.ucsd.edu/~revans/NConsecutive1972.pdf">On N Consecutive Integers in an Arithmetic Progression</a>, Acta Sci. Math. Univ. Szeged, vol. 33, 1972, pp. 295-296.

%H Irene Gassko, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v3i1r33">Stapled Sequences and Stapling Coverings of Natural Numbers</a>, Electronic Journal of Combinatorics, Vol. 3, Paper R33.

%H L. Hajdu and N. Saradha, <a href="http://www.math.unideb.hu/~hajdul/hsaafinal.pdf">On a problem of Pillai and its generalizations</a>, Acta Arithmetica 144:4 (2010), pp. 323-347.

%H Heiko Harborth, <a href="http://dx.doi.org/10.1007/BF01220876">Eine Eigenschaft Aufeinanderfolgender Zahlen</a>, Arch. Math. (Basel), vol. 21, 1970, pp. 50-51.

%H Jyhmin Kuo and Hung-Lin Fu, <a href="https://doi.org/10.11650/twjm/1500405731">On Near Relative Prime Number in a Sequence of Positive Integers</a>, Taiwanese J. Math. 14 (1) 123-129, 2010.

%H S. S. Pillai, <a href="https://www.ias.ac.in/article/fulltext/seca/011/01/0006-0012">On m Consecutive Integers I</a>, 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.

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

%t 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 *)

%o (C++)

%o /* For the current parameters it needs ~ 4GB of RAM to run smoothly.

%o It first precomputes the smallest prime divisor < 59 of each number below 10^9 and stores them in the array sp. It then uses these divisors to grow up from each particular n < 10^9 a stapled interval of 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:

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

%o 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 }.

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

%o #include <iostream>

%o #include <vector>

%o using namespace std;

%o #include <stdint.h>

%o #define D 59

%o #define N 1000000000ul

%o const uint32_t prime[16] =

%o     { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53 };

%o int main() {

%o     vector<uint32_t> sp(N+D);

%o     vector<uint32_t> L(D);

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

%o         uint32_t p = prime[i];

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

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

%o         }

%o     }

%o     clog << "Init done\n";

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

%o         uint32_t m = 1;

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

%o             uint32_t s = sp[n+d];

%o             if(s==0) break;

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

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

%o         }

%o     }

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

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

%o     }

%o     return 0;

%o }

%o /* _Max Alekseyev_, Oct 08 2007 */

%Y Cf. A130170, A130171, A130173.

%K nonn,nice

%O 1,17

%A _William Rex Marshall_, Jan 25 2004

%E Edited by _N. J. A. Sloane_, Aug 04 2007, Oct 08 2007