Erdős-Woods-Zahl
# Erdős-Woods-Zahl

In der Zahlentheorie wird eine natürliche Zahl $d>1$ als Erdős-Woods-Zahl bezeichnet, wenn es eine weitere natürliche Zahl $a$ gibt, sodass jede Zahl in der Folge $(a,a+1,\ldots ,a+d)$ einen gemeinsamen Teiler echt größer eins mit $a$ oder $a+d$ 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 $a$ finden sich in Folge A059757 der On-Line Encyclopedia of Integer Sequences.

Das kleinste zu $d=16$ gehörige $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.

| $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 $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 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. Der bislang bekannte Algorithmus (Stand 2017) besitzt jedoch keine polynomielle Laufzeit, ist also für größere Zahlen langsam. Sowohl die Menge der Erdős-Woods-Zahlen als auch ihr relatives Komplement in den natürlichen Zahlen besitzen unendlich viele Elemente. Auch Primzahlen können Erdős-Woods-Zahlen sein, beispielsweise 15.493.

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

## Geschichte

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

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

Er stellte daraufhin die Vermutung auf, dass es für zwei nicht direkt aufeinanderfolgende Zahlen immer eine dazwischen gibt, die teilerfremd zu beiden ist. Dies sagt aus, dass es keine Erdős-Woods-Zahlen gibt, und impliziert 2 als kleinsten Wert für $g$. Bald darauf bekam er Zweifel an dieser Vermutung und fand schließlich mit $d=16$ sowie $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. 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. Das Rätsel wurde zwei Jahre später in der zweiten Staffel von Mr. Robot aufgegriffen.

