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
Keywords
Examples
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}.
References
- Richard K. Guy, Unsolved Problems in Number Theory, 1981, related to Sections B27, B28, B29.
- Konstantin Lakkis, Number Theory [in Greek], Revised edition, 1984.
Links
- 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]
Programs
-
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
Extensions
Further terms from Victor S. Miller, Sep 29 2005
Comments