Decyzja, czy interwał zawiera liczbę pierwszą

Jaka jest złożoność decyzji, czy przedział liczb naturalnych zawiera liczbę pierwszą? Wariant Sita Eratostenesa daje algorytm , w którym jest długością przedziału, a ukrywa czynniki polilarytmiczne w punkcie początkowym przedziału; czy możemy zrobić lepiej (pod względem samego )? $\tilde O(L)$ $L$ $\sim$ $L$

— Elliot Gorokhovsky
źródło

Nitpick: Sito Eratostenesa nie podaje jedynie czynników polikarytmicznych w punkcie początkowym, nawet dla przedziału długości 1. Rzeczywiście można sprawdzić, czy liczba jest liczbą pierwszą jest czasem, który jest liczbą polilogarytmiczną w liczbie (= wielomian wielkości reprezentacji), ale wymaga to algorytmu znacznie bardziej zaawansowanego niż sito Eratostenesa.

— Vanessa

@Squark Prawda, powinien był określić „pseudopierwszy względem danej podstawy czynnikowej”. Chociaż wraz ze wzrostem punktu początkowego przedziału czasowego oczekiwany koszt testowania pierwszeństwa spada do zera ...

— Elliot Gorokhovsky

Zastrzeżenie : Nie jestem ekspertem w teorii liczb.

Krótka odpowiedź : jeśli jesteś gotów do przyjęcia „rozsądnych liczbowo teoretyczne przypuszczenia”, to możemy powiedzieć, czy jest najlepszym w przedziale w czasie . Jeśli nie jesteś skłonny przyjąć takiego założenia, istnieje piękny algorytm dzięki Odlyzko, który osiąga , i uważam, że jest to najlepiej znany. $[n, n+\Delta]$ $\mathrm{polylog}(n)$ $n^{1/2 + o(1)}$

Bardzo pomocny link z dużą ilością świetnych informacji o ściśle powiązanym problemie : projekt PolyMath dotyczący deterministycznych algorytmów wyszukiwania liczb pierwszych .

Długa odpowiedź :

Jest to trudny problem, aktywny obszar badań i wydaje się być ściśle związany z trudną kwestią ograniczania luk między liczbami pierwszymi. Twój problem jest moralnie bardzo podobny do problemu znalezienia liczby pierwszej między a deterministycznie, który był ostatnio przedmiotem projektu PolyMath . (Jeśli chcesz naprawdę zagłębić się w te pytania, ten link jest doskonałym miejscem do rozpoczęcia.) W szczególności nasze najlepsze algorytmy dla obu problemów są zasadniczo takie same. $n$ $2n$

W obu przypadkach najlepszy algorytm zależy w dużej mierze od wielkości przerw między liczbą pierwszą. W szczególności, jeśli jest takie, że zawsze istnieje liczba pierwsza między i (i można obliczyć efektywnie), to zawsze możemy znaleźć liczbę pierwszą w czasie w następujący sposób. Aby ustalić, czy istnieje liczba pierwsza między i $f(n)$ $n$ $n + f(n)$ $f(n)$ $\mathrm{polylog}(n) \cdot f(n)$ $n$ , najpierw sprawdź, czy . Jeśli tak, wyślij tak. W przeciwnym razie po prostu iteruj przez liczby całkowite między i i przetestuj każdą z nich pod kątem pierwszeństwa i odpowiedz tak, jeśli znajdziesz liczbę pierwszą, a nie inaczej. (Można to zrobić deterministycznie, dlatego deterministyczne znalezienie liczby pierwszej między a jest tak ściśle związane z ustaleniem, czy liczba pierwsza występuje w określonym przedziale.) $n + \Delta$ $\Delta \geq f(n)$ $n$ $n + \Delta$ $n$ $2n$

$\mathrm{polylog}(n)$ $f(n) = O(\log^2 n)$ $n \geq 3$ $1/\log n$

$f(n) \leq O(\sqrt{n})$ $f(n) \leq O(\sqrt{n} \log n)$ $n^{o(1)}$

$\widetilde{O}(n^{0.525})$ $n^{0.025}$

— Noah Stephens-Davidowitz
źródło

k

$k$

k

$k$

π (x) := \# primes below \leq x

$\pi(x) := \text{\# primes below $\leq x$}$

p_{n + k} - p_{n}

$p_{n+k}-p_n$

p_{n + 1} - p_{n}

$p_{n+1}-p_n$