Erdős Woods number

In number theory , a natural number is called Erdős-Woods number if there is another natural number such that every number in the sequence has a common factor that is really greater than one with or . For any sequence term, the greatest common divisor with at least one of the boundary values is not equal to one. The smallest of the infinitely many Erdős-Woods numbers is 16; in the On-Line Encyclopedia of Integer Sequences they are stored as sequence A059756 . ${\ displaystyle d> 1}$ ${\ displaystyle a}$ ${\ displaystyle (a, a + 1, \ ldots, a + d)}$ ${\ displaystyle a}$ ${\ displaystyle a + d}$

They are named after Alan Woods, who initiated their research with his dissertation from 1981, and Paul Erdős , on whose work and problems Woods built.

Examples

The first nine Erdős-Woods numbers are

16, 22, 34, 36, 46, 56, 64, 66 and 70,

the corresponding values for can be found in series A059757 of the On-Line Encyclopedia of Integer Sequences. ${\ displaystyle a}$

The smallest that corresponds to it is 2184. The following table uses prime factorization to show that 16 meets the conditions for an Erdős-Woods number. All common prime factors with one of the border values marked in color are shown in bold. ${\ displaystyle d = 16}$ ${\ displaystyle a}$

${\ displaystyle a \ leq x \ leq a + d}$	2184	2185	2186	2187	2188	2189	2190	2191	2192	2193	2194	2195	2196	2197	2198	2199	2200
Prime factorization of ${\ displaystyle x}$	2 ³ 3 7 13	5 19 23	2 1093	3 ⁷	2 ² 547	11 199	2 · 3 · 5 · 73	7 313	2 ⁴ 137	3 17 43	2 1097	5 439	2 ² · 3 ² · 61	13 ³	2 · 7 · 157	3 733	2 ³ 5 ² 11

properties

The set of Erdős-Woods numbers is decidable , i.e. for every number it can be determined in a finite time whether it is an Erdős-Woods number or not. The previously known algorithm (as of 2017) does not have a polynomial running time , so it is slow for larger numbers. Both the set of Erdős-Woods numbers and their relative complement in the natural numbers have an infinite number of elements. Erdős-Woods numbers can also be prime numbers, for example 15,493.

The definition of prim partitionable as introduced by Holsztyński and Strube as well as Trotter and Erdős in 1978 is equivalent to that of the Erdős-Woods numbers.

history

In his doctoral thesis in 1981, Alan Woods proved the following in the chapter on the Erdős-Woods conjecture :

There is a natural number such that for any two numbers with a strictly monotonic sequence , exists, in which two successive elements are relatively prime are.

{\ displaystyle g}

{\ displaystyle x <y}

{\ displaystyle yx \ geq g}

{\ displaystyle (x, z_ {1}, z_ {2}, \ ldots, z_ {m}, y)}

{\ displaystyle 0 <m <g}

He then put forward the conjecture that for two numbers that are not directly consecutive there is always one in between that is relatively prime to both. This means that there are no Erdős-Woods numbers and implies 2 as the smallest value for . Soon afterwards he had doubts about this assumption and finally found a counterexample with and - the first Erdős-Woods number. In 1989 David L. Dowe published this result for the first time and, building on it, proved that there are an infinite number of Erdős-Woods numbers. Since, as became known in 2015, the set of Erdős-Woods numbers and that of the prime partitionable numbers coincide, Trotter and Erdős proved as early as 1978, regardless of this, that the set is infinitely large. ${\ displaystyle g}$ ${\ displaystyle d = 16}$ ${\ displaystyle a = 2184}$

At DEFCON 2014, a cryptographic puzzle was posed in which Erdős-Woods numbers and numbers from the Perrin sequence had to be removed from a set of numbers in order to obtain a telephone number. The puzzle was picked up by Mr. Robot two years later in the second season .

literature

David L. Dowe: On the existence of sequences of co-prime pairs of integers . In: Journal of the Australian Mathematical Society. Series A. Pure Mathematics and Statistics . Volume 47, Issue 1, 1989, doi: 10.1017 / S1446788700031220 , pp. 84–89.
Patrick Cégielski, François Heroult, Denis Richard: On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity . In: Theoretical Computer Science . Volume 303, Issue 1, 2003, doi: 10.1016 / S0304-3975 (02) 00444-9 , pp. 53-62.

Web links

Follow A059756 in OEIS
Nik Lygeros: Erdös-Woods Numbers . All Erdős-Woods numbers up to 400,000.
Nik Lygeros: From the computation of Erdös-Woods Numbers to the quadratic Goldbach Conjecture .

Individual evidence

↑ ^a ^b Follow A059756 in OEIS
↑ Patrick Cégielski, François Heroult, Denis Richard: On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity . 2003, p. 56.
↑ Patrick Cégielski, François Heroult, Denis Richard: On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity . 2003, p. 57f.
↑ David L. Dowe: On the existence of sequences of co-prime pairs of integers . 1989, p. 86f.
↑ Patrick Cégielski, François Heroult, Denis Richard: On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity . 2003, p. 59.
↑ W. Holsztyński, RFE Strube: Paths and circuits in finite groups . In: Discrete Mathematics . Volume 22, Issue 3, 1978, doi: 10.1016 / 0012-365X (78) 90059-6 , p. 269.
↑ ^a ^b William T. Trotter, Paul Erdős: When the cartesian product of directed cycles is Hamiltonian. In: Journal of Graph Theory . Volume 2, Issue 2, 1978, doi: 10.1002 / jgt.3190020206 , p. 141.
^ ^A ^b Maximilian F. Hasler, Richard J. Mathar: Corrigendum to “Paths and circuits in finite groups”, Discr. Math. 22 (1978) 263 . 2015, arxiv : 1510.07997 .
↑ ^a ^b David L. Dowe: On the existence of sequences of co-prime pairs of integers . 1989, p. 84 in the notation by Alan Robert Woods: Some Problems in Logic and Number Theory, and their Connections . Dissertation, University of Manchester, 1981, pp. 87f. (PDF; 3.5 MB).
^ Alan Robert Woods: Some Problems in Logic and Number Theory, and their Connections . Dissertation, University of Manchester, 1981, p. 88 (PDF; 3.5 MB).
↑ Forum entry by Rainer Rosenthal, in which he quoted an email from Woods (English).
↑ David L. Dowe: On the existence of sequences of co-prime pairs of integers . 1989, pp. 85f.
↑ Brett Buerhaus, Jason Thor Hall: DEFCON 22 Badge Challenge . Retrieved September 14, 2017.
↑ Russell Brandom: The Mr Robot Hack Report: Following the bread crumbs . September 14, 2016, accessed September 14, 2017.

[OEIS-1] Follow A059756 in OEIS

[2] Patrick Cégielski, François Heroult, Denis Richard: On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity . 2003, p. 56.

[3] Patrick Cégielski, François Heroult, Denis Richard: On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity . 2003, p. 57f.

[4] David L. Dowe: On the existence of sequences of co-prime pairs of integers . 1989, p. 86f.

[5] Patrick Cégielski, François Heroult, Denis Richard: On the amplitude of intervals of natural numbers whose every element has a common prime divisor with at least an extremity . 2003, p. 59.

[6] W. Holsztyński, RFE Strube: Paths and circuits in finite groups . In: Discrete Mathematics . Volume 22, Issue 3, 1978, doi: 10.1016 / 0012-365X (78) 90059-6 , p. 269.

[trotter_erdös-7] William T. Trotter, Paul Erdős: When the cartesian product of directed cycles is Hamiltonian. In: Journal of Graph Theory . Volume 2, Issue 2, 1978, doi: 10.1002 / jgt.3190020206 , p. 141.

[hasler-8] A ^b Maximilian F. Hasler, Richard J. Mathar: Corrigendum to “Paths and circuits in finite groups”, Discr. Math. 22 (1978) 263 . 2015, arxiv : 1510.07997 .

[doweNotWoods-9] David L. Dowe: On the existence of sequences of co-prime pairs of integers . 1989, p. 84 in the notation by Alan Robert Woods: Some Problems in Logic and Number Theory, and their Connections . Dissertation, University of Manchester, 1981, pp. 87f. (PDF; 3.5 MB).

[10] Alan Robert Woods: Some Problems in Logic and Number Theory, and their Connections . Dissertation, University of Manchester, 1981, p. 88 (PDF; 3.5 MB).

[11] Forum entry by Rainer Rosenthal, in which he quoted an email from Woods (English).

[12] David L. Dowe: On the existence of sequences of co-prime pairs of integers . 1989, pp. 85f.

[13] Brett Buerhaus, Jason Thor Hall: DEFCON 22 Badge Challenge . Retrieved September 14, 2017.

[14] Russell Brandom: The Mr Robot Hack Report: Following the bread crumbs . September 14, 2016, accessed September 14, 2017.