|
|
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.
|
|
10
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
"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
|
|
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
|
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]
|
|
EXAMPLE
|
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}.
|
|
PROG
|
(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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Nik Lygeros (webmaster(AT)lygeros.org), Feb 12 2001
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|