|
%I #86 Jan 02 2023 12:30:46
%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 Cégielski, 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
%C Named after the Hungarian mathematician Paul Erdős (1913-1996) and the Australian mathematician Alan Robert Woods (1953-2011). - _Amiram Eldar_, Jun 20 2021
%D Richard 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 Patrick Cégielski, François Heroult and Denis 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., Vol. 303, No. 1 (2003), pp. 53-62.
%H David L. Dowe, <a href="http://dx.doi.org/10.1017/S1446788700031220">On the existence of sequences of co-prime pairs of integers</a>, J. Austral. Math. Soc. Ser. A, Vol. 47, No. 1 (1989), pp. 84-89.
%H Paul Erdős and John 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 Bertram Felgenhauer, <a href="http://www.int-e.eu/oeis/">Some OEIS computations</a> (includes the terms of this sequence up to 100000).
%H M. F. Hasler and R. J. Mathar, <a href="http://arxiv.org/abs/1510.07997">Corrigendum to "Paths and circuits in finite groups", Discr. Math. 22 (1978) 263</a>, arXiv:1510.07997 [math.NT], 2015.
%H Christopher Hunt Gribble, <a href="http://list.seqfan.eu/oldermail/seqfan/2014-December/014092.html">Seqfan thread</a>, Dec 05 2014.
%H W. Holsztynski and 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="https://lygeros.org/erdoswoods/">Erdos-Woods Numbers</a>, contains a list for a(n)<=400000. [Warning: a lot of terms are missing. The smallest missing term is a(169) = 796. - _Jianing Song_, Mar 08 2021]
%H William T. Trotter, Jr. 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, Vol. 2, No. 2 (1978), pp. 137-142.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Woods_number">Erdős-Woods number</a>.
%H Alan Robert Woods, <a href="https://web.archive.org/web/20190608093205/http://staffhome.ecm.uwa.edu.au/~00017049/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). [Cached copy at the Wayback Machine]
%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
|
