Die Länge der kleinsten Co-Prim-Kette zwischen zwei beliebigen ganzen Zahlen

7

Betrachten Sie die folgende Aussage:

Für jedes gilt eine der folgenden Bedingungen: a<bN

  1. gcd(a,b)=1 .
  2. es gibt ein a<x<b so dass gcd(a,x)=gcd(x,b)=1 .
  3. es gibt a<x<y<b so dass gcd(a,x)=gcd(x,y)=gcd(y,b)=1 .

Ist diese Aussage wahr?


Motivation:

Ich habe eine Variante dieses Problems in einem der jüngsten Algorithmenwettbewerbe gefunden.

Betrachten Sie das folgende Problem:

Eingabe: zwei ganze Zahlen a und b wobei a<b .

Ausgabe: kleinste Zahl l so dass es ganze Zahlen a=x0<x1<x2<<xl<xl+1=b so dass alle aufeinanderfolgenden ganzen Zahlen in der Liste Co-Primzahlen sind: gcd(xi,xi+1)=1 für i=0,,l .

Beispiele:

  1. a=7,b=13 : gcd(a,b)=1 , daher l=0 .

  2. a=10,b=12 : gcd(a,b)=21 , daher l1 . Die Folge sei 10,11,12 . gcd(10,11)=1,gcd(11,12)=1 .

  3. a=2184,b=2200 : Es gibt kein so dass . Wir können jedoch ganze Zahlen finden, die dieses Problem erfüllen.a<x<bgcd(a,x)=gcd(x,b)=12

Es gibt einen Referenzalgorithmus, anhand dessen Algorithmen bewertet werden. Dieser Algorithmus geht davon aus

  1. Es gibt immer ein , das die Bedingung erfüllt.l

  2. l2 .

Ich verstehe nicht, warum sie wahr sind.

Ich habe einen Polynom-Zeitalgorithmus, der keinen von beiden annimmt. Ich verliere nicht die asymptotische Leistung im Vergleich zum Referenzalgorithmus, aber ich könnte die Leistungskonstanten viel niedriger bekommen, wenn ich die Gültigkeit der Annahmen verstehen und beweisen kann.

DarthShader
quelle
5
Dass es immer lösbar ist, lässt sich an allen ganzen Zahlen zwischen und ablesen ( , , ..). Dies zeigt . ABN1=A+1N2=A+2LBA1
Polkjh
polkjh: das scheint zu funktionieren, wenn GCD (n, n + 1) = 1 ist (was wahr ist).
DarthShader
Bitte nutzen Sie den auf dieser Website verfügbaren Latex-Support.
Aryabhata
2
Ich denke, Sie haben vielleicht mehr Glück in Mathematik .
Kaveh

Antworten:

1

Die Vermutung scheint offen zu sein. Es wird als Vermutung 3 in einem Papier von Dowe angegeben . Dowe zeigt, dass die Goldbach-Vermutung impliziert, dass , und erwähnt, dass Alan Woods in seiner Doktorarbeit gezeigt hat, dass begrenzt ist. Vielleicht impliziert der jüngste Beweis der seltsamen Goldbach-Vermutung auch eine bestimmte und kleine Grenze.23

Wenn dann ist eine Erdős-Woods-Zahl. Insbesondere wenn ist, müssen sowohl als auch Erdős-Woods-Zahlen sein. A059756 listet die ersten Erdős-Woods-Nummern auf. Während alle Zahlen auf dieser Liste gerade sind, gibt es auch ungerade Erdős-Woods-Zahlen, von denen einige in A111042 aufgeführt sind . Die kleinsten Werte entsprechenden Unterschieds sind in A059757 aufgeführt . Obwohl diese Liste nicht wächst, scheint es, als ob die Zahlen ziemlich schnell wachsen. Jedes Gegenbeispiel zu wäre so, dass sowohl als auch>1ba>2baba1a2baba1sind Erdős-Woods-Zahlen und insbesondere (gemäß A059756). Dies deutet darauf hin (beweist aber nicht), dass ein solches Gegenbeispiel riesig sein wird, und daher können wir für alle praktischen Zwecke davon ausgehen, dass .ba>4302

Yuval Filmus
quelle