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

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

[tex]\large \fbox{f(n)=???}[/tex]
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:

$$f(n)=\sum\limits_{k=2}^{2^n}\small\left(k\cdot\left[\frac{1}{1 \left|k-2 \sum\limits_{i=1}^{k-1}\left[-\left\{\frac{k}{i}\right\}\right]\right|}\right]\cdot \left[\frac{1}{1 \left|n - \sum\limits_{j=2}^{k}\left[\frac{1}{1 \left|j-2 \sum\limits_{i=1}^{j-1}\left[-\left\{\frac{j}{i}\right\}\right]\right|}\right] \right| } \right] \right) $$

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

   $$z_a(x)=\left[\frac{1}{1+\left|a-x\right|}\right]$$
przyjmuje wartość 1 dla argumentu x = a, a dla pozostałych przyjmuje wartość 0.

Zauważmy, że wartości wyrażenia $\frac{17}{i}$ 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 $\left\{\frac{17}{i}\right\}$ są różne od zera i mniejsze od 1.
Zauważmy dalej, że wszystkie wartości $\left[-\left\{\frac{17}{i}\right\}\right]$ są równe -1.

Natomiast wśród liczb $\left[-\left\{\frac{18}{i}\right\}\right]$ , dla i = 2,3,...,17, niektóre są równe 0. Które?

ĆWICZENIE Oblicz wartości sum:
   $\sum\limits_{i=2}^{16}\left[-\left\{\frac{17}{i}\right\}\right]$
   $\sum\limits_{i=2}^{17}\left[-\left\{\frac{18}{i}\right\}\right]$
   $\sum\limits_{i=2}^{28}\left[-\left\{\frac{29}{i}\right\}\right]$
   $\sum\limits_{i=2}^{23}\left[-\left\{\frac{24}{i}\right\}\right]$

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ą:
   $$g(k)=z_{(k-2)}\left(-\sum\limits_{i=1}^{k-1}\left[-\left\{\frac{k}{i}\right\}\right]\right)$$

Po uproszczeniu otrzymamy:
$$g(k)=\left[\frac{1}{1+\left|k-2+\sum\limits_{i=1}^{k-1}\left[-\left\{\frac{k}{i}\right\}\right]\right|}\right]$$

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

$$f(n)=\sum\limits_{k=2}^{+\infty}\left(k\cdot g(k)\cdot z_n\left(\sum\limits_{j=2}^{k}g(j)\right)\right)$$

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 $\sum\limits_{j=2}^{k}g(j)$ 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 $+\infty$ ?

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ą:

$$f(n)=\sum\limits_{k=2}^{2^n}\small\left(k\cdot\left[\frac{1}{1 \left|k-2 \sum\limits_{i=1}^{k-1}\left[-\left\{\frac{k}{i}\right\}\right]\right|}\right]\cdot \left[\frac{1}{1 \left|n - \sum\limits_{j=2}^{k}\left[\frac{1}{1 \left|j-2 \sum\limits_{i=1}^{j-1}\left[-\left\{\frac{j}{i}\right\}\right]\right|}\right] \right| } \right] \right) $$


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

$$f(n)=\sum\limits_{k=3}^{{2}^{n}}\small\left( k\cdot \mbox{sgn}\!\!\left( \prod\limits_{i=2}^{k-1}k \mbox{ mod } i \right)\! \cdot \! \left( 1 - \mbox{sgn}\!\!\left( \left| n - 1 - \sum\limits_{j=3}^{k}\mbox{sgn}\!\!\left( \prod\limits_{i=2}^{j-1} j\mbox{ mod }i \right) \right| \right) \right) \right) $$

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.

 

Niesamowite

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.

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ś: $$m=\frac{n!}{n}+n$$
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 więcej, tylko zapełnienie pewnej luki. Weźmy jako pierwszą - dwójkę - i zaznaczajmy na osi liczbowej co dwie jednostki od zera liczby parzyste. Jedziemy dalej i wpadamy na trójkę, która się nie załapała do ciągu liczb parzystych, wiec ją zaznaczamy i jedziemy dalej. Postępujemy tak w nieskończoność i każda 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 zrobić. 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 wspólnego. Po 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.

Działa!

Naprawdę dla małych liczb działa.

Skoro jest wzór na liczby

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

Ciekawostka: istnieje

Ciekawostka: istnieje sposób (podobny do sita Eratostenesa ale szybszy) na wyznaczenie liczb pierwszych tzw. Sito Małgorzaty opisany pod linkiem: https://1drv.ms/b/s!AsqwpKK-51whhhzzvgOxdib8Y_rW

Ciekawostka: rozmieszczenie

Ciekawostka: rozmieszczenie liczb pierwszych dobrze obrazuje Fraktal Rafała pokazany pod linkiem https://1drv.ms/b/s!AsqwpKK-51whhnSpIs0VqjqTgnrc

Przykład, że odległość

Przykład, że odległość liczb złożonych od danej liczby nie jest przypadkowa: https://1drv.ms/b/s!AsqwpKK-51whhyrXq3rEvKSwC62Q

W poprzednim wpisie

W poprzednim wpisie przedstawiłem prosty algorytm Krystyny obliczający rozkład liczb złożonych wokół danej liczby. Okazuje się, że reszty dzielenia danej liczby można też obliczyć iteracyjnie (algorytm: iteracje Kamila). Przykład zaumieściłem pod linkiem: https://1drv.ms/b/s!AsqwpKK-51whhyxst9k9X9-1unaI
Algorytm iteracyjny operuje na mniejszych liczbach i dlatego może być szybszy dla wielkich liczb. Również ten algorytm pozwala na przetwarzanie rozproszone.

liczby pierwsze wzór

Liczby pierwsze -zbiór liczb pierwszych wbrew przekonaniu jest to zbiór skończony Wskazuje na to fakt że na każde 10000 liczb ilość liczb pierwszych maleje. W liczbach z 100 000 000 cyfr może występować jedna lub 2 liczby pierwsze które i tak zostaną wyeliminowane .Nadmieniam że w niedługim czasie opublikuję swoją miesięczną pracę i przedstawię wzór na liczby pierwsze, Mogę jeszcze poinformować że wszystkie liczby pierwsze jestem w stanie utworzyć wykorzystując tylko 3 cyfry od 1 do 9
Nadmieniam że zbiór liczb pierwszych jest bardzo regularnym zbiorem.
Po analizie stawiam hipotezę, że liczby pierwsze są ukrytym zapisem binarnym .

Marian, to bardzo ciekawe,

Marian, to bardzo ciekawe, co piszesz. Koniecznie przedstaw wyniki swojej pracy.

Powrót na górę strony