In der Zahlentheorie wird eine natürliche Zahl als Erdős-Woods-Zahl bezeichnet, wenn es eine weitere natürliche Zahl gibt, sodass jede Zahl in der Folge einen gemeinsamen Teiler echt größer eins mit oder aufweist. 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.
Beispiele Die ersten neun Erdős-Woods-Zahlen lauten 16, 22, 34, 36, 46, 56, 64, 66 und 70, die korrespondierenden Werte für finden sich in Folge A059757 der On-Line Encyclopedia of Integer Sequences.
Das kleinste zu gehörige 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.
2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 Primfaktorzerlegung von 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
Eigenschaften 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.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. Der bislang bekannte Algorithmus (Stand 2017) besitzt jedoch keine polynomielle Laufzeit, ist also für größere Zahlen langsam.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. Sowohl die Menge der Erdős-Woods-Zahlen als auch ihr relatives Komplement in den natürlichen Zahlen besitzen unendlich viele Elemente.David L. Dowe: On the existence of sequences of co-prime pairs of integers. 1989, S. 86f. Auch Primzahlen können Erdős-Woods-Zahlen sein, beispielsweise 15.493.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.
Die Definition von prim partitionierbar, wie sie 1978 Holsztyński und StrubeW. 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. sowie Trotter und ErdősWilliam 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. einführten, ist äquivalent zu der der Erdős-Woods-Zahlen.Maximilian F. Hasler, Richard J. Mathar: Corrigendum to “Paths and circuits in finite groups”, Discr. Math. 22 (1978) 263. 2015, .
Geschichte In seiner Doktorarbeit 1981 bewies Alan Woods im Kapitel über die Erdős-Woods-Vermutung folgendes: Es gibt eine natürliche Zahl , sodass für je zwei Zahlen mit eine streng monotone Folge , , existiert, bei der je zwei aufeinanderfolgende Elemente teilerfremd sind.David L. Dowe: On the existence of sequences of co-prime pairs of integers. 1989, S. 84 in der Notation von Alan Robert Woods: Dissertation, University of Manchester, 1981, S. 87f. (PDF; 3,5 MB). Er stellte daraufhin die Vermutung auf, dass es für zwei nicht direkt aufeinanderfolgende Zahlen immer eine dazwischen gibt, die teilerfremd zu beiden ist.Alan Robert Woods: Dissertation, University of Manchester, 1981, S. 88 (PDF; 3,5 MB). Dies sagt aus, dass es keine Erdős-Woods-Zahlen gibt, und impliziert 2 als kleinsten Wert für . Bald darauf bekam er Zweifel an dieser VermutungForumseintrag von Rainer Rosenthal, in dem er eine E-Mail von Woods zitiert (englisch). und fand schließlich mit sowie 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.David L. Dowe: On the existence of sequences of co-prime pairs of integers. 1989, S. 85f. Da, wie 2015 bekannt wurde, die Menge der Erdős-Woods-Zahlen und die der prim partitionierbaren Zahlen übereinstimmen, bewiesen bereits 1978 Trotter und Erdős unabhängig davon, dass die Menge unendlich groß ist.
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.Brett Buerhaus, Jason Thor Hall: DEFCON 22 Badge Challenge. Abgerufen am 14. September 2017. Das Rätsel wurde zwei Jahre später in der zweiten Staffel von Mr. Robot aufgegriffen.Russell Brandom: The Mr Robot Hack Report: Following the bread crumbs. 14. September 2016, abgerufen am 14. September 2017.
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
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
Kategorie:Zahlentheorie Kategorie:Ganzzahlmenge