The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A059756 Erdős-Woods numbers: the length of an interval of consecutive integers with property that every element has a factor in common with one of the endpoints. 9


%S 16,22,34,36,46,56,64,66,70,76,78,86,88,92,94,96,100,106,112,116,118,

%T 120,124,130,134,142,144,146,154,160,162,186,190,196,204,210,216,218,

%U 220,222,232,238,246,248,250,256,260,262,268,276,280,286,288,292,296,298,300,302,306,310,316,320,324,326,328,330,336,340,342,346,356,366,372,378,382,394,396,400,404,406,408,414,416,424,426,428,430

%N Erdős-Woods numbers: the length of an interval of consecutive integers with property that every element has a factor in common with one of the endpoints.

%C "Length" means total number of terms including endpoints, minus 1.

%C Woods was the first to find such numbers, Dowe proved there are infinitely many and Cegielski, Heroult and Richard showed that the set is recursive.

%C This seems to coincide with prime partitionable numbers in sense of Holsztynski & Strube: n such that there is a partition {P1,P2} of the primes less than n such that for any composition n1+n2=n, there is (p1,p2) in P1 x P2 such that p1|n1 or p2|n2. - _M. F. Hasler_, Jun 29 2014; there is now a proof for this (see Gribble link), Dec 17 2014

%C In popular culture: this sequence was involved in the encryption of a message in Episode "eps2.9_pyth0n-pt1.p7z" of the "Mr. Robot" TV series (first aired Sep 14 2016). - _Jessica K. Sklar_, Jan 30 2019

%D R. K. Guy: Unsolved Problems in Number Theory, 1981, related to Sections B27, B28, B29.

%D Konstantin Lakkis, Number Theory [in Greek], Revised edition, 1984.

%H P. Cegielski, F. Heroult, D. Richard, <a href="http://dx.doi.org/10.1016/S0304-3975(02)00444-9">On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity</a>, Theor. Comp. Sci. 303 (1) (2003) 53-62.

%H D. Dowe, <a href="http://dx.doi.org/10.1017/S1446788700031220">On the existence of sequences of coprime pairs of integers</a>, J. Austral. Math. Soc. Ser. A 47, no. 1, 84-89. 1989

%H P. Erdős and J. L. Selfridge, <a href="http://www.renyi.hu/~p_erdos/1971-03.pdf">Complete prime subsets of consecutive integers</a>, Proceedings of the Manitoba Conference on Numerical Mathematics, 1971, pp. 1-14.

%H M. F. Hasler, R. J. Mathar, <a href="http://arxiv.org/abs/1510.07997">Corrigendum to "Paths and circutis in finite groups", Discr. Math. 22 (1978) 263</a>, arXiv:1510.07997 (2015).

%H Christopher Hunt Gribble, <a href="http://list.seqfan.eu/pipermail/seqfan/2014-December/014092.html">Seqfan thread</a>, Dec 05 2014

%H W. Holsztynski, R. F. E. Strube, <a href="http://dx.doi.org/10.1016/0012-365X(78)90059-6">Paths and circuits in finite groups</a>, Discr. Math. 22 (1978) 263-272.

%H Internet Movie Database, <a href="https://www.imdb.com/title/tt5831628/">Mr. Robot: Season 2, Episode 11: eps2.9_pyth0n-pt1.p7z</a>

%H Nik Lygeros, <a href="http://www.lygeros.org/Math/erdoswoods.html">Erdos-Woods Numbers</a>

%H W. T. Trotter and Paul Erdős, <a href="http://dx.doi.org/10.1002/jgt.3190020206">When the Cartesian product of directed cycles is Hamiltonian</a>, J. Graph Theory 2 (1978) 137-142

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Woods_number">Erdos-Woods number</a>

%H Alan Robert Woods, <a href="http://school.maths.uwa.edu.au/~woods/thesis/WoodsPhDThesis.pdf">Some Problems in Logic and Number Theory, and their Connections</a>, Thesis, University of Manchester, 1981 (reprinted in New Studies in Weak Arithmetics, Sept 2013, CSLI).

%e a(1) = 16 refers to the interval 2184, 2185, ..., 2200. The end points are 2184 = 2^3 *3 *7 *13 and 2200 = 2^3 *5^2 *11, and each number 2184<=k<=2200 has at least one prime factor in the set {2,3,5,7,11,13}.

%o (PARI) prime_part(n)={my(P=primes(primepi(n-1)));forstep(x1=2,2^#P-1,2, P1=vecextract(P,x1); P2=setminus(P,P1); for(n1=1,n-1, bittest(n-n1,0) || next; setintersect(P1,factor(n1)[,1]~) || setintersect(P2,factor(n-n1)[,1]~) || next(2)); return([P1,P2]))} \\ _M. F. Hasler_, Jun 29 2014

%Y See A059757 for first terms of corresponding intervals. Cf. A111042.

%K nonn

%O 1,1

%A Nik Lygeros (webmaster(AT)lygeros.org), Feb 12 2001

%E Further terms from _Victor S. Miller_, Sep 29 2005

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 7 05:20 EDT 2020. Contains 334837 sequences. (Running on oeis4.)