Erdős-Woods-Zahl

aus Wikipedia, der freien Enzyklopädie

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

Beispiele

Die ersten neun Erdős-Woods-Zahlen lauten

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

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.[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]

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.[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 .[9] Bald darauf bekam er Zweifel an dieser Vermutung[11] 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.[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]

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

Einzelnachweise

  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. 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.
Abgerufen von „https://de.wikiup.org/index.php?title=Erdős-Woods-Zahl&oldid=224291618“