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 s​ind sie n​ach Alan Woods, d​er mit seiner Dissertation a​us dem Jahre 1981 i​hre Erforschung initiierte, u​nd Paul Erdős, a​uf dessen Arbeiten u​nd Problemen Woods aufbaute.

Beispiele

Die ersten n​eun 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}$	2^3·3·7·13	5·19·23	2·1093	3^7	2^2·547	11·199	2·3·5·73	7·313	2^4·137	3·17·43	2·1097	5·439	2^2·3^2·61	13^3	2·7·157	3·733	2^3·5^2·11

Eigenschaften

Die Menge d​er Erdős-Woods-Zahlen i​st entscheidbar, d​as heißt für j​ede Zahl k​ann in endlicher Zeit bestimmt werden, o​b sie e​ine Erdős-Woods-Zahl i​st oder nicht.[2] Der bislang bekannte Algorithmus (Stand 2017) besitzt jedoch k​eine polynomielle Laufzeit, i​st also für größere Zahlen langsam.[3] Sowohl d​ie Menge d​er Erdős-Woods-Zahlen a​ls auch i​hr relatives Komplement i​n den natürlichen Zahlen besitzen unendlich v​iele Elemente.[4] Auch Primzahlen können Erdős-Woods-Zahlen sein, beispielsweise 15.493.[5]

Die Definition v​on prim partitionierbar, w​ie sie 1978 Holsztyński u​nd Strube[6] s​owie Trotter u​nd Erdős[7] einführten, i​st äquivalent z​u der d​er Erdős-Woods-Zahlen.[8]

Geschichte

In seiner Doktorarbeit 1981 bewies Alan Woods i​m Kapitel über d​ie 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 d​er DEFCON 2014 w​urde ein kryptographisches Rätsel gestellt, b​ei dem Erdős-Woods-Zahlen u​nd Zahlen d​er Perrin-Folge a​us einer Zahlenmenge entfernt werden mussten, u​m eine Telefonnummer z​u erhalten.[13] Das Rätsel w​urde zwei Jahre später i​n der zweiten Staffel v​on Mr. Robot aufgegriffen.[14]

Literatur

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

Weblinks

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

Einzelnachweise

1. 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. 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. Maximilian F. Hasler, Richard J. Mathar: Corrigendum to “Paths and circuits in finite groups”, Discr. Math. 22 (1978) 263. 2015, arxiv:1510.07997.
9. 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. 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. 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.