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

Data ostatniej modyfikacji:
2015-08-6
Autor: 
Krzysztof Omiljanowski
pracownik IM UWr
Dział matematyki: 
arytmetyka
Poziom edukacyjny: 
szkoła średnia z maturą

To pytanie nie jest jednoznaczne, bo...
nie wiadomo co to znaczy 'wzór' i nie wiadomo co to znaczy 'istnieje'.
Ale w ogóle co to za pytanie 'czy istnieje'? Niemal w każdym programie do obliczeń symbolicznych (CAS) istnieje funkcja podająca n-tą liczbę pierwszą (np. w MAPLEu jest ithprime(n) ). Z drugiej jednak strony szyfry, które kodują nasze dane w internecie, bazują na kłopotach z rozkładem liczb na czynniki pierwsze, więc gdyby taka funkcja istniała...

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 za(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ż 2n .

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:


przy f (10) (dla ułatwienia tylko oszacujemy z dołu liczbę obliczeń {x})

przy f (10) (podamy liczbę obliczeń {x})

przy f (n) (podamy liczbę obliczeń {x})

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.

 

Nudne

To jest nudne.

Nie dla cieniasów

Bo to nie dla takich cieniasów jak ty. Idź się najpierw douczyć. To niesamowite. Zawsze mnie uczyli, że w matematyce nie ma wzoru na n-tą liczbę pierwszą. Rozumiałem to dosłownie. A tu masz... To się rzeczywiście nawet całkiem łatwo zapisuje wzorem, tylko że nie o zapis tu chodzi, a o efektywny sposób obliczania. Nigdy nie miałem świadomości, że to dwie różne sprawy. Że można wyprodukować taki całkowicie poprawny i całkowicie bezużyteczny wzór. Fajnie, że coś takiego zamieściliście.

Masz rację

Rzeczywiście. Masz zupełną rację. Mnie też tego uczyli.

Trudno się dziwić

Po takich wywodach trudno się dziwić, że ludzie zniechecają się do matematyki!

Trzeba się wysilić

Nie wszystko przychodzi bez wysiłku. To jest dość trudne, ale jak dla mnie, jest napisane w sposób raczej zrozumiały, a przykłady dobrze wyjaśniają kolejne kroki.

Popieram przedmówcę

Popieram. Przeczytałem w miarę uważnie, ale bez specjalnego wysiłku. Napisane jest prosto, a przykłady wszystko wyjaśniają. Doszedłem do końca i bardzo mi się podobało.

A co powiecie na coś takiego?

Przypadkowo wymyśliłem takie coś:


n
-dowolna liczba pierwsza
m-liczba pierwsza większa od n
Dla małych liczb się sprawdza;)

MAPLE na to:

n=2, m=(n-1)!+n = 3, m = 3, true,
n=3, m=(n-1)!+n = 5, m = 5, true,
n=5, m=(n-1)!+n = 29, m = 29, true,
n=7, m=(n-1)!+n = 727, m = 727, true,
n=11, m=(n-1)!+n = 3628811, m = 3628811, true,
n=13, m=(n-1)!+n = 479001613, m = 29*6599*2503, false,
n=17, m=(n-1)!+n = 20922789888017, m =127*6385271*25801, false,
n=19, m=(n-1)!+n = 6402373705728019, m = 257*1483*1291883*13003, false,
n=23, m=(n-1)!+n = 1124000727777607680023 = 29*1049*117151079*315389197, false,
n=29, m=(n-1)!+n = 304888344611713860501504000029 = 123662437024088191*2465488728419, false

Wzór istnieć nie może

Moim zdaniem wzór istnieć nie może. Dlaczego? Każda liczba pierwsza to ni mniej, ni wiecej, tylko zapełnienie pewnej luki. Weźmy jako pierwszą - dwojkę - i zaznaczajmy na osi liczbowej co dwie jednostki od zera liczby parzyste. Jedziemy dalej i wpadamy na trojke, ktora się nie załapała do ciągu liczb parzystych, wiec ją zaznaczamy i jedziemy dalej. Postepujemy tak w nieskonczoność i każda natrafiona luka pomiędzy zaznaczonymi już  liczbami to liczba pierwsza. A dlaczego (moim zdaniem) wzór istnieć nie może? Bo przy każdym natrafieniu na liczbę pierwszą (zgodnie z opisaną procedurą) tworzy się nowy ciąg, który wszystko "psuje", a zatem, aby znać wzór, trzeba by znać wszystkie liczby pierwsze. A skoro ich jest nieskończenie wiele, to tego się nie da zrobic. A zresztą gdybyśmy znali wszystkie, to po co byłby nam wzór? :)

Precyzja zwala z nóg

Precyzja i logika powyższego wywodu zwalają z nóg. Po pierwsze, wzór (jak widać z artykułu) jest, więc nie można udawać, że go nie ma. Po drugie, każdy ciąg arytmetyczny jest nieskończony i to wcale nie przeszkadza, żeby opisać go wzorem. Jedno z drugim nie ma nic do rzeczy. Poza trzecie, jeśli zbiór jakichś liczb jest nieskończony, to z definicji nieskończoności nie można "znać wszystkich" tych liczb. Jedyne co można, to właśnie opisać je wzorem.

Udowodnij, że działa

Udowodnij, że działa na n-tą liczbę pierwszą, bez pominięcia żadnej.

Nie osłabiaj

Nie osłabiaj mnie gościu. Przecież w artykule masz wytłumaczone jak i dlaczego wzór działa. Wysil się trochę i spróbuj zrozumieć. Nie spamuj.

Działa!

Naprawdę dla małych liczb działa.

To teraz można udowodnić,

To teraz można udowodnić, że każda liczba parzysta P > 2 jest sumą dwóch liczb pierwszych o pewnych numerach n1 i n2, czyli:
P = f(n1)+ f(n2)

:)

Skoro jest wzór na liczby

Skoro jest wzór na liczby pierwsze, to po co ludzie ukrywają, że go nie ma?

Sądzę, że wzór istnieje,

Sądzę, że wzór istnieje, ale jest to "algorytm" o liczbie iteracji równej liczbie całkowita ze wzoru: pierwiastek z (x-c)/6 i gdzie: x testowana liczba, c reszta z dzienną x przez 3 tj. c={1,2}. Algorytm daje w wyniku informację o liczbach sąsiednich oraz o wszystkich dzielnicach liczby x potrzebnych do określenia czy x to liczba pierwsza. Wynika z niego też, że liczby pierwsze nie są przypadkowe.

Ciekawostka: mrożna

Ciekawostka: mrożna utworzyć tabelę w Excelu zawierającej argumenty (liczby naturalne) a pierwszej kolumnie i pierwszym wierszu. Pozostałe pola to funkcja argumentów (nad i po lewej wybranego pola). W tak utworzonej tabeli wszystkie wyniki funkcji są liczbami złożonymi. Zatem liczby nie występujące są liczbami pierwszymi i znalezienie maksymalnej liczby pierwszej ograniczają możliwości komputera.

Powrót na górę strony