n-ta liczba pierwsza mniejsza od ...
-
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
n-ta liczba pierwsza mniejsza od ...
Bez powoływania się na postulat Bertranda udowodnić, że dla każdego \(\displaystyle{ n}\) naturalnego, dodatniego zachodzi:
\(\displaystyle{ p_n < 10n}\)
Gdzie \(\displaystyle{ p_n}\), to \(\displaystyle{ n}\)-ta liczba pierwsza, czyli:
\(\displaystyle{ p_1 = 2, \; p_2 = 3, \; p_3 = 5, \; p_4 = 7, \dots}\)
\(\displaystyle{ p_n < 10n}\)
Gdzie \(\displaystyle{ p_n}\), to \(\displaystyle{ n}\)-ta liczba pierwsza, czyli:
\(\displaystyle{ p_1 = 2, \; p_2 = 3, \; p_3 = 5, \; p_4 = 7, \dots}\)
-
- Użytkownik
- Posty: 7922
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1672 razy
Re: n-ta liczba pierwsza mniejsza od ...
Jeśli nie powołujemy się na twierdzenie Bertranda, to możemy skorzystać z twierdzenia (którego dowód można znaleźć u Sierpińskiego i Steinhausa)
Dla każdej liczby rzeczywistej \(\displaystyle{ x>0}\) istnieje ciąg liczb pierwszych \(\displaystyle{ (p(n))}\) taki, że
\(\displaystyle{ \lim_{n\to \infty} \frac{p_{n}}{n} = x.}\)
Dla każdej liczby rzeczywistej \(\displaystyle{ x>0}\) istnieje ciąg liczb pierwszych \(\displaystyle{ (p(n))}\) taki, że
\(\displaystyle{ \lim_{n\to \infty} \frac{p_{n}}{n} = x.}\)
- Janusz Tracz
- Użytkownik
- Posty: 4085
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1398 razy
Re: n-ta liczba pierwsza mniejsza od ...
Twoja hipoteza nie jest prawdziwa. Zobacz na tabelę \(\displaystyle{ 10000}\) pierwszych liczb pierwszych. Indeks ostatniej to \(\displaystyle{ n=10000}\) a wartość to \(\displaystyle{ 104729}\). Widać więc, że coś jest nie tak \(\displaystyle{ 104729<10 \cdot 10000}\).
I nie będzie ok bo liczby pierwsze rosną szybciej niż dowolne liniowe oszacowanie. Innymi słowy nawet jak zmieniasz nierówność na \(\displaystyle{ p_n<10^{100}n}\) to i tak znajdzie się indeks od którego nie będzie spełniona. Jest prawdą nierówność przeciwna (od pewnego miejscaindeksu zwykle dużego).
I nie będzie ok bo liczby pierwsze rosną szybciej niż dowolne liniowe oszacowanie. Innymi słowy nawet jak zmieniasz nierówność na \(\displaystyle{ p_n<10^{100}n}\) to i tak znajdzie się indeks od którego nie będzie spełniona. Jest prawdą nierówność przeciwna (od pewnego miejscaindeksu zwykle dużego).
Kod: Zaznacz cały
http://www.algorytm.edu.pl/algorytmy-maturalne/badanie-czy-liczba-pierwsza/10000-liczb-pierwszych-1.html
- Janusz Tracz
- Użytkownik
- Posty: 4085
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1398 razy
Re: n-ta liczba pierwsza mniejsza od ...
Zobacz tu \(\displaystyle{ \rightarrow}\) klik choć są to dość mocne wyniki (w stosunku do tego co postulujesz i od razy dają Twoją tezę) to warto zerknąć z czystej ciekawości. Natomiast
\(\displaystyle{ \lim_{n \to \infty } \left( \ln\pi(n)+\ln\ln n-\ln n\right) =0}\)
\(\displaystyle{ \lim_{n \to \infty } \ln n\left( \frac{\ln\pi(n)}{\ln n} + \frac{\ln\ln n}{\ln n} -1\right) =0}\)
Widać stąd, że nawias musi dążyć do zera bo inaczej równość nie zachodziła by a zachodzi bo to wniosek z twierdzenia o liczbach pieszych, poza tym proste cieczenie z analizy matematycznej pokazuje, że \(\displaystyle{ \frac{\ln\ln n}{\ln n} \rightarrow 0}\) zatem \(\displaystyle{ \frac{\ln\pi(n)}{\ln n} \rightarrow 1}\). Skorzystajmy teraz z "definicji Heinego" i zamiast ciągu \(\displaystyle{ n}\) podstawmy \(\displaystyle{ p_n}\) wszak jest to rosnący podciąg liczb naturalnych więc podstawiając to do lematu mamy równość:
PS Teraz widać dlaczego Twoja hipoteza zepsuła się dopiero na tak dużym indeksie. Bo funkcja \(\displaystyle{ \ln n}\) jest wybitnie ślamazarna w rozbieganiu się do nieskończoności i potrzebowała aż \(\displaystyle{ 10000}\) enów na rozpęd. To tak półżartem pół serio... nie jest to formalny meteorytyczny argument.
PPS To samo rozumowanie pokazuje, że dla dowolnego ustalonego \(\displaystyle{ \epsilon>0}\) dla odpowiednio dużych \(\displaystyle{ n}\) spełniona jest nierówność \(\displaystyle{ p_n<n^{1+\epsilon}}\) bo \(\displaystyle{ \frac{\ln n}{n^{\epsilon}} \rightarrow 0}\)
Udowodnię coś mocniejszego. Dla dowolnej liczby \(\displaystyle{ a}\) zachodzi od pewnego miejsca \(\displaystyle{ p_n>an}\) (o \(\displaystyle{ a}\) myślimy jak o liczbie "dużej" bo jak widać dla \(\displaystyle{ a<10}\) w zwykłych tablicach już napotykamy na kontrprzykład). Więc najpierw lemat:Janusz Tracz, a masz może pomysł na udowodnienia, że od pewnego miejsca zachodzi:
\(\displaystyle{ p_n > 10n}\)?
\(\displaystyle{ \lim_{n \to \infty } \frac{\ln \pi \left( n\right) }{\ln n}=1}\)
\(\displaystyle{ \pi \left( n\right)}\) to standardowo liczba liczb pierwszych mniejszych równych od \(\displaystyle{ n}\). Wyjdźmy od twierdzenia o liczbach pieszych tj. \(\displaystyle{ \lim_{n \to \infty } \frac{\pi(n)}{ \frac{n}{\ln n} }=\lim_{n \to \infty } \frac{\ln n\pi(n)}{ n }=1}\)
(\(\displaystyle{ n}\) można zastąpić \(\displaystyle{ x}\) i traktować to jak granicę funkcji a nie ciągu to się przyda w dwóch miejscach potem zatem miej to z tyłu głowy) logarytmując stronami i przekształcając mamy: \(\displaystyle{ \lim_{n \to \infty } \left( \ln\pi(n)+\ln\ln n-\ln n\right) =0}\)
\(\displaystyle{ \lim_{n \to \infty } \ln n\left( \frac{\ln\pi(n)}{\ln n} + \frac{\ln\ln n}{\ln n} -1\right) =0}\)
Widać stąd, że nawias musi dążyć do zera bo inaczej równość nie zachodziła by a zachodzi bo to wniosek z twierdzenia o liczbach pieszych, poza tym proste cieczenie z analizy matematycznej pokazuje, że \(\displaystyle{ \frac{\ln\ln n}{\ln n} \rightarrow 0}\) zatem \(\displaystyle{ \frac{\ln\pi(n)}{\ln n} \rightarrow 1}\). Skorzystajmy teraz z "definicji Heinego" i zamiast ciągu \(\displaystyle{ n}\) podstawmy \(\displaystyle{ p_n}\) wszak jest to rosnący podciąg liczb naturalnych więc podstawiając to do lematu mamy równość:
\(\displaystyle{ \lim_{n \to \infty } \frac{\ln \pi \left( p_n\right) }{\ln p_n}=1}\)
Oczywiście skoro \(\displaystyle{ \pi\left( n\right)}\) to liczba liczb pierwszych do \(\displaystyle{ n}\) a \(\displaystyle{ p_n}\) to \(\displaystyle{ n}\) ta liczba pierwsza to \(\displaystyle{ \pi (p_n)=n}\) więc:\(\displaystyle{ \lim_{n \to \infty } \frac{\ln n }{\ln p_n}=1}\)
teraz przekształćmy to do postaci równoważnej: \(\displaystyle{ \lim_{n \to \infty } \frac{\ln n \cdot {\red {p_n}}}{{\red{\ln p_n \cdot \pi \left( p_n\right)}} } \cdot \frac{\pi \left( p_n\right) }{p_n} =1}\)
czerwony kawałek dąży do \(\displaystyle{ 1}\) wszak znowu z twierdzenia o liczbach pieszych mamy \(\displaystyle{ \lim_{x \to \infty } \frac{\pi(x)}{ \frac{x}{\ln x} }=1}\) w roli szczególnego ciągu \(\displaystyle{ x=p_n}\) i po raz kolejny zauważamy, że \(\displaystyle{ \pi (p_n)=n}\) czyli ostatecznie: \(\displaystyle{ \lim_{n \to \infty } \frac{n\ln n}{p_n}=1}\)
więc dla dużych \(\displaystyle{ n}\) zachodzi \(\displaystyle{ p_n \approx n\ln n}\) co oznaczą, że \(\displaystyle{ \frac{p_n}{n} \approx \ln n}\) czyli: \(\displaystyle{ \lim_{n \to \infty }\frac{p_n}{n}=\lim_{n \to \infty } \ln n= \infty}\)
A to oznacza, że dla dowolnego \(\displaystyle{ a}\) istnieje takie \(\displaystyle{ N}\) po którym dla \(\displaystyle{ n>N}\) zachodzi \(\displaystyle{ \frac{p_n}{n}>a}\)
czyli właśnie \(\displaystyle{ p_n>an}\) zostaje spełnione ze względy na tą granicę. Co kończy dowód.PS Teraz widać dlaczego Twoja hipoteza zepsuła się dopiero na tak dużym indeksie. Bo funkcja \(\displaystyle{ \ln n}\) jest wybitnie ślamazarna w rozbieganiu się do nieskończoności i potrzebowała aż \(\displaystyle{ 10000}\) enów na rozpęd. To tak półżartem pół serio... nie jest to formalny meteorytyczny argument.
PPS To samo rozumowanie pokazuje, że dla dowolnego ustalonego \(\displaystyle{ \epsilon>0}\) dla odpowiednio dużych \(\displaystyle{ n}\) spełniona jest nierówność \(\displaystyle{ p_n<n^{1+\epsilon}}\) bo \(\displaystyle{ \frac{\ln n}{n^{\epsilon}} \rightarrow 0}\)
-
- Użytkownik
- Posty: 421
- Rejestracja: 19 lut 2019, o 19:30
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 163 razy
- Pomógł: 16 razy
Re: n-ta liczba pierwsza mniejsza od ...
Skąd mamy pewność, że taka granica istnieje?\(\displaystyle{ \lim_{n \to \infty } \left( \ln\pi(n)+\ln\ln n-\ln n\right) =0}\)
- MrCommando
- Użytkownik
- Posty: 554
- Rejestracja: 5 gru 2016, o 21:55
- Płeć: Mężczyzna
- Lokalizacja: Płock/MiNI PW
- Podziękował: 48 razy
- Pomógł: 107 razy
Re: n-ta liczba pierwsza mniejsza od ...
Bran, funkcja logarytmiczna jest ciągła, więc na spokojnie możemy "wyłączać" granicę przed logarytm i na odwrót.
- Janusz Tracz
- Użytkownik
- Posty: 4085
- Rejestracja: 13 sie 2016, o 15:01
- Płeć: Mężczyzna
- Lokalizacja: hrubielowo
- Podziękował: 80 razy
- Pomógł: 1398 razy
Re: n-ta liczba pierwsza mniejsza od ...
Z ciągłości logarytmu w \(\displaystyle{ x=1}\). Mamy zatem
\(\displaystyle{ \lim_{x \to 1}\ln x=\ln \left( \lim_{ x\to1 } x\right)= 0}\)
Wiec jak się za \(\displaystyle{ x}\) w szczególność podstawi ciąg \(\displaystyle{ \frac{\pi(n)}{ \frac{n}{\ln n} }}\) do dostaniesz co trzeba.
\(\displaystyle{ \lim_{x \to 1}\ln x=\ln \left( \lim_{ x\to1 } x\right)= 0}\)
Wiec jak się za \(\displaystyle{ x}\) w szczególność podstawi ciąg \(\displaystyle{ \frac{\pi(n)}{ \frac{n}{\ln n} }}\) do dostaniesz co trzeba.