Czy istnieje wzór na n-tą liczbę pierwszą?

Dość filozofowania. Taka funkcja jest. Poniżej przedstawiamy jeden z jej możliwych wzorów:

Czyż nie piękny?

Piękny, ale... bezużyteczny. Mimo wszystko zobaczmy najpierw, że jest poprawny (o  bezużyteczności porozmawiamy na końcu).

By przedstawić, jak wymyślono ten wzór, wprowadzimy pomocnicze funkcje z_a(x) oraz g(k). Uwaga: stale trzeba pamiętać, że [x] i {x} oznaczają część całkowitą i część ułamkową liczby x; (np.: [2,3] = , [0,1] = , [-2,3] = , oraz {2,3} = , {-1} = , {-2,3} = ).

Najpierw zauważmy, że dla ustalonej wartości parametru a, funkcja

  
przyjmuje wartość 1 dla argumentu x = a, a dla pozostałych przyjmuje wartość 0.

Zauważmy, że wartości wyrażenia dla i = 2,3,...,16, wszystkie są niecałkowite, bo 17 nie dzieli się przez żadną liczbę naturalną mniejszą od niej i większą od 1.

Zatem części ułamkowe są różne od zera i mniejsze od 1.
Zauważmy dalej, że wszystkie wartości są równe -1.

Natomiast wśród liczb , dla i = 2,3,...,17, niektóre są równe 0. Które?

ĆWICZENIE Oblicz wartości sum:
  
  
  
  

Te obserwacje można uogólnić. Pozwala to napisać funkcję g(k), która:
- przyjmuje wartość 1, gdy k jest liczbą pierwszą
- przyjmuje wartość 0, gdy k jest liczbą złożoną:
  

Po uproszczeniu otrzymamy:
  

Teraz możemy zdefiniować tytułową funkcję  f (n) :

Zauważmy, że w każdym składniku tej sumy jest iloczyn trzech czynników. Wśród nich:
- pierwszy, k jest zawsze różny od zera,
- drugi, g(k), jest różny od zera (równy 1), gdy k jest liczbą pierwszą,
- trzeci jest różny od zera (równy 1), gdy suma jest równa n, to znaczy gdy jest dokładnie n liczb pierwszych nie większych od k.

Zauważmy, że ta 'niby' nieskończona suma ma tylko jeden niezerowy składnik, równy właśnie szukanej n-tej liczbie pierwszej. Co zatem wstawić w miejsce ?

Tu wykorzystamy niebanalne twierdzenie Czebyszewa:

TWIERDZENIE. Pomiędzy liczbą naturalną m i 2m leży co najmniej jedna liczba pierwsza.

Z tego twierdzenia wynika (nietrudno)

WNIOSEK. n-ta liczba pierwsza jest nie większa niż 2ⁿ .

Zatem nieskończoną sumę zastąpimy skończoną:

Zbadamy teraz dlaczego powyższy wzór jest nieprzydatny. Pokażemy jego tzw. złożoność obliczeniową badając, ile razy obliczana jest funkcja {x}, część ułamkowa, przy:

A oto inny, podobny wzór:  dla n > 1

Można, podobnie jak wyżej, przeanalizować jego poprawność i zbadać jego złożoność obliczeniową.

Powyższy tekst jest ledwie wstępem do tematyki przedstawionej w książce: Paulo Ribenboim, Mała księga wielkich liczb pierwszych, WNT 1997 (rozdział trzeci jest zatytułowany: Czy istnieją funkcje określające liczby pierwsze?). Gorąco namawiam do lektury.