Am wenigsten gemeinsamer Nicht-Teiler

Grundsätzlich ist das Problem: Finden Sie für eine Menge $S$ positiver Zahlen eine minimale Zahl $d$ , die kein Teiler eines Elements von $S$ , dh $\forall x \in S,\ d \nmid x$ .

Bezeichne $n = |S|$und $C = \max(S)$ . Betrachten Sie die Funktion $F(x) =$ die kleinste Primzahl, die x nicht teilt $x$. Es ist leicht zu erkennen, dass $F(x) \leq \log x$ . Und für eine Menge $S$ sei $F(S) =$ die kleinste Primzahl, die kein Element von S teilt $S$. Wir haben eine Obergrenze

Daher ist ein einfacher Brute-Force-Algorithmus, der alle Zahlen von $1$ bis $n \log C$ auflistet und prüft, ob er kein Element von S teilt $S$, polynomisch und hat die Zeitkomplexität $O(n^2 \log C)$ .

Die andere Möglichkeit, das Problem zu lösen, besteht darin, alle Faktoren für jedes Element von S zu berechnen $S$und sie im Brute-Force-Algorithmus zu verwenden, um zu überprüfen, ob $x$ eine Antwort in $O(1)$ -Zeit ist. Dieser Algorithmus hat eine zeitliche Komplexität von $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ und verwendet $O(n \log C)$ -Speicher, da wir nicht berechnen müssen und Speicher Faktoren größer ist als $n \log C$ . Für kleine $n$ und $C$ ist die Leistung besser.

Im Detail besteht der Algorithmus aus zwei Teilen:

1. Konstruieren Sie eine Menge $\hat{S}$ die aus allen Faktoren aller Elemente von $S$ , dh

   $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$ Dies kann in $O(n \cdot \min (\sqrt{C}, n \log C))$ Zeit und $O(n \log C)$ Speicher erfolgen. (Woher kommt das? Für jedes Element von $S$ können wir es entweder durch Versuchsfaktorisierung mit allen Zahlen bis zu $\sqrt{C}$ oder mit allen Primzahlen bis zu n \ log C faktorisieren $n \log C$, je nachdem, welcher Wert kleiner ist, also jedes Element von $S$ kann in der Zeit O (\ min (\ sqrt {C}, n \ log C)) berücksichtigt $O(\min (\sqrt{C}, n \log C))$werden.)

2. Finden Sie die minimale Anzahl . Dieser Schritt erfordert die Zeit , wenn geprüft wird, ob in der Zeit kann.$d \notin \hat{S}$$O(|\hat{S}|) = O(n \log C)$$x \in \hat{S}$$O(1)$

Ich habe zwei Fragen, die mich interessieren:

1. Gibt es einen schnelleren Algorithmus, um das Problem zu lösen?
2. Wie können wir für und eine Menge mit maximal kleinstem gemeinsamen Nicht-Divisor konstruieren ?$n$$C$$S$

Es ist möglich, Ihren zweiten Algorithmus zu verbessern, indem Sie bessere Algorithmen für die ganzzahlige Faktorisierung verwenden.

Hier sind zwei Algorithmen zur ganzzahligen Faktorisierung relevant:

• GNFS kann eine Ganzzahl mit der Laufzeit .$\le C$$O(L_C[0.33,1.92])$

• ECM kann einen Faktor (falls vorhanden) mit der Laufzeit ; Das Finden aller Faktoren dauert mal (was im Vergleich zur Laufzeit von ECM relativ klein ist).$\le n \log C$$O(L_{n \log C}[0.5,1.41])$$O(\log C / \log(n \log C))$

Hier ist .$L_n[\alpha,c] = \exp\{c (\log n)^\alpha (\log \log n)^{1-\alpha}\}$

Das ist ein ziemlich schrecklich aussehender Ausdruck für die Laufzeit, aber die wichtige Tatsache ist, dass dies schneller ist als die von Ihnen erwähnten Methoden. Insbesondere ist asymptotisch viel kleiner als , dh GNFS ist viel schneller als das Ausprobieren aller möglichen Faktoren . Auch asymptotisch viel kleiner als , das heißt, ist ECM viel schneller als alle möglichen Faktoren versuchen .$L_C[0.33,1.92]$$\sqrt{C}$$\le \sqrt{C}$$L_{n \log C}[0.5,1.41]$$n \log C$$\le n \log C$

Die Gesamtlaufzeit für diese Methode beträgt also ungefähr , und dies ist asymptotisch besser als Ihre erste Methode und asymptotisch besser als Ihre zweite Methode. Ich weiß nicht, ob es möglich ist, es noch besser zu machen.$\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$

Der am wenigsten verbreitete Nicht-Divisor kann so groß sein wie N log C, aber wenn die N Zahlen zufällig verteilt sind, ist der am wenigsten verbreitete Nicht-Divisor wahrscheinlich viel kleiner, wahrscheinlich viel weniger als N. Ich würde Tabellen erstellen, von denen Primzahlen sind Teiler welcher Zahlen.

Für jede Primzahl p haben wir einen Index was bedeutet, dass alle Zahlen bis zu diesem Index auf Teilbarkeit durch p untersucht wurden, und wir haben eine Liste aller Zahlen, die durch teilbar waren.$k_p$

Dann versuchen wir für d = 2, 3, 4, ... eine durch d teilbare Zahl zu finden oder zeigen, dass es keine gibt. Wir nehmen den größten Primfaktor p von d. Dann prüfen wir alle durch p teilbaren Zahlen, ob sie auch durch d teilbar sind. Wenn keine gefunden werden, überprüfen wir weitere Zahlen mit Indizes> auf Teilbarkeit durch p, aktualisieren und die Liste der durch p teilbaren Zahlen und prüfen, ob jede Zahl durch d teilbar ist.$k_p$$k_p$

Um zu überprüfen, ob es eine durch p teilbare Zahl gibt, überprüfen wir die durchschnittlichen p-Zahlen. Wenn wir später prüfen, ob es eine durch 2p teilbare Zahl gibt, besteht eine 50% ige Chance, dass wir nur eine Zahl (die durch p teilbare) überprüfen müssen, und eine 50% ige Chance, durchschnittlich 2p mehr Zahlen zu prüfen. Das Finden einer durch 3p teilbaren Zahl ist sehr wahrscheinlich und so weiter, und wir überprüfen nie mehr als N Zahlen auf Teilbarkeit durch p, da es nur N Zahlen gibt.

Ich würde hoffen, dass dies mit ungefähr Teilbarkeitsprüfungen klappt.$N^2 / log N$

PS. Wie groß wäre das Ergebnis für Zufallszahlen?

Angenommen, ich habe N Zufallszahlen. Die Wahrscheinlichkeit, dass eine der N Zahlen durch d teilbar ist, beträgt 1 - (1 - 1 / d) ^ N. Ich gehe davon aus, dass die Wahrscheinlichkeit, dass jede der Zahlen 1 ≤ d ≤ k ein Faktor einer der Zufallszahlen ist, durch Multiplikation dieser Wahrscheinlichkeiten berechnet wird (Ok, das ist etwas zwielichtig, da diese Wahrscheinlichkeiten wahrscheinlich nicht ganz unabhängig sind).

Mit dieser Annahme besteht bei N = 1000 eine 50% ige Chance, dass eine der Zahlen 1..244 keine Zahl teilt, und eine von einer Milliarde, dass jede Zahl bis zu 507 eine der Zahlen teilt. Mit N = 10.000 besteht eine 50% ige Chance, dass eine der Zahlen 1..1726 keine Zahl teilt, und eine von einer Milliarde, dass jede Zahl bis zu 2979 eine der Zahlen teilt.

Ich würde vorschlagen, dass für N zufällige Eingaben die Größe des Ergebnisses etwas größer als N / ln N ist; vielleicht so etwas wie N / ln N * (ln ln N) ^ 2. Hier ist der Grund:

Die Wahrscheinlichkeit , dass mindestens einer von N Zufallszahlen von einem Zufall d teilbar ist . Wenn d um N liegt, dann ist ungefähr 1 - exp (-1) ≤ 0,6321. Das ist für einen einzelnen Teiler; Die Wahrscheinlichkeit, dass jede von mehreren Zahlen d ≈ N ein Teiler von mindestens einer von N Zahlen ist, ist ziemlich gering, so dass das Maximum d signifikant kleiner als N ist.$1 - (1 - 1/d)^N$$1 - (1 - 1/d)^N$

Wenn d << N ist, dann ist .$1 - (1 - 1/d)^N ≈ 1 - exp (-N / d)$

Wenn d ≈ N / ln N dann .$1 - exp (-N / d) ≈ 1 - exp (- ln N) = 1 - 1/N$

Wir würden diese Wahrscheinlichkeiten für ungefähr N / ln N-Werte d addieren, aber für die meisten d wird das Ergebnis signifikant größer sein, so dass das größte d irgendwie größer als N / ln N, aber signifikant kleiner als N sein wird.

PS. Finden einer durch d teilbaren Zahl:

Wir wählen den größten Primfaktor p von d und untersuchen dann zuerst die Zahlen, von denen bereits bekannt war, dass sie durch p teilbar sind. Sagen Sie d = kp. Dann prüfen wir im Durchschnitt nur k Zahlen, die durch p teilbar sind, während wir dieses bestimmte d prüfen, und wir prüfen höchstens alle N Werte auf Teilbarkeit durch p insgesamt, für alle d, die durch p teilbar sind. Tatsächlich prüfen wir höchstwahrscheinlich weniger als N Werte für die meisten Primzahlen p, da der Algorithmus nach Überprüfung aller N Werte höchstwahrscheinlich endet. Wenn das Ergebnis also R ist, dann erwarte ich, dass weniger als N Werte durch jede Primzahl geteilt werden, die kleiner als R ist. Unter der Annahme von R ≤ N sind das ungefähr N ^ 2 / log N Prüfungen.

PS. Einige Tests ausführen

Ich habe diesen Algorithmus einige Male mit N = 1.000.000 Zufallszahlen> 0 ausgeführt. Der am wenigsten verbreitete Nicht-Divisor lag zwischen 68.000 und 128.000, wobei die überwiegende Mehrheit der Läufe zwischen 100.000 und 120.000 lag. Die Anzahl der Abteilungen lag zwischen 520 und 1800 Millionen, was viel weniger als (N / ln N) ^ 2 ist; Die meisten Fälle wurden zwischen 1000 und 1500 Millionen Abteilungen verwendet.