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.

Liczby pierwsze

Nie ma możliwości uzyskać liczb pierwszych za pomocą jedynie 3 cyfr i to jeszcze z przedziału 1 do 9...
Skąd mam pewność?
Dlatego, że napisałem definicje i wyprowadziłem wzory (podkreślam liczbę mnogą!).
Tą wiedzą dysponowaliśmy już dano temu, nim świat został zniszczony...

Jedyna prawda z tego, to, że przypuszczalnie zbiór liczb pierwszych jest skończony, bowiem pomimo tego, że każdy kolejny blok w którym znajdują się liczby pierwsze stale zwiększa się, to ilość liczb pierwszych bardzo powoli zmniejsza się.
Tym samym oznacza to, że dąży on do wartości zerowej, a więc wskazuje na to, że powinna istnieć ostatnia liczba pierwsza - "klucz", pytanie do czego, skoro pewne kręgi są w stanie za znalezienie jego oddać wiele "śmieciowych skarbów"...

Co więcej, nie jest prawdą, że liczby pierwsze występują chaotycznie, gdyż są one jak najbardziej uporządkowane, a ich występowanie jest w pewnym sensie bardzo uporządkowane...
Kto nie dotarł przynajmniej do tego miejsca, to jest daleko w "lesie" i nigdy nie znajdzie wzoru na liczby pierwsze...

Pozdrawiam wszystkich i życzę sukcesów w poszukiwaniu.

Zamiast plików w Excelu

Zamiast plików w Excelu fraktal Rafała można opisać wzorem:
f(y)= n + x * (-1)^{n} + (3*x + 0.5 - 0.5 * (-1)^{x}) * (n + 0.5 - 0.5 * (-1)^{n})
gdzie n > 0 i x >0 oraz x,n należy do liczb naturalnych. Liczba x określa kolejne wystąpienie liczby "złożonej" dla n. Dodatkowo zachodzi zależność jezeli:
x parzyste, n parzyste to f(y) parzyste
x parzyste, n nieparzyste to f(y) nieparzyste
x nieparzyste, n parzyste to f(y) nieparzyste
x nieparzyste, n nieparzyste to f(y) parzyste

Związek liczb złożonych z fraktalem Rafała jest następujący:
f(z)= 3 * f(y) + 1.5 - 0.5 *(-1)^{x+n}
gdzie f(y) funkcja generująca liczby tworzące fraktal Rafał dla wartości x i n.

Jeżeli dla wzoru f(y) wprowadzimy ograniczenie x >= n oraz f(y) <= Ym to otrzymamy tzw. sito Małgorzaty w przedziale liczb naturalnych (1,Ym).
Związek wartości Y z przedziału (1,Ym) z liczbami (złożonymi i pierwszymi) jest następujący:
f(L)= 3 * Y + 2 dla wartości nieparzystych Y lub
f(L)= 3 * Y + 1 dla wartości parzystych Y
oraz f(L) jest liczbą złożoną jeżeli wartość Y została wyznaczona przez f(y).

nie jestem matematykiem i

nie jestem matematykiem i mam swoje lata ale myślę że mogę podać 12 liczb jeszcze nie odkrytych z których jedna będzie liczbą pierwsza jeszcze nie znalezioną trzeba tylko sprawdzić te 12 liczb tak można znaleźć następną i następną pomijając po drodze wiele liczb leżących jedna za drugą sprawdziłem to do 2 bilionów bazując oczywiście na liczbach znanych i się sprawdziło Mogę podać to za dużo powiedziane ale sposób jest prosty

trywialny problem?

Witam
tez nie jestem matematykiem, ale być może domyłam się na czym ta metoda może polegać. Jakiś czas temu wykonałem trochę testów, realizując pewien pomysł i okazuje się, że można określić, które liczby są pierwszymi. Może to zakrawać na szaleństwo, ale problem okazał się dość trywialny. Nie wiem, czy da się z tego stworzyć wzór, ale sama metoda działa, ale testowałem ją jedynie na relatywnie małych wartościach (kilka milionów): braki techniczne. Miejsca występowania liczb pierwszych w pewnym przedziale są stałe, pozostałe miejsca są eliminowane przez pewne czynniki, które chyba dało się ustalić i które są obliczalne.
Jeśli ktoś to przeczytał, może uznać to za bredzenie szaleńca, sam też się zastanawiam od jakiegoś czasu, czy to co ustaliłem naprawdę ma jakiś sens (tak,działa, ale może wszyscy to wiedzą), a może robię jakiś logiczny błąd.
A może to przekleństwo liczb pierwszych?

Jak już pisałem fraktal

Jak już pisałem fraktal Rafała można opisać wzorem:
f(y)= n + x * (-1)^{n} + (3*x + 0.5 - 0.5 * (-1)^{x}) * (n + 0.5 - 0.5 * (-1)^{n})
gdzie n > 0 i x >0 oraz x, n należy do liczb naturalnych.

W celu ułatwienia zrozumienia dalszej analizy zrobię małe podsumowanie:
1) Sito Małgorzaty to fraktal Rafała przy założeniu, że x>=n oraz f(y) gdzie Ym wyznacza górną granicę sita tj. wartości f(y) należą do przedziału (1,Ym).
Dodatkowo dla n=f(yn) dla dowolnego x wartości f(y) można pominąć – nie mają
wpływu na wynik sita, a jedynie wykonuje się mniej obliczeń.
2) Dla wartości f(y) fraktala Rafała zachodzą zależności:
- x parzyste, n parzyste to f(y) parzyste
- x parzyste, n nieparzyste to f(y) nieparzyste
- x nieparzyste, n parzyste to f(y) nieparzyste
- x nieparzyste, n nieparzyste to f(y) parzyste
Poszczególne warianty sita liczb będą tworzone poprzez branie do dalszej
analizy parzystych lub nieparzystych wierszy tabeli:
wiersze (1,Ys), kolumny n.
(n powiązane z Ly – Ly=3 * n + 1,5 – 0,5 * (-1)^n)
3) Szczególną uwagę można zwrócić na wynik działania fraktal Rafała dla n=1 i n=2
dla dowolnego x. W analizie posłuży to do wyliczenia „podstawy” wyznaczenia różnych wariantów sita liczb.
4) Analizowane będą różne warianty sita liczb – dające wartość f(ys) w przedziale
(1,Ys). Jeżeli związek pomiędzy wartościami ys a y (zależny jest od wyboru wierszy parzystych i nieparzystych tabeli wspomnianej w punkcie 2) określimy jako funkcję y=P(ys), to wartości ys z przedziału (1,Ys) z liczbami (złożonymi i pierwszymi) dla każdego wariantu sita liczb można zapisać ogólnie:
f(L)= 3 * P(ys) + 2 dla wartości nieparzystych P(ys) lub
f(L)= 3 * P(ys) + 1 dla wartości parzystych P(ys)
oraz f(L) jest liczbą złożoną jeżeli wartość ys została wyznaczona przez f(ys).

Korzystając z możliwości wyboru wierszy parzystych (sito_p) lub nieparzystych (sito_n) tworzymy dwa niezależne sita liczb. Dalsze przetwarzanie i analiza sita liczb w obu przypadkach jest podoba:
- dla każdej kolumny n mamy pierwszą wyznaczoną wartość ys1,
którą można określić jako podstawa;
- pozostałe wartości dla kolumny n są w odległości Ly
(Ly=3 * n + 1,5 – 0,5 * (-1)^n).

Jeżeli dla jednego z wybranych sit liczb zaczniemy znowu wybierać wiersze parzyste i nieparzyste tworzymy kolejny wariant sita liczb. Powtarzając tę czynność można tworzyć kolejne sita liczb. Zauważyć można, że tak tworzone sito licz zawiera w kolumnie n pierwszą wartość ys1, którą można nazwać podstawą tworzenia sita. Pozostałe wartości w kolumnie n są zawsze w odległości Ly.
Dodatkowo jeżeli wartość ys1 ma być uwzględniona w docelowy sicie liczb, a jest w odrzucanych wierszach, to bierzemy ys1+Ly jako podstawę do kolejnego sita.

Jako ciekawostkę mogę podać sito liczb utworzone poprzez trzykrotnie wybranie parzystych wierszy. Jego zaletą jest to, że wyrazy ys1 dla kolejnych kolumn n tworzą ciąg, którego elementy różnią się o wartość n/(1,5 - 0,5 * (-1)^n) oraz wyrazy ys1 odpowiadają kwadratom liczb Ly. Pozostałe wartości ys w danej kolumnie są w odległości Ly.

Ostatnim zdaniu we wzorze

Ostatnim zdaniu we wzorze wkradł się błąd we wzorze - poprawiony fragmemt zamieszczam poniżej:

Jako ciekawostkę mogę podać sito liczb utworzone poprzez trzykrotnie wybranie parzystych wierszy. Jego zaletą jest to, że wyrazy ys1 dla kolejnych kolumn n tworzą ciąg, którego elementy różnią się o wartość n/(1,5 + 0,5 * (-1)^n) oraz wyrazy ys1 odpowiadają kwadratom liczb Ly. Pozostałe wartości ys w danej kolumnie są w odległości Ly.

Powrót na górę strony