Formuła dla liczb pierwszych

W teorii liczb wzór na liczby pierwsze to wzór generujący liczby pierwsze dokładnie i bez wyjątku. Nie jest znana taka formuła, która jest wydajnie obliczalna . Znanych jest wiele ograniczeń, pokazujących, czym taka „formuła” może, a czym nie może być.

Wzory oparte na twierdzeniu Wilsona

Prosta formuła jest

${\ Displaystyle f (n) = \ lewo \ lfloor {\ Frac {n! {\ bmod {(}} n + 1)} {n}} \ prawo\rpodłoga (n-1)+2}$

dla dodatniej liczby $.$ , gdzie $podłogi ,$ funkcją jest zaokrąglana w dół do najbliższej liczby całkowitej Zgodnie z twierdzeniem Wilsona ${\ displaystyle n + 1}$ jest liczbą pierwszą wtedy i tylko wtedy, gdy ${\ Displaystyle n! \ równoważnik n {\ pmod {n + 1}}}$ . Tak więc, gdy $displaystyle n + 1}$$\$ pierwszą, pierwszy czynnik w iloczynie staje się jeden, a formuła daje liczbę pierwszą. . Ale kiedy ${\ displaystyle n + 1}$ nie jest liczbą pierwszą, pierwszy czynnik staje się zerem, a formuła daje liczbę pierwszą 2. Ta formuła nie jest wydajnym sposobem generowania liczb pierwszych, ponieważ ocena ${\ Displaystyle n! {\ bmod {(}} n + 1)}$$n$$1$ { \ .

W 1964 Willans podał formułę

${\ Displaystyle p_ {n} = 1 +\sum _{i=1}^{2^{n}}\left\lfloor \left({\frac {n}{\sum _{j=1}^{i}\left\lfloor \left( \cos {\frac {(j-1)!+1}{j}}\pi \right)^{2}\right\rfloor}}\right)^{1/n}\right\rfloor}$

dla ${\ displaystyle n}$ th liczba pierwsza ${\ displaystyle p_ {n}}$ . Ta formuła również nie jest skuteczna. Oprócz pojawienia się ${\ Displaystyle (j-1)!}$ , oblicza się przez dodanie $p_ {n}}$$\ displaystyle$$displaystyle 1}$ ; na przykład ${\ Displaystyle p_ {5} = 1 + 1 + 1 + 1 + 1+1+1+1+1+1+1+0+0+\kropki +0=11}$ .

Formuła oparta na układzie równań diofantycznych

Ponieważ zbiór liczb pierwszych jest zbiorem przeliczalnym , zgodnie z twierdzeniem Matiyasewicza , można go otrzymać z układu równań diofantycznych . Jones i in. (1976) znaleźli wyraźny zestaw 14 równań diofantycznych w 26 zmiennych, takich że dana liczba k + 2 jest liczbą pierwszą wtedy i tylko wtedy, gdy ten układ ma rozwiązanie w nieujemnych liczbach całkowitych:

${\ Displaystyle \ alfa _ {0} = wz + h + jq = 0}$

${\ Displaystyle \ alfa _ {1} = (gk + 2g + k + 1) (h + j) + hz = 0}$

${\ Displaystyle \ alfa _ {2} = 16 (k + 1) ^ {3} (k + 2) (n + 1) ^ {2} + 1-f ^ {2 } = 0}$

${\ Displaystyle \ alfa _ {3} = 2n + p + q + ze = 0}$

${\ Displaystyle \ alfa _ {4} = e ^ {3} (e + 2) (a + 1) ^ {2} + 1-o ^ {2} = 0}$

${\ Displaystyle \ alfa _ {5} = (a ^ {2} -1) y ^ {2} + 1-x ^ {2} = 0}$

${\ Displaystyle \ alfa _ {6} = 16r ^ {2} y ^ {4} (a ^ {2} -1 ) + 1-u ^ {2} = 0}$

${\ Displaystyle \ alfa _ {7} = n + \ ell + vy = 0}$

${\ Displaystyle \ alfa _ {8} = (a ^ {2} -1) \ ell ^ {2} + 1-m ^ {2} = 0}$

${\ Displaystyle \ alfa _ {9} = ai + k + 1- \ ell -i = 0}$

${\ Displaystyle \ alfa _ {10} = ((a + u ^ {2} (u ^ {2} -a)) ^ {2}-1)(n+4dy)^{2}+1-(x+cu)^{2}=0}$

${\ Displaystyle \ alfa _ {11} = p + \ ell (an-1) + b (2an + 2a-n ^ {2} -2n-2) - m = 0}$

${\ Displaystyle \ alfa _ {12} = q + y(ap-1)+s(2ap+2a-p^{2}-2p-2)-x=0}$

${\ Displaystyle \ alfa _ {13} = z + p \ ell (ap) + t (2ap-p ^ {2} -1) -pm = 0}$

₀ 14 równań α , …, α ₁₃ można wykorzystać do stworzenia nierówności wielomianowej generującej liczby pierwsze w 26 zmiennych:

${\ Displaystyle (k + 2) (1- \ alfa _ {0} ^ {2} - \ alfa _ {1} ^{2}-\cdots -\alpha _{13}^{2})>0}$

tj:

${\ Displaystyle {\ rozpocząć {wyrównane} i (k + 2) (1- {} \\ [6pt] i [wz +h+jq]^{2}-{}\\[6pt]&[(gk+2g+k+1)(h+j)+hz]^{2}-{}\\[6pt]&[ 16(k+1)^{3}(k+2)(n+1)^{2}+1-f^{2}]^{2}-{}\\[6pt]&[2n+p +q+ze]^{2}-{}\\[6pt]&[e^{3}(e+2)(a+1)^{2}+1-o^{2}]^{2 }-{}\\[6pt]&[(a^{2}-1)y^{2}+1-x^{2}]^{2}-{}\\[6pt]&[16r^ {2}y^{4}(a^{2}-1)+1-u^{2}]^{2}-{}\\[6pt]&[n+\ell +vy]^{2} -{}\\[6pt]&[(a^{2}-1)\ell ^{2}+1-m^{2}]^{2}-{}\\[6pt]&[ai+ k+1-\ell -i]^{2}-{}\\[6pt]&[((a+u^{2}(u^{2}-a))^{2}-1)( n+4dy)^{2}+1-(x+cu)^{2}]^{2}-{}\\[6pt]&[p+\ell (an-1)+b(2an+2a- n^{2}-2n-2)-m]^{2}-{}\\[6pt]&[q+y(ap-1)+s(2ap+2a-p^{2}-2p- 2)-x]^{2}-{}\\[6pt]&[z+p\ell (ap)+t(2ap-p^{2}-1)-pm]^{2})\\ [6pt]&>0\end{wyrównane}}}$

jest nierównością wielomianową w 26 zmiennych, a zbiór liczb pierwszych jest identyczny ze zbiorem wartości dodatnich przyjmowanych przez lewą stronę, gdy zmienne a , b , …, z rozciągają się na nieujemne liczby całkowite.

Ogólne twierdzenie Matiyasewicza mówi, że jeśli zbiór jest zdefiniowany przez układ równań diofantycznych, to można go również zdefiniować przez układ równań diofantycznych tylko w 9 zmiennych. Stąd istnieje wielomian generujący liczby pierwsze, jak powyżej, z tylko 10 zmiennymi. Jej stopień jest jednak duży (rzędu 10 ⁴⁵ ). Z drugiej strony istnieje też taki układ równań stopnia tylko 4, ale w 58 zmiennych.

Formuła Millsa

Pierwszy taki znany wzór został ustalony przez WH Millsa ( 1947 ), który udowodnił, że istnieje taka liczba rzeczywista A , że jeśli

${\ Displaystyle d_ {n} = A ^ {3 ^ {n}}}$

Następnie

${\ Displaystyle \ lewo \ lfloor d_ {n} \ prawo \ rfloor = \ lewo \ lfloor A ^ {3 ^ {n}} \ prawo \ rfloor}$

jest liczbą pierwszą dla wszystkich dodatnich liczb całkowitych n . Jeśli hipoteza Riemanna jest prawdziwa, to najmniejsze takie A ma wartość około 1,3063778838630806904686144926... (sekwencja A051021 w OEIS ) i jest znane jako stała Millsa . Ta wartość powoduje powstanie liczb pierwszych ${\ Displaystyle \ lewo \ lfloor d_ {1} \ prawo \ rfloor = 2}$ , ${\ Displaystyle \ lewo \ lfloor d_ {2} \ prawo \ rfloor = 11}$ , ${\ Displaystyle \ lewo \ lfloor d_ {3} \ prawo \ rfloor = 1361}$ , ... (sekwencja A051254 w OEIS ). Bardzo niewiele wiadomo o stałej A (nawet czy jest wymierna ). Ta formuła nie ma praktycznej wartości, ponieważ nie ma znanego sposobu obliczania stałej bez znajdowania liczb pierwszych.

we wzorze nie ma nic specjalnego w funkcji podłogi . Tóth udowodnił, że istnieje również taka $,$ że

${\ Displaystyle \ lceil B ^ {r ^ {n}} \ rceil}$

$jest$ również reprezentacją liczb ( Tóth )

W przypadku , wartość stałej ${\ displaystyle r =$ się od 1,24055470525201424067 ... Kilka pierwszych wygenerowanych liczb pierwszych to: $3}$

${\ Displaystyle 2,7 337,38272739,56062005704198360319209,176199995814327287356671209104585864397055039072110696028654438846269,\ldots }$

Nie przyjmując hipotezy Riemanna, Elsholtz opracował kilka funkcji reprezentujących liczby pierwsze , podobnych do funkcji Millsa. Na przykład, jeśli ${\ displayStyle A \ ok. 1.00536773279814724017}$ , to ${\ displayStyle \ left \ lfloor a^{10^{10n}}} \ r -rOROR}$ jest premiera dla wszystkich pozytywnych Intece. ${\ displaystyle n}$ . Podobnie, jeśli $\ Displaystyle$$\ lewo \ lfloor A ^ {3 ^ {13n}} \ prawo \ rfloor }$ jest wszystkich dodatnich liczb całkowitych ${\ displaystyle n}$ .

Formuła Wrighta

Inna formuła generująca liczby pierwsze, podobna do formuły Millsa, pochodzi z twierdzenia EM Wrighta . Udowodnił, że istnieje liczba rzeczywista α taka, że ​​jeśli

${\ Displaystyle g_ {0} = \ alfa}$ i

${\ Displaystyle g_ {n + 1} = 2 ^ {g_ {n}}}$ dla ${\ Displaystyle n \ geq 0}$ ,

Następnie

${\ Displaystyle \ lewo \ lfloor g_ {n} \ prawo \ rfloor = \ lewo \ lfloor 2 ^ {\ kropki ^ {2 ^ {2 ^ {\ alfa}}} }\prawo\rpodłoga }$

jest liczbą pierwszą dla wszystkich ${\ displaystyle n \ geq 1}$ . Wright podaje pierwsze siedem miejsc po przecinku takiej stałej: ${\ displaystyle \ alpha = 1,9287800}$ . Ta wartość daje początek liczbom pierwszym ${\ Displaystyle \ lewo \ lfloor g_ {1} \ prawo \ rfloor = \ lewo \ lfloor 2 ^ {\ alfa} \ prawo \ rfloor = 3 }$ , ${\ Displaystyle \ lewo \ lfloor g_ {2} \ prawo \ rfloor = 13}$ i ${\ Displaystyle \ lewo \ lfloor g_ {3} \ prawo \ rfloor = 16381}$ . ${\ Displaystyle \ lewo \ lfloor g_ {4} \ prawo \ rfloor}$ jest parzysta , a więc nie jest liczbą pierwszą. α ${\ Displaystyle \ alpha = 1,9287800 + 8,2843 \ cdot 10 ^ {-4933}}$ ⌊ $\ Displaystyle \ lewo \ lfloor g_ {1} \ prawo \ rfloor }$ , ${\ Displaystyle \ lewo \ lfloor g_ {2} \ prawo \ rfloor}$ i ${\ Displaystyle \ lewo \ lfloor g_ {3} \ prawo \ rfloor}$ pozostają niezmienione, podczas gdy ${\ Displaystyle \ lewo \ lfloor g_ {4} \ prawo \ rfloor}$ to liczba pierwsza z 4932 cyframi. Tej sekwencji $nie$$można$ rozszerzyć poza większej liczby Podobnie jak wzór Millsa iz tych samych powodów, wzór Wrighta nie może być użyty do znalezienia liczb pierwszych.

Funkcja reprezentująca wszystkie liczby pierwsze

$Displaystyle n \ geq 2$ uwagę stałą (sekwencja $)$ w OEIS , dla sekwencję

${\ Displaystyle f_ {n} = \ lewo \ lfloor f_ {n-1} \ prawo \ rfloor (f_ {n} -1}-\lewa\lpodłoga f_{n-1}\prawa\rpodłoga +1)}$

 

 

 

 

()

gdzie $_$ podłogi . _ Wtedy ${\ Displaystyle n \ geq 1}$ , ${\ Displaystyle \ lewo \ lfloor f_ {n} \ prawo \ rfloor}$ równa się ${\ Displaystyle n}$ th liczba pierwsza: ${\ Displaystyle \ lewo \ lfloor f_ {1} \ prawo \ rfloor = 2}$ , ${\ Displaystyle \ lewo \ lfloor f_ {2} \ prawo \ rfloor = 3}$ , ${\ Displaystyle \ lewo \ lfloor f_ {3} \ prawo \ rfloor = 5}$$.$ w artykule jest wystarczająco dokładna dla równania ( 1 ), aby wygenerować liczby pierwsze do 37, ${\ displaystyle 12}$ th liczba pierwsza.

Dokładna wartość , która generuje wszystkie liczby pierwsze, jest podana przez szybko zbieżny szereg $\ displaystyle f_ {1}}$ {

${\ Displaystyle f_ {1} =\sum _{n=1}^{\infty}{\frac {p_{n}-1}{P_{n}}}={\frac {2-1}{1}}+{\frac { 3-1}{2}}+{\frac {5-1}{2\cdot 3}}+{\frac {7-1}{2\cdot 3\cdot 5}}+\cdots ,}$

gdzie $}}$${n}} }$$n$ jest pierwszą, a iloczynem wszystkich liczb pierwszych mniejszych niż $p_$ . Im więcej cyfr $1$ , tym więcej równań liczb pierwszych ( ) wygeneruje Na przykład możemy użyć 25 wyrazów w szeregu, używając 25 liczb pierwszych mniejszych niż 100, aby obliczyć następujące dokładniejsze przybliżenie:

${\ displaystyle f_ {1} \ simeq 2,920050977316134712092562917112019.}$

To ma wystarczającą liczbę cyfr do równania ( 1 ), aby ponownie uzyskać 25 liczb pierwszych mniejszych niż 100.

Podobnie jak w przypadku powyższego wzoru Millsa i wzoru Wrighta, aby wygenerować dłuższą listę liczb pierwszych, musimy zacząć od znajomości większej liczby cyfr stałej początkowej , co w tym przypadku wymaga fa 1 {\ displaystyle $}$ dłuższą listę liczb pierwszych w swoich obliczeniach.

Wzory Plouffe'a

W 2018 roku Simon Plouffe wymyślił zestaw wzorów na liczby pierwsze. Podobnie jak formuła Millsa, mają one postać

${\ Displaystyle \ lewo \ {a_ {0} ^ {r ^ {n}} \ prawo \}}$

gdzie $jest funkcją$ do najbliższej liczby całkowitej $r = 5/4}$ przykład z $\ Displaystyle$ 4 to 113, 367, 1607, 10177, 102217 ${\ Displaystyle a_ {0} = 10 ^ {500} + 961 + \ varepsilon}$ i ${\ Displaystyle r = 1,01}$ z określoną liczbą między 0 a ${\ Displaystyle \ varepsilon}$ i połowę, Plouffe odkrył, że może wygenerować sekwencję 50 prawdopodobnych liczb pierwszych (z dużym prawdopodobieństwem bycia liczbą pierwszą). Przypuszczalnie istnieje ε takie, że ta formuła da nieskończoną sekwencję rzeczywistych liczb pierwszych. Liczba cyfr zaczyna się od 501 i za każdym razem wzrasta o około 1%.

Wzory pierwsze i funkcje wielomianowe

Wiadomo, że nie istnieje niestała funkcja wielomianowa P ( n ) o współczynnikach całkowitych, która daje w wyniku liczbę pierwszą dla wszystkich liczb całkowitych n . Dowód jest następujący: załóżmy, że taki wielomian istnieje. Wtedy P (1) oceniłoby się na liczbę pierwszą p , więc ${\ Displaystyle P (1) \ równoważnik 0 {\ pmod {p}}}$ . Ale dla dowolnej liczby całkowitej k , ${\ Displaystyle P (1 + kp) \ równoważnik 0 {\ pmod {p}}}$ również, więc ${\ displaystyle P(1+kp)}$ nie może być również liczbą pierwszą (ponieważ byłaby podzielna przez p ), chyba że byłaby samą p . $_$ jedynym _ _ _ To samo rozumowanie prowadzi do jeszcze silniejszego wyniku: nie istnieje żadna niestała funkcja wielomianowa P ( n ), która dałaby liczbę pierwszą dla prawie wszystkich liczb całkowitych n .

Euler po raz pierwszy zauważył (w 1772 r.), że wielomian kwadratowy

${\ Displaystyle P (n) = n ^ {2} + n + 41}$

jest liczbą pierwszą dla 40 liczb całkowitych n = 0, 1, 2, ..., 39, z odpowiednimi liczbami pierwszymi 41, 43, 47, 53, 61, 71, ..., 1601. Różnice między wyrazami to 2, 4 , 6, 8, 10... Dla n = 40 daje liczbę kwadratową 1681, która jest równa 41 × 41, najmniejszej liczbie złożonej dla tego wzoru dla n ≥ 0. Jeśli 41 dzieli n , dzieli P ( n ) też. Ponadto, ponieważ P ( n ) można zapisać jako n ( n + 1) + 41, jeśli zamiast tego 41 dzieli n + 1, to również dzieli P ( n ). Zjawisko to jest związane ze spiralą Ulama , która jest również niejawnie kwadratowa, oraz z numerem klasy ; ten wielomian jest powiązany z liczbą Heegnera ${\ Displaystyle 163 = 4 \ cdot 41-1}$ . Istnieją $)$ Eulera liczbom _ .

Biorąc pod uwagę dodatnią liczbę całkowitą S , może istnieć nieskończenie wiele c takich , że wyrażenie n ² + n + c jest zawsze względnie pierwsze względem S . Liczba całkowita c może być ujemna, w takim przypadku występuje opóźnienie przed wytworzeniem liczb pierwszych.

Wiadomo, na podstawie twierdzenia $b$ postępach arytmetycznych liniowe funkcje wielomianowe o ile a i są względnie (chociaż żadna taka funkcja nie przyjmie wartości pierwszych dla wszystkich wartości n ). Co więcej, twierdzenie Greena – Tao mówi, że dla dowolnego k istnieje para a i b , z właściwością, że $\ Displaystyle L (n) = an + b}$ jest liczbą pierwszą dla dowolnego n od 0 do k - 1. Jednak od 2020 roku najbardziej znanym wynikiem tego typu jest k = 27:

${\ Displaystyle 224584605939537911 + 18135696597948930n}$

jest liczbą pierwszą dla wszystkich n od 0 do 26. Nie wiadomo nawet, czy istnieje wielomian jednowymiarowy stopnia co najmniej 2, który przyjmuje nieskończoną liczbę liczb pierwszych; patrz hipoteza Bunyakovsky'ego .

Możliwa formuła wykorzystująca relację powtarzalności

Inny główny generator jest zdefiniowany przez relację powtarzania

${\ Displaystyle a_ {n} = a_ {n-1} + \ gcd (n, a_ {n-1}) ,\kwadrat a_{1}=7,}$

gdzie gcd( x , y ) oznacza największy wspólny dzielnik x i y . Sekwencja różnic a _{n +1} − a _n zaczyna się od 1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 , 1, 47, 3, 1, 5, 3, ... (sekwencja A132199 w OEIS ). Rowland (2008) udowodnił, że ten ciąg zawiera tylko jedynki i liczby pierwsze. Jednak nie zawiera wszystkich liczb pierwszych, ponieważ wyrażenia gcd( n + 1, a _n ) są zawsze nieparzyste , a więc nigdy nie są równe 2. 587 to najmniejsza liczba pierwsza (inna niż 2), która nie pojawia się w pierwszych 10 000 wyników które są różne od 1. Niemniej jednak w tym samym artykule przypuszczano, że zawiera wszystkie nieparzyste liczby pierwsze, mimo że jest raczej nieefektywny.

Zauważ, że istnieje trywialny program, który wylicza wszystkie i tylko liczby pierwsze, a także te bardziej wydajne , więc takie relacje rekurencyjne są bardziej kwestią ciekawostki niż jakiegokolwiek praktycznego zastosowania.

Zobacz też

• Twierdzenie o liczbach pierwszych

Dalsza lektura

•   Regimbal, Stephen (1975), „Wyraźny wzór na k-tą liczbę pierwszą”, Mathematics Magazine , Mathematical Association of America, 48 (4): 230–232, doi : 10,2307/2690354 , JSTOR 2690354 .
• Venugopalan. Wzór na liczby pierwsze, liczby bliźniacze, liczba liczb pierwszych i liczba liczb bliźniaczych . Proceedings of the Indian Academy of Sciences-Matematical Sciences, tom. 92, nr 1, wrzesień 1983, s. 49–52 errata

Linki zewnętrzne

• Eric W. Weisstein , Formuły liczb pierwszych ( wielomian liczb pierwszych ) w MathWorld .