Opracowałem uproszczony wzór na N-tą liczbę pierwszą, który działa dobrze dla bardzo dużych liczb, a który można łatwo zapamiętać i liczyć nawet na kalkulatorze albo w excelu, nie potrzeba żadnych specjalnych narzędzi ani super wysokiej precyzji obliczeń aby dostać dość dokładny wynik.
f(N) ≈ N*(ln(N) + ln(ln(N)) - 0,953)
Ponieważ wynik jest liczbą rzeczywistą to należy ją zaokrąglić do najbliższej liczby nieparzystej.
(np 4.1 zaokrąglamy do 5 a 7,9 zaokrąglamy do 7)
Jest spora szansa że trafimy w ten sposób właśnie na N-tą liczbę pierwszą, a jeśli nawet nie trafi się dokładnie to różnica jest minimalna.
(błąd nie przekracza 0,1 ‰ dla dużych liczb, a 0,1 ‰ to tyle co nic).
Gdyby ktoś potrzebował dokładniej to można wyznaczyć dokładniej tą stałą która we wzorze występuje, jednak ponieważ logarytm jest funkcją gładką a liczby pierwsze występują schodkowo to osiągniemy tylko to, że funkcja będzie przez te schody przechodzić ale się z nimi nie pokryje.
Jak podjazd dla wózka który może być dowolnie blisko stopni, ale nie położy się na nich jak dywanik bo musi być gładki aby wózek podjechał.
Dla wielu zastosowań takie przybliżenie wystarczy, wiedząc na jakiej wysokości jest podjazd nawet po ciemku da się wymacać stopą schodek który jest obok podjazdu.
Wzór jest przewidziany dla dużych liczb, małe 8-bitowe mnie nie obchodzą, małe to sobie można na piechotę wyznaczyć bez wzoru, ważniejsze jest to jak wzór się zachowuje dla liczb bliskich nieskończoności.
Jak to wygląda w praktyce dla średnich liczb (o numerach 16 bitowych)
257 liczba pierwsza to 1621 liczona ze wzoru to 1621.5948345
258 liczba pierwsza to 1627 liczona ze wzoru to 1629.0869823
259 liczba pierwsza to 1637 liczona ze wzoru to 1636.5835782
...
777 liczba pierwsza to 5903 liczona ze wzoru to 5903.5488504
...
2570 liczba pierwsza to 23029 liczona ze wzoru to 23025.622796
2571 liczba pierwsza to 23039 liczona ze wzoru to 23035.709760
2572 liczba pierwsza to 23041 liczona ze wzoru to 23045.797157
2573 liczba pierwsza to 23053 liczona ze wzoru to 23055.884985
...
60870 liczba pierwsza to 758617 liczona ze wzoru to 758616.08277
60871 liczba pierwsza to 758629 liczona ze wzoru to 758629.63644
60877 liczba pierwsza to 758711 liczona ze wzoru to 758710.95884
Skąd wziąłem ten wzór?
Jest takie oszacowanie na f(N) prawdziwe dla wszystkich N większych niż 6.
N*(ln(N) + ln(ln(N)) - 1) < f(N) < N*(ln(N) + ln(ln(N)) - 0)
To nie ja wymyśliłem, ja tylko dodałem „- 0” aby było lepiej widać, że po obu stronach jest prawie to samo, różnią się tylko tą jedną stałą.
Te nierówności podobno zostały udowodnione, choć dowodu nigdzie w internecie nie znalazłem (no ale zakładam, że dowód istnieje skoro poważni matematycy twierdzą, że go widzieli w papierowej wersji, prawdopodobnym autorem tego dowodu jest Pierre Dusart jakby ktoś chciał poszukać dowodu może będzie miał więcej szczęścia).
Skoro tak to musi istnieć jakaś stała L z przedziału (0,1) taka, że:
f(N) = N*(ln(N) + ln(ln(N)) - L)
Pozostaje tylko wyznaczyć liczbę L.
W pierwszej chwili myślałem że to będzie proste, wziąłem 20 milionów znanych mi liczb pierwszych (znaczy najpierw komputer mi je policzył tradycyjną metodą) i potem za pomocą bi-sekcji dobrałem taką stała aby dla tych liczb funkcja dawała dobry wynik, wyszło L=0,95487476
Fajnie że w jednej liczbie dało się zapisać 20 milionów innych liczb...
...ale rozumowanie w ten sposób nie do końca dało taki wynik o jaki mi chodziło, bardziej zależało mi na tym aby funkcja dawała dobry wynik dla bardzo dużych liczb, a przecież te wszystkie znane liczby pierwsze są małe w porównaniu z nieskończonością. Oszacowanie co się dzieje gdy N dąży do nieskończoności jest już znacznie trudniejsze, zwiększając N wykładniczo patrzyłem gdzie dąży różnica (błąd) między faktyczną liczbą pierwszą o takim numerze i liczbą pierwszą policzoną ze wzoru, wyszło mi że aby błąd w nieskończoności dążył do zera to L powinno być odrobinę mniejsze, coś w okolicy 0,953...
#matematyka
f(N) ≈ N*(ln(N) + ln(ln(N)) - 0,953)
Ponieważ wynik jest liczbą rzeczywistą to należy ją zaokrąglić do najbliższej liczby nieparzystej.
(np 4.1 zaokrąglamy do 5 a 7,9 zaokrąglamy do 7)
Jest spora szansa że trafimy w ten sposób właśnie na N-tą liczbę pierwszą, a jeśli nawet nie trafi się dokładnie to różnica jest minimalna.
(błąd nie przekracza 0,1 ‰ dla dużych liczb, a 0,1 ‰ to tyle co nic).
Gdyby ktoś potrzebował dokładniej to można wyznaczyć dokładniej tą stałą która we wzorze występuje, jednak ponieważ logarytm jest funkcją gładką a liczby pierwsze występują schodkowo to osiągniemy tylko to, że funkcja będzie przez te schody przechodzić ale się z nimi nie pokryje.
Jak podjazd dla wózka który może być dowolnie blisko stopni, ale nie położy się na nich jak dywanik bo musi być gładki aby wózek podjechał.
Dla wielu zastosowań takie przybliżenie wystarczy, wiedząc na jakiej wysokości jest podjazd nawet po ciemku da się wymacać stopą schodek który jest obok podjazdu.
Wzór jest przewidziany dla dużych liczb, małe 8-bitowe mnie nie obchodzą, małe to sobie można na piechotę wyznaczyć bez wzoru, ważniejsze jest to jak wzór się zachowuje dla liczb bliskich nieskończoności.
Jak to wygląda w praktyce dla średnich liczb (o numerach 16 bitowych)
257 liczba pierwsza to 1621 liczona ze wzoru to 1621.5948345
258 liczba pierwsza to 1627 liczona ze wzoru to 1629.0869823
259 liczba pierwsza to 1637 liczona ze wzoru to 1636.5835782
...
777 liczba pierwsza to 5903 liczona ze wzoru to 5903.5488504
...
2570 liczba pierwsza to 23029 liczona ze wzoru to 23025.622796
2571 liczba pierwsza to 23039 liczona ze wzoru to 23035.709760
2572 liczba pierwsza to 23041 liczona ze wzoru to 23045.797157
2573 liczba pierwsza to 23053 liczona ze wzoru to 23055.884985
...
60870 liczba pierwsza to 758617 liczona ze wzoru to 758616.08277
60871 liczba pierwsza to 758629 liczona ze wzoru to 758629.63644
60877 liczba pierwsza to 758711 liczona ze wzoru to 758710.95884
Skąd wziąłem ten wzór?
Jest takie oszacowanie na f(N) prawdziwe dla wszystkich N większych niż 6.
N*(ln(N) + ln(ln(N)) - 1) < f(N) < N*(ln(N) + ln(ln(N)) - 0)
To nie ja wymyśliłem, ja tylko dodałem „- 0” aby było lepiej widać, że po obu stronach jest prawie to samo, różnią się tylko tą jedną stałą.
Te nierówności podobno zostały udowodnione, choć dowodu nigdzie w internecie nie znalazłem (no ale zakładam, że dowód istnieje skoro poważni matematycy twierdzą, że go widzieli w papierowej wersji, prawdopodobnym autorem tego dowodu jest Pierre Dusart jakby ktoś chciał poszukać dowodu może będzie miał więcej szczęścia).
Skoro tak to musi istnieć jakaś stała L z przedziału (0,1) taka, że:
f(N) = N*(ln(N) + ln(ln(N)) - L)
Pozostaje tylko wyznaczyć liczbę L.
W pierwszej chwili myślałem że to będzie proste, wziąłem 20 milionów znanych mi liczb pierwszych (znaczy najpierw komputer mi je policzył tradycyjną metodą) i potem za pomocą bi-sekcji dobrałem taką stała aby dla tych liczb funkcja dawała dobry wynik, wyszło L=0,95487476
Fajnie że w jednej liczbie dało się zapisać 20 milionów innych liczb...
...ale rozumowanie w ten sposób nie do końca dało taki wynik o jaki mi chodziło, bardziej zależało mi na tym aby funkcja dawała dobry wynik dla bardzo dużych liczb, a przecież te wszystkie znane liczby pierwsze są małe w porównaniu z nieskończonością. Oszacowanie co się dzieje gdy N dąży do nieskończoności jest już znacznie trudniejsze, zwiększając N wykładniczo patrzyłem gdzie dąży różnica (błąd) między faktyczną liczbą pierwszą o takim numerze i liczbą pierwszą policzoną ze wzoru, wyszło mi że aby błąd w nieskończoności dążył do zera to L powinno być odrobinę mniejsze, coś w okolicy 0,953...
#matematyka
AMIGA
4
Mam nadzieję że to nie inspirowany AI obłęd umysłu 🥴
Dps
1
Czy ktoś już to wcześniej wymyślił? Bo mam wrażenie, podczas ostatnich 2 tyg, że na Lurku oprócz miłośników pejsów są najlepsi matematycy na świecie 😁
borubar
1
Czy ktoś to wymyślił wcześniej?
Jeśli tak to się nie chwalił. No i to musiało by być niedawno, oszacowanie z którego korzystałem przy tworzeniu tego wzoru powstało dopiero 15 lat temu.
Dps
1
borubar
3
Ponieważ w Hipotezie Riemanna też występują logarytmy to przy próbie jego udowodnienia powstała cała masa innych twierdzeń i szacowań wykorzystujących logarytmy.
Jedno z tych oszacowań (nierówności które podałem) wydało mi się szczególnie ciekawe, bo wskazuje ono konkretny wąski przedział w którym znajduje się dana liczba pierwsza. W dodatku górę i dół tego ograniczenia opisuje niemal takie samo równanie - różnią się one tylko stałą.
A skoro tak to musi istnieć trzecie, podobne równanie które będzie wskazywać najbardziej prawdopodobną wartość liczby pierwszej - tylko trzeba dobrać odpowiednią stałą.
Najpierw chciałem ją obliczyć dopasowując wartość funkcji do jakiś znanych liczb pierwszych, ale gdy potem sprawdzałem dla innych większych liczb pierwszych to wychodziły drobne różnice, dlatego zmieniłem podejście skupiłem się nie na tym co jest na początku tego wykresu tylko na miejscu do którego on dąży
http://pl.wikipedia.org/wiki/Twierdzenie_o_liczbach_pierwszych#/media/Plik:Prime_number_theorem_ratio_convergence.svg
To też jest tylko wyznaczone numerycznie (w przybliżeniu), no ale okazuje się że nawet taka przybliżona wartość bardzo dobrze działa. To taj jak przy liczeniu pola koła przybliżenie 3,14 w większości przypadków jest wystarczająco dobre.
Thanos
4
tak na marginesie, pisałem ostatnio na temat Symfonii Riemanna: nawet jeśli ten wzór nie zastąpi aktualnie używanych (mega skutecznych!) metod znajdywania liczb pierwszych, można go z powodzeniem użyć, aby stworzyć podejście hybrydowe! Czyli użyć go do ulepszenia ATK / MR — wzór nie zastąpi testów pierwszości, ale może je znacząco przyspieszyć przez:
- redukcję liczby kandydatów do testowania
- optymalizację parametrów testów
- inteligentne przewidywanie gdzie szukać
To jak GPS dla liczb pierwszych: nie jedzie za Ciebie, ale pokazuje najlepszą trasę!
Konto usunięteWpis został usunięty przez moderatora
borubar
2
Gorsze w tym sensie, że to tylko przybliżenie, faktyczna liczba pierwsza może minimalnie różnić.
Ten szybki wzór można stosować wszędzie tam gdzie nie potrzeba super precyzji.
Thanos
1