n-ta liczba pierwsza mniejsza od ...

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Bran
Użytkownik
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 ...

Post autor: Bran »

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}\)
janusz47
Użytkownik
Użytkownik
Posty: 7910
Rejestracja: 18 mar 2009, o 16:24
Płeć: Mężczyzna
Podziękował: 30 razy
Pomógł: 1670 razy

Re: n-ta liczba pierwsza mniejsza od ...

Post autor: janusz47 »

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.}\)
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: n-ta liczba pierwsza mniejsza od ...

Post autor: Janusz Tracz »

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).

Kod: Zaznacz cały

http://www.algorytm.edu.pl/algorytmy-maturalne/badanie-czy-liczba-pierwsza/10000-liczb-pierwszych-1.html
Bran
Użytkownik
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 ...

Post autor: Bran »

Janusz Tracz, a masz może pomysł na udowodnienia, że od pewnego miejsca zachodzi:
\(\displaystyle{ p_n > 10n}\)?
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: n-ta liczba pierwsza mniejsza od ...

Post autor: Janusz Tracz »

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
Janusz Tracz, a masz może pomysł na udowodnienia, że od pewnego miejsca zachodzi:
\(\displaystyle{ p_n > 10n}\)?
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:
\(\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}\)
Bran
Użytkownik
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 ...

Post autor: Bran »

\(\displaystyle{ \lim_{n \to \infty } \left( \ln\pi(n)+\ln\ln n-\ln n\right) =0}\)
Skąd mamy pewność, że taka granica istnieje?
Awatar użytkownika
MrCommando
Użytkownik
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 ...

Post autor: MrCommando »

Bran, funkcja logarytmiczna jest ciągła, więc na spokojnie możemy "wyłączać" granicę przed logarytm i na odwrót.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: n-ta liczba pierwsza mniejsza od ...

Post autor: Janusz Tracz »

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.
Brombal
Użytkownik
Użytkownik
Posty: 465
Rejestracja: 1 gru 2015, o 21:49
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 6 razy
Pomógł: 20 razy

Re: n-ta liczba pierwsza mniejsza od ...

Post autor: Brombal »

A może chodziło o coś takiego?
\(\displaystyle{ p_n < 10^n}\)
ODPOWIEDZ