Erdős-Woods-Zahl

In der Zahlentheorie wird eine natürliche Zahl ${\displaystyle d>1}$ als Erdős-Woods-Zahl bezeichnet, wenn es eine weitere natürliche Zahl ${\displaystyle a}$ gibt, sodass jede Zahl in der Folge ${\displaystyle (a,a+1,\ldots ,a+d)}$ einen gemeinsamen Teiler echt größer eins mit ${\displaystyle a}$ oder ${\displaystyle a+d}$ aufweist.^[1] Für jedes beliebige Folgenglied ist also der größte gemeinsame Teiler mit mindestens einem der Randwerte nicht gleich eins. Die kleinste der unendlich vielen Erdős-Woods-Zahlen ist 16, in der On-Line Encyclopedia of Integer Sequences sind sie als Folge A059756 abgespeichert.

Benannt sind sie nach Alan Woods, der mit seiner Dissertation aus dem Jahre 1981 ihre Erforschung initiierte, und Paul Erdős, auf dessen Arbeiten und Problemen Woods aufbaute.

Die ersten neun Erdős-Woods-Zahlen lauten

16, 22, 34, 36, 46, 56, 64, 66 und 70,^[1]

die korrespondierenden Werte für ${\displaystyle a}$ finden sich in Folge A059757 der On-Line Encyclopedia of Integer Sequences.

Das kleinste zu ${\displaystyle d=16}$ gehörige ${\displaystyle a}$ ist 2184. Die folgende Tabelle veranschaulicht mithilfe von Primfaktorzerlegung, dass 16 die Bedingungen für eine Erdős-Woods-Zahl erfüllt. Alle gemeinsamen Primfaktoren mit einem der farbig markierten Randwerte sind fett ausgezeichnet.

${\displaystyle a\leq x\leq a+d}$	2184	2185	2186	2187	2188	2189	2190	2191	2192	2193	2194	2195	2196	2197	2198	2199	2200
Primfaktorzerlegung von ${\displaystyle x}$	23·3·7·13	5·19·23	2·1093	37	22·547	11·199	2·3·5·73	7·313	24·137	3·17·43	2·1097	5·439	22·32·61	133	2·7·157	3·733	23·52·11

Die Menge der Erdős-Woods-Zahlen ist entscheidbar, das heißt für jede Zahl kann in endlicher Zeit bestimmt werden, ob sie eine Erdős-Woods-Zahl ist oder nicht.^[2] Der bislang bekannte Algorithmus (Stand 2017) besitzt jedoch keine polynomielle Laufzeit, ist also für größere Zahlen langsam.^[3] Sowohl die Menge der Erdős-Woods-Zahlen als auch ihr relatives Komplement in den natürlichen Zahlen besitzen unendlich viele Elemente.^[4] Auch Primzahlen können Erdős-Woods-Zahlen sein, beispielsweise 15.493.^[5]

Die Definition von prim partitionierbar, wie sie 1978 Holsztyński und Strube^[6] sowie Trotter und Erdős^[7] einführten, ist äquivalent zu der der Erdős-Woods-Zahlen.^[8]

In seiner Doktorarbeit 1981 bewies Alan Woods im Kapitel über die Erdős-Woods-Vermutung folgendes:

Es gibt eine natürliche Zahl ${\displaystyle g}$, sodass für je zwei Zahlen ${\displaystyle x<y}$ mit ${\displaystyle y-x\geq g}$ eine streng monotone Folge ${\displaystyle (x,z_{1},z_{2},\ldots ,z_{m},y)}$, ${\displaystyle 0<m<g}$, existiert, bei der je zwei aufeinanderfolgende Elemente teilerfremd sind.^[9]

Er stellte daraufhin die Vermutung auf, dass es für zwei nicht direkt aufeinanderfolgende Zahlen immer eine dazwischen gibt, die teilerfremd zu beiden ist.^[10] Dies sagt aus, dass es keine Erdős-Woods-Zahlen gibt, und impliziert 2 als kleinsten Wert für ${\displaystyle g}$.^[9] Bald darauf bekam er Zweifel an dieser Vermutung^[11] und fand schließlich mit ${\displaystyle d=16}$ sowie ${\displaystyle a=2184}$ ein Gegenbeispiel – die erste Erdős-Woods-Zahl. 1989 veröffentlichte David L. Dowe erstmals dieses Ergebnis und bewies darauf aufbauend, dass es unendlich viele Erdős-Woods-Zahlen gibt.^[12] Da, wie 2015 bekannt wurde, die Menge der Erdős-Woods-Zahlen und die der prim partitionierbaren Zahlen übereinstimmen,^[8] bewiesen bereits 1978 Trotter und Erdős unabhängig davon, dass die Menge unendlich groß ist.^[7]

Auf der DEFCON 2014 wurde ein kryptographisches Rätsel gestellt, bei dem Erdős-Woods-Zahlen und Zahlen der Perrin-Folge aus einer Zahlenmenge entfernt werden mussten, um eine Telefonnummer zu erhalten.^[13] Das Rätsel wurde zwei Jahre später in der zweiten Staffel von Mr. Robot aufgegriffen.^[14]

• 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. Jahrgang 47, Heft 1, 1989, doi:10.1017/S1446788700031220, S. 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. Jahrgang 303, Heft 1, 2003, doi:10.1016/S0304-3975(02)00444-9, S. 53–62.

• Folge A059756 in OEIS
• Nik Lygeros: Erdös-Woods Numbers. Alle Erdős-Woods-Zahlen bis 400.000.
• Nik Lygeros: From the computation of Erdös-Woods Numbers to the quadratic Goldbach Conjecture.

1. ↑ ^{a b} Folge 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, S. 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, S. 57f.
4. ↑ David L. Dowe: On the existence of sequences of co-prime pairs of integers. 1989, S. 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, S. 59.
6. ↑ W. Holsztyński, R.F.E. Strube: Paths and circuits in finite groups. In: Discrete Mathematics. Jahrgang 22, Heft 3, 1978, doi:10.1016/0012-365X(78)90059-6, S. 269.
7. ↑ ^{a b} William T. Trotter, Paul Erdős: When the cartesian product of directed cycles is Hamiltonian. In: Journal of Graph Theory. Jahrgang 2, Heft 2, 1978, doi:10.1002/jgt.3190020206, S. 141.
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.
9. ↑ ^{a b} David L. Dowe: On the existence of sequences of co-prime pairs of integers. 1989, S. 84 in der Notation von Alan Robert Woods: Some Problems in Logic and Number Theory, and their Connections. (Memento vom 12. September 2015 im Internet Archive) Dissertation, University of Manchester, 1981, S. 87f. (PDF; 3,5 MB).
10. ↑ Alan Robert Woods: Some Problems in Logic and Number Theory, and their Connections. (Memento vom 12. September 2015 im Internet Archive) Dissertation, University of Manchester, 1981, S. 88 (PDF; 3,5 MB).
11. ↑ Forumseintrag von Rainer Rosenthal, in dem er eine E-Mail von Woods zitiert (englisch).
12. ↑ David L. Dowe: On the existence of sequences of co-prime pairs of integers. 1989, S. 85f.
13. ↑ Brett Buerhaus, Jason Thor Hall: DEFCON 22 Badge Challenge. Abgerufen am 14. September 2017.
14. ↑ Russell Brandom: The Mr Robot Hack Report: Following the bread crumbs. 14. September 2016, abgerufen am 14. September 2017.