Najmniej powszechny niepodzielnik

$S$$d$$S$$\forall x \in S,\ d \nmid x$

Oznacz $n = |S|$i $C = \max(S)$ . Rozważ funkcję $F(x) =$ najmniejsza liczba pierwsza niepodzieląca $x$ . Łatwo zauważyć, że $F(x) \leq \log x$ . I przez zestaw $S$ , niech $F(S) =$ najmniej Prime że nie dzieli każdy z elementów $S$ . Mamy górną granicę

Dlatego prosty algorytm brutalnej siły, który wylicza wszystkie liczby od $1$ do $n \log C$ i sprawdza, czy nie dzieli żadnego elementu $S$ , jest wielomianowy i ma złożoność czasową $O(n^2 \log C)$ .

Innym sposobem rozwiązania problemu jest obliczenie wszystkich czynników dla każdego elementu $S$ i użycie ich w algorytmie brute-force, aby sprawdzić, czy $x$ jest odpowiedzią w czasie $O(1)$ . Ten algorytm ma złożoność czasową $O(n \cdot \min (\sqrt{C}, n \log C) + n \log C)$ i wykorzystuje pamięć $O(n \log C)$ , ponieważ nie musimy obliczać i czynniki przechowywać większą niż $n \log C$ . Dla małych $n$ i $C$ działa lepiej.

Szczegółowo algorytm składa się z dwóch części:

1. Zbuduj zestaw złożony ze wszystkich czynników wszystkich elementów , tj. Można to zrobić w czasie i pamięci . (Skąd to się bierze? Dla dowolnego elementu , możemy go uwzględnić przy użyciu próbnego faktoryzacji ze wszystkimi liczbami do lub wszystkich liczb pierwszych do , w zależności od tego, który jest mniejszy; dlatego każdy element można uwzględnić w czasie .)$\hat{S}$$S$

   $$\forall x \in S\ \forall f \le n \cdot \log C, \ (f \mid x \rightarrow f \in \hat{S})$$ $O(n \cdot \min (\sqrt{C}, n \log C))$$O(n \log C)$$S$$\sqrt{C}$$n \log C$$S$$O(\min (\sqrt{C}, n \log C))$

2. Znajdź minimalną liczbę . Ten krok wymaga czasu , jeśli sprawdza się, czy można wykonać w czasie .$d \notin \hat{S}$$O(|\hat{S}|) = O(n \log C)$$x \in \hat{S}$$O(1)$

Mam dwa pytania, którymi jestem zainteresowany:

1. Czy istnieje szybszy algorytm do rozwiązania problemu?
2. W przypadku danych i , w jaki sposób możemy zbudować zbiór z maksymalnym najmniej wspólnym niepodzielnikiem?$n$$C$$S$

Możliwe jest ulepszenie drugiego algorytmu poprzez zastosowanie lepszych algorytmów do faktoryzacji liczb całkowitych.

Istotne są tutaj dwa algorytmy faktoryzacji liczb całkowitych:

• GNFS może uwzględniać liczbę całkowitą z czasem działania .$\le C$$O(L_C[0.33,1.92])$

• ECM może znaleźć czynniki (jeśli istnieje) z czasem działania ; znalezienie wszystkich czynników zajmie tyle razy (co jest względnie małe w porównaniu z czasem działania ECM).$\le n \log C$$O(L_{n \log C}[0.5,1.41])$$O(\log C / \log(n \log C))$

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

To dość przerażająco wyglądające wyrażenie na czas wykonywania, ale ważne jest to, że jest to szybsze niż metody, o których wspomniałeś. W szczególności jest asymptotycznie znacznie mniejszy niż , tzn. GNFS jest znacznie szybszy niż wypróbowanie wszystkich możliwych czynników . Również jest asymptotycznie znacznie mniejsze niż , czyli ECM jest znacznie szybciej niż próbuje wszystkich możliwych czynników .$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$

Tak więc całkowity czas działania dla tej metody wynosi mniej więcej , a to jest asymptotycznie lepsze niż twoje pierwsza metoda i asymptotycznie lepsza niż druga metoda. Nie wiem, czy da się zrobić jeszcze lepiej.$\tilde{O}(n \min(L_C[0.33,1.92], L_{n \log C}[0.5,1.41]))$

Najmniej powszechny niepodzielnik może być tak duży jak N log C, ale jeśli liczby N są losowo rozmieszczone, to najmniej powszechny niepodzielnik jest prawdopodobnie znacznie mniejszy, prawdopodobnie dużo mniejszy niż N. Zbudowałbym tabele, z których liczby pierwsze są dzielnikami, których liczby.

Dla każdej liczby pierwszej p mamy indeks co oznacza, że ​​wszystkie liczby do tego indeksu zostały zbadane pod kątem podzielności przez p, i mamy listę wszystkich tych liczb, przez które można było podzielić.$k_p$

Następnie dla d = 2, 3, 4, ... próbujemy znaleźć liczbę podzielną przez d lub pokazać, że nie ma. Przyjmujemy największy czynnik p p. D. Następnie sprawdzamy wszystkie liczby, które można podzielić przez p, czy są one również podzielne przez d. Jeśli nie zostaną znalezione, sprawdzamy kolejne liczby za pomocą wskaźników> kątem podzielności przez p, aktualizując i listę liczb podzielnych przez p, i sprawdzamy, czy każda liczba jest podzielna przez d.$k_p$$k_p$

Aby sprawdzić, czy istnieje liczba podzielna przez p, sprawdzamy średnie liczby p. Później, jeśli sprawdzimy, czy istnieje liczba podzielna przez 2p, istnieje 50% szansa, że ​​musimy sprawdzić tylko jedną liczbę (tę, która jest podzielna przez p) i 50% szansy na sprawdzenie średnio o 2 p więcej liczb. Znalezienie liczby podzielnej przez 3p jest dość prawdopodobne i tak dalej, i nigdy nie sprawdzamy więcej niż N liczb pod kątem podzielności przez p, ponieważ są tylko N liczb.

Mam nadzieję, że to zadziała z około podzielnością$N^2 / log N$

PS. Jak duży byłby wynik dla liczb losowych?

Załóżmy, że mam N liczb losowych. Prawdopodobieństwo, że jedna z N liczb jest podzielna przez d wynosi 1 - (1 - 1 / d) ^ N. Zakładam, że prawdopodobieństwo, że każda z liczb 1 ≤ d ≤ k jest współczynnikiem jednej z liczb losowych, jest obliczane poprzez pomnożenie tych prawdopodobieństw (Ok, to trochę niepewne, ponieważ te prawdopodobieństwa prawdopodobnie nie są całkiem niezależne).

Przy takim założeniu, przy N = 1000, istnieje 50% szans, że jedna z liczb 1..244 nie podzieli żadnej liczby, a jedna na miliard, że każda liczba do 507 dzieli jedną z liczb. Przy N = 10 000 istnieje 50% szans, że jedna z liczb 1..1726 nie podzieli żadnej liczby, a jedna na miliard, że każda liczba do 2979 dzieli jedną z liczb.

Proponuję, aby dla N losowych danych wejściowych rozmiar wyniku był nieco większy niż N / ln N; może coś w stylu N / ln N * (ln ln N) ^ 2. Dlatego:

Prawdopodobieństwo, że co najmniej jeden z N liczb losowych jest podzielna przez losową d jest . Jeśli d jest w pobliżu N, to wynosi około 1 - exp (-1) ≈ 0,6321. To dotyczy pojedynczego dzielnika; istnieje szansa, że ​​każda z kilku liczb d ≈ N jest dzielnikiem co najmniej jednej z N liczb, są dość wąskie, więc maksymalne d będzie znacznie mniejsze niż N.$1 - (1 - 1/d)^N$$1 - (1 - 1/d)^N$

Jeśli d << N, to .$1 - (1 - 1/d)^N ≈ 1 - exp (-N / d)$

Jeżeli d ≈ N / ln N, a następnie .$1 - exp (-N / d) ≈ 1 - exp (- ln N) = 1 - 1/N$

Dodalibyśmy te prawdopodobieństwa dla wartości około N / ln N, ale dla większości d wynik będzie znacznie większy, więc największe d będzie jakoś większe niż N / ln N, ale znacznie mniejsze niż N.

PS. Znajdowanie liczby podzielnej przez d:

Wybieramy największy czynnik p p, a następnie najpierw badamy liczby, o których wiadomo, że są podzielne przez p. Powiedz d = kp. Następnie średnio sprawdzamy tylko liczby k, które są podzielne przez p, podczas sprawdzania tego konkretnego d, i sprawdzamy co najwyżej wszystkie wartości N pod kątem podzielności przez p ogółem, dla wszystkich d podzielnych przez p. W rzeczywistości najprawdopodobniej sprawdzamy mniej niż N wartości dla większości liczb pierwszych p, ponieważ po sprawdzeniu wszystkich N wartości algorytm najprawdopodobniej się kończy. Więc jeśli wynikiem jest R, to oczekuję, że mniejsze niż N wartości zostaną podzielone przez każdą liczbę pierwszą mniejszą niż R. Zakładając, że R ≤ N, to około N ^ 2 / log N kontroli.

PS. Przeprowadzanie niektórych testów

Uruchomiłem ten algorytm kilka razy z N = 1 000 000 liczb losowych> 0. Najmniej powszechny niepodzielnik wynosił od 68 000 do 128 000, przy ogromnej większości przebiegów od 100 000 do 120 000. Liczba podziałów wynosiła od 520 milionów do 1800 milionów, czyli o wiele mniej niż (N / ln N) ^ 2; w większości przypadków wykorzystano od 1000 do 1500 milionów dywizji.