A059757 -id:A059757 - cp's OEIS frontend

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.

16, 22, 34, 36, 46, 56, 64, 66, 70, 76, 78, 86, 88, 92, 94, 96, 100, 106, 112, 116, 118, 120, 124, 130, 134, 142, 144, 146, 154, 160, 162, 186, 190, 196, 204, 210, 216, 218, 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

Offset: 1

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

nonn

"Length" means total number of terms including endpoints, minus 1.
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.
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
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
Named after the Hungarian mathematician Paul Erdős (1913-1996) and the Australian mathematician Alan Robert Woods (1953-2011). - Amiram Eldar, Jun 20 2021

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

Richard K. Guy, Unsolved Problems in Number Theory, 1981, related to Sections B27, B28, B29.
Konstantin Lakkis, Number Theory [in Greek], Revised edition, 1984.

Bertram Felgenhauer, Table of n, a(n) for n = 1..10000
Patrick Cégielski, François Heroult and Denis Richard, On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity, Theor. Comp. Sci., Vol. 303, No. 1 (2003), pp. 53-62.
David L. Dowe, On the existence of sequences of co-prime pairs of integers, J. Austral. Math. Soc. Ser. A, Vol. 47, No. 1 (1989), pp. 84-89.
Paul Erdős and John L. Selfridge, Complete prime subsets of consecutive integers, Proceedings of the Manitoba Conference on Numerical Mathematics, 1971, pp. 1-14.
Bertram Felgenhauer, Some OEIS computations (includes the terms of this sequence up to 10^6).
James Grime and Brady Haran, Erdős-Woods Numbers, Numberphile video (2024)
M. F. Hasler and R. J. Mathar, Corrigendum to "Paths and circuits in finite groups", Discr. Math. 22 (1978) 263, arXiv:1510.07997 [math.NT], 2015.
Christopher Hunt Gribble, Seqfan thread, Dec 05 2014.
W. Holsztynski and R. F. E. Strube, Paths and circuits in finite groups, Discr. Math. 22 (1978) 263-272.
Internet Movie Database, Mr. Robot: Season 2, Episode 11: eps2.9_pyth0n-pt1.p7z
Nik Lygeros, Erdos-Woods Numbers, 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]
William T. Trotter, Jr. and Paul Erdős, When the Cartesian product of directed cycles is Hamiltonian, J. Graph Theory, Vol. 2, No. 2 (1978), pp. 137-142.
Wikipedia, Erdős-Woods number.
Alan Robert Woods, Some Problems in Logic and Number Theory, and their Connections, Thesis, University of Manchester, 1981 (reprinted in New Studies in Weak Arithmetics, Sept 2013, CSLI). [Cached copy at the Wayback Machine]

See A059757 for first terms of corresponding intervals. Cf. A111042, A342310.

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

Further terms from Victor S. Miller, Sep 29 2005

A244620 Initial terms of Erdős-Wood intervals of length 22.

Original entry on oeis.org

3521210, 6178458, 13220900, 15878148, 22920590, 25577838, 32620280, 35277528, 42319970, 44977218, 52019660, 54676908, 61719350, 64376598, 71419040, 74076288, 81118730, 83775978, 90818420, 93475668, 100518110, 103175358, 110217800, 112875048, 119917490

Offset: 1

R. J. Mathar, Jul 02 2014

nonn

By definition of the intervals in A059756, these are numbers that start a sequence of 23 consecutive integers such that none of the 23 integers is coprime to the first and also coprime to the last integer of the interval.

Hence each initial term of an Erdős-Wood interval is the initial term of a stapled interval of length A059756(n) + 1 (see definition in A090318). - Christopher Hunt Gribble, Dec 02 2014

			3521210 = 2*5*7*11*17*269 and 3521210+22 = 3521232 = 2^4 * 3^4 * 11 * 13 * 19, and all numbers in [3521210,3521232] have at least one prime factor in {2, 3, 5, 7, 11, 13, 17, 19, 269}. Therefore 3521210 is in the list.

Christopher Hunt Gribble, Table of n, a(n) for n = 1..1000
Wikipedia, Erdős-Woods number
Index entries for linear recurrences with constant coefficients, signature (1, 1, -1).

Cf. A059757, A194585, A090318, A130173.

isEWood := proc(n,ewlength)
    local nend,fsn,fsne,fsall,fsk ;
    nend := n+ewlength ;
    fsn := numtheory[factorset](n) ;
    fsne := numtheory[factorset](nend) ;
    fsall := fsn union fsne ;
    for k from n to nend do
        fsk := numtheory[factorset](k) ;
        if fsk intersect fsall = {} then
            return false;
        end if;
    end do:
    return true;
end proc:
for n from 2 do
    if isEWood(n,22) then
        print(n) ;
    end if;
end do:

a(1) = A059757(2).
From Christopher Hunt Gribble, Dec 02 2014: (Start)
a(1) = A130173(524).
a(2*n+1) = 3521210 + 9699690*n.
a(2*n+2) = 6178458 + 9699690*n.
a(n) = (-4849867 - 2192597*(-1)^n + 9699690*n)/2.
a(n) = a(n-1) + a(n-2) - a(n-3).
G.f.: (3521232*x^2+2657248*x+3521210) / ((x-1)^2*(x+1)). (End)

More terms from Christopher Hunt Gribble, Dec 03 2014

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Extensions