

A090318


a(n) = least positive k such that k, k+1, k+2, ... k+n1 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(n1) = (n1)#. [From Max Alekseyev, Oct 08 2007]


REFERENCES

I. Gassko, Common factor graphs of stapled sequences, Proceedings of the Twentyeighth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1997). Congr. Numer. 126 (1997), 163173.
I. Gassko, Stapling and composite coverings of natural numbers, Proceedings of the Twentyseventh Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 1996). Congr. Numer. 118 (1996), 109116.
H. L. Nelson, There is a better sequence, Journal of Recreational Mathematics, Vol. 8(1), 1975, pp. 3943.


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. 328331.
R. B. Eggleton, Common factors of integers: A graphic view, Discrete Math. 65 (1987), 141147.
R. J. Evans, On Blocks of N Consecutive Integers, Amer. Math. Monthly, vol. 76, 1969, pp. 4849.
R. J. Evans, On N Consecutive Integers in an Arithmetic Progression, Acta Sci. Math. Univ. Szeged, vol. 33, 1972, pp. 295296.
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. 323347.
Heiko Harborth, Eine Eigenschaft Aufeinanderfolgender Zahlen, Arch. Math. (Basel), vol. 21, 1970, pp. 5051.
S. S. Pillai, On m Consecutive Integers I, Proc. Indian Acad. Sci., Sect. A, vol. 11, 1940, pp. 612; II ibid., vol. 11, 1940, pp. 7380, III ibid, vol. 13, 1941, pp. 530533; IV Bull. Calcutta Math. Soc. 36, 1944, pp. 99101.


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]] (* JeanFranç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 tsp(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;
}
/* Max Alekseyev, Oct 08 2007 */


CROSSREFS

Cf. A130170, A130171, A130173.
Sequence in context: A206057 A130173 A130170 * A130171 A194585 A107657
Adjacent sequences: A090315 A090316 A090317 * A090319 A090320 A090321


KEYWORD

nonn,nice


AUTHOR

William Rex Marshall, Jan 25 2004


EXTENSIONS

Edited by N. J. A. Sloane, Aug 04 2007, Oct 08 2007


STATUS

approved



