Najmniej powszechny niepodzielnik

11

SdSxS, dx

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

F(S)F(lcm(S))F(Cn)nlogC.

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

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(nmin(C,nlogC)+nlogC) i wykorzystuje pamięć O(nlogC) , ponieważ nie musimy obliczać i czynniki przechowywać większą niż nlogC . 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 .)S^S

    xS fnlogC, (fxfS^)
    O(nmin(C,nlogC))O(nlogC)SCnlogCSO(min(C,nlogC))
  2. Znajdź minimalną liczbę . Ten krok wymaga czasu , jeśli sprawdza się, czy można wykonać w czasie .dS^O(|S^|)=O(nlogC)xS^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?nCS
SkyterX
źródło
1. Przez „wstępne obliczenie” rozumiałem przed uruchomieniem algorytmu brutalnej siły. 2. Złożoność faktoringu rzeczywiście subexponential patrz zaliczane do . C
SkyterX
@DW w punkcie 2, złożoność faktorowania jest podwykonawcza na długości ciągu bitów reprezentujących liczbę, ale SkyterX poprawnie twierdzi, że jest to , to znaczy proporcjonalne do pierwiastka kwadratowego z wielkości numer. O(C)
Lieuwe Vinkhuijzen
@LieuweVinkhuijzen, To nie wygląda mi dobrze. Złożoność faktoringu przy użyciu GNFS będzie podobna do , czyli znacznie mniej niż . Zobacz en.wikipedia.org/wiki/… . O(exp{1.9(logC)1/3(loglogC)2/3})O(C)
DW
Stwierdzenie, że druga metoda działa lepiej „dla małych i ” nie jest całkiem poprawne. Działa lepiej tylko wtedy, gdy . Zatem musi być duże, aby druga metoda działała lepiej (nie mała). nCnC/log(C)n
DW
@DW Masz rację, nie byłem świadomy złożoności GNFS.
Lieuwe Vinkhuijzen

Odpowiedzi:

6

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 .CO(LC[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).nlogCO(LnlogC[0.5,1.41])O(logC/log(nlogC))

Tutaj .Ln[α,c]=exp{c(logn)α(loglogn)1α}

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 .LC[0.33,1.92]CCLnlogC[0.5,1.41]nlogCnlogC

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.O~(nmin(LC[0.33,1.92],LnlogC[0.5,1.41]))

DW
źródło
Myślę, że każdy szybki algorytm dla tego problemu musi zawierać jakiś faktoryzacji zadanej Wejście . Sprawdzę te algorytmy faktoryzacji, ale nadal istnieje problem z ich prawidłowym testowaniem, co rodzi drugi problem, o którym wspominałem, o budowie zestawu z maksymalną odpowiedzią. SS
SkyterX
ECM znajduje jeden czynnik w podanym czasie. Jeśli wszystkie czynniki liczby są ≤ n log C, musisz powtórzyć algorytm, aż do log C / log (n log C) razy.
gnasher729,
3

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ć.kp

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

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ąN2/logN

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(11/d)N1(11/d)N

Jeśli d << N, to .1(11/d)N1exp(N/d)

Jeżeli d ≈ N / ln N, a następnie .1exp(N/d)1exp(lnN)=11/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.

gnasher729
źródło