|
|
| Linia 1: |
Linia 1: |
| − | <div style="text-align:right; font-size: 130%; font-style: italic; font-weight: bold;">07.11.2021</div>
| |
| | | | |
| − | __FORCETOC__
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Oznaczenia ==
| |
| − |
| |
| − | Będziemy stosowali następujące oznaczenia:
| |
| − |
| |
| − | ::<math>\mathbb{Z}</math> — zbiór liczb całkowitych<br/>
| |
| − | ::<math>\mathbb{Z}_+</math> — zbiór liczb całkowitych dodatnich<br/>
| |
| − | ::<math>\mathbb{N}</math> — zbiór liczb naturalnych <math>\mathbb{N} = \mathbb{Z}_{+}\cup \left \{ 0 \right \}</math><br/>
| |
| − | ::<math>\mathbb{R}</math> — zbiór liczb rzeczywistych<br/>
| |
| − | ::<math>d \mid n</math> — czytaj: d dzieli n (<math>d</math> jest dzielnikiem liczby <math>n</math>)<br/>
| |
| − | ::<math>d \nmid n</math> — czytaj: d nie dzieli n (<math>d</math> nie jest dzielnikiem liczby <math>n</math>)<br/>
| |
| − | ::<math>p_n</math> — <math>n</math>-ta liczba pierwsza<br/>
| |
| − | ::<math>\pi (n)</math> — ilość liczb pierwszych nie większych od <math>n</math><br/>
| |
| − | ::<math>P(n)</math> — iloczyn liczb pierwszych nie większych od <math>n</math><br/>
| |
| − | ::<math>\lfloor x \rfloor</math> — największa liczba całkowita nie większa od <math>x</math><br/>
| |
| − | ::<math>\binom{n}{m}</math> — współczynnik dwumianowy (symbol Newtona), <math>\binom{n}{m} = \frac{n!}{m! \cdot (n - m) !}</math><br/>
| |
| − | ::<math>\log (x)</math> — logarytm naturalny liczby <math>x > 0</math>
| |
| − | ::<math>W_p (n)</math> — wykładnik z jakim liczba pierwsza <math>p</math> wchodzi do rozwinięcia na czynniki pierwsze liczby <math>n</math>
| |
| − | ::<math>n</math> — oznacza zawsze liczbę naturalną
| |
| − | ::<math>p</math> — oznacza zawsze liczbę pierwszą
| |
| − |
| |
| − |
| |
| − |
| |
| − | Przykładowe wartości niektórych wypisanych wyżej funkcji:
| |
| − |
| |
| − | ::<math>p_2 = 3</math>, <math>p_{10} = 29</math>, <math>p_{100} = 541</math><br/>
| |
| − | ::<math>\pi (10) = 4</math>, <math>\pi (100) = 25</math>, <math>\pi (541) = 100</math><br/>
| |
| − | ::<math>P(5) = 30</math>, <math>P(10) = 210</math>, <math>P(50) = 614889782588491410</math><br/>
| |
| − | ::<math>\lfloor 1.2 \rfloor = 1</math>, <math>\lfloor 2.8 \rfloor = 2</math>, <math>\lfloor - 1.5 \rfloor = - 2</math><br/>
| |
| − | ::<math>\binom{5}{2} = 10</math>, <math>\binom{10}{5} = 252</math>, <math>\binom{9}{3} = 84</math><br/>
| |
| − | ::<math>W_2 (8) = 3</math>, <math>W_3 (18) = 2</math>, <math>W_7 (28) = 1</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − | Funkcje te są zaimplementowane w PARI/GP<ref name="PARIGP"/>
| |
| − |
| |
| − | ::<math>p_n</math> = prime(n)<br/>
| |
| − | ::<math>\pi (n)</math> = primepi(n)<br/>
| |
| − | ::<math>P(n)</math> = prodeuler(p=2, n, p)<br/>
| |
| − | ::<math>\lfloor x \rfloor</math> = floor(x)<br/>
| |
| − | ::<math>\binom{n}{m}</math> = binomial(n, m)<br/>
| |
| − | ::<math>W_p (n)</math> = valuation(n, p)
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Twierdzenie Czebyszewa ==
| |
| − |
| |
| − | W 1852 roku rosyjski matematyk Czebyszew<ref name="Czebyszew1"/><ref name="Czebyszew2"/> udowodnił, że dla funkcji <math>\pi (n)</math> prawdziwe jest następujące oszacowanie
| |
| − |
| |
| − |
| |
| − | ::<math>a \cdot \frac{n}{\log n} \underset{n \geqslant 11}{<} \pi (n) \underset{n \geqslant 96098}{<} b \cdot \frac{n}{\log n}</math>
| |
| − |
| |
| − |
| |
| − | gdzie <math>a = \log (2^{1 / 2} \cdot 3^{1 / 3} \cdot 5^{1 / 5} \cdot 30^{- 1 / 30}) = 0.921292022</math> oraz <math>b = \tfrac{6}{5} a = 1.105550428</math>
| |
| − |
| |
| − |
| |
| − | Dziwnym zrządzeniem losu rezultat ten określany jest jako nierówności Czebyszewa (których nie należy mylić z nierównościami udowodnionymi przez Czebyszewa w teorii prawdopodobieństwa), a twierdzeniem Czebyszewa nazywany jest łatwy wniosek z tych nierówności. Stąd tytuł tego artykułu: „Twierdzenie Czebyszewa o funkcji <math>\pi (n)</math>”
| |
| − |
| |
| − | Twierdzenie Czebyszewa o funkcji <math>\pi (n)</math> nabrało nowego życia, gdy w 1936 Erdos<ref name="Erdos"/> zelementaryzował jego dowód. Elementarny dowód daje mniej dokładne oszacowania, ale pozwala zapoznać się z tym pięknym twierdzeniem nawet uczniom szkoły podstawowej.
| |
| − |
| |
| − |
| |
| − | Czytelnik powinien mieć świadomość, że rezultat ten ma już jedynie znaczenie historyczne – dzisiaj dysponujemy znacznie lepszymi oszacowaniami<ref name="Dusart99"/><ref name="Dusart06"/><ref name="Dusart10"/><ref name="Dusart18"/> funkcji <math>\pi (n)</math> oraz <math>p_n</math>
| |
| − |
| |
| − |
| |
| − | ::<math>\frac{n}{\log n} \left( 1 + \frac{1}{\log n} \right) \underset{n \geqslant 599}{<} \pi (n) \underset{n \geqslant 2}{<} \frac{n}{\log n} \left( 1 + \frac{1.28}{\log n} \right)</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − | ::<math>n (\log n + \log \log n - 1) \underset{n \geqslant 2}{<} p_n \underset{n \geqslant 6}{<} n (\log n + \log \log n)</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − | Przedstawimy tutaj elementarny dowód twierdzenia Czebyszewa o funkcji <math>\pi (n)</math> oraz analogiczne oszacowanie dla funkcji <math>p_n</math>.
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A1</span><br/>
| |
| − | Prawdziwe są następujące oszacowania:
| |
| − |
| |
| − |
| |
| − | ::<math>0.72 \cdot n \log n \underset{n \geqslant 1}{<} p_n \underset{n \geqslant 3}{<} 2n \log n</math>
| |
| − |
| |
| − |
| |
| − | ::<math>\frac{2}{3} \cdot \frac{n}{\log n} \underset{n \geqslant 3}{<} \pi (n) \underset{n \geqslant 2}{<} \frac{2 n}{\log n}</math>
| |
| − |
| |
| − |
| |
| − | Dowód powyższego twierdzenia jest łatwy, ale wymaga udowodnienia kolejno wielu, przeważnie bardzo prostych, twierdzeń pomocniczych.
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Oszacowanie <math>p_n</math> od dołu i <math>\pi (n)</math> od góry ==
| |
| − |
| |
| − | Rozpoczniemy od oszacowania liczby <math>\binom{2n}{n}</math>. Badanie właściwości tego współczynnika dwumianowego jest kluczowe dla naszego dowodu.
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A2</span><br/>
| |
| − | Niech <math>n, k \in \mathbb{N}</math>. Współczynnik dwumianowy <math>\binom{n}{k}</math> jest zawsze liczbą całkowitą dodatnią.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Indukcja matematyczna. Ponieważ
| |
| − |
| |
| − | ::<math>\binom{0}{0} = \binom{1}{0} = \binom{1}{1} = 1</math>
| |
| − |
| |
| − | to twierdzenie jest prawdziwe dla <math>n = 1</math>. Zakładając prawdziwość twierdzenia dla wszystkich liczb całkowitych należących do przedziału <math>[1, n]</math> mamy dla <math>n + 1</math>
| |
| − |
| |
| − | ::<math>\binom{n + 1}{0} = \binom{n + 1}{n + 1} = 1</math>
| |
| − |
| |
| − | zaś dla <math>k</math> spełniającego warunek <math>1 \leqslant k \leqslant n</math>, jest
| |
| − |
| |
| − | ::<math>\binom{n + 1}{k} = \binom{n}{k} + \binom{n}{k - 1}</math>
| |
| − |
| |
| − | Na podstawie założenia indukcyjnego liczby po prawej stronie są liczbami całkowitymi dodatnimi, zatem <math>\binom{n + 1}{k}</math> dla wszystkich wartości <math>k</math> jest liczbą całkowitą dodatnią. Co należało pokazać.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A3</span><br/>
| |
| − | Niech <math>n \in \mathbb{Z}_+</math>. Współczynnik dwumianowy <math>\binom{2 n}{n}</math> jest liczbą parzystą.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Łatwo zauważamy, że
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = \frac{(2 n) !}{n! \cdot n!} = \frac{2 n \cdot (2 n - 1)!}{n \cdot (n - 1) ! \cdot n!} = 2 \cdot \binom{2 n - 1}{n - 1}</math><br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A4</span><br/>
| |
| − | Prawdziwe są następujące oszacowania współczynnika dwumianowego <math>\binom{2 n}{n}</math>
| |
| − |
| |
| − | ::<math>3.8^{n + 1} \underset{n \geqslant 80}{<} \binom{2 n}{n} \underset{n \geqslant 5}{<} 4^{n - 1}</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Indukcja matematyczna. W przypadku lewej nierówności łatwo sprawdzamy, że <math>3.8^{81} < \binom{160}{80}</math>. Zakładając prawdziwość nierówności dla <math>n \geqslant 80</math>, otrzymujemy dla <math>n + 1</math>
| |
| − |
| |
| − | ::<math>\binom{2 (n + 1)}{n + 1} = \binom{2 n}{n} \cdot \frac{(2 n + 2) (2 n + 1)}{(n + 1) (n + 1)} > 3.8^{n + 1} \cdot 2 \cdot \left( 2 - \frac{1}{n + 1} \right) \geqslant 3.8^{n + 1} \cdot 2 \cdot \left( 2 - \frac{1}{80 + 1} \right) > 3.8^{n + 1} \cdot 3.9753 > 3.8^{n + 2}</math>
| |
| − |
| |
| − |
| |
| − | Prawa nierówność jest prawdziwa dla <math>n = 5</math>. Zakładając prawdziwość nierówności dla <math>n</math>, otrzymujemy dla <math>n + 1</math>:
| |
| − |
| |
| − | ::<math>\binom{2 (n + 1)}{n + 1} = \binom{2 n}{n} \cdot \frac{(2 n + 2) (2 n + 1)}{(n + 1) (n + 1)} < 4^{n -1} \cdot 2 \cdot \left( 2 - \frac{1}{n + 1} \right) < 4^n</math>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A5</span><br/>
| |
| − | Dla <math>n \geqslant 12</math> prawdziwe jest oszacowanie <math>p_n > 3 n</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Indukcja matematyczna. Dowód oprzemy na spostrzeżeniu, że wśród kolejnych sześciu liczb naturalnych <math>6 k, 6 k + 1, 6 k + 2, 6 k + 3, 6 k + 4, 6 k + 5</math>
| |
| − | jedynie dwie: <math>6 k + 1</math> i <math>6 k + 5</math> mogą być pierwsze. Wynika stąd, że <math>p_{n + 2} \geqslant p_n + 6</math> dla <math>n \geqslant 4</math>. Dowód indukcyjny przeprowadzimy, stosując krok równy <math>2</math>. Twierdzenie jest oczywiście prawdziwe dla <math>n = 12</math>, bowiem <math>p_{12} = 37 > 3 \cdot 12 = 36</math>, podobnie <math>p_{13} = 41 > 3 \cdot 13 = 39</math>. Zakładając prawdziwość twierdzenia dla wszystkich liczb naturalnych <math>k \in [12, n]</math>, otrzymujemy dla <math>n + 2</math>:
| |
| − |
| |
| − | ::<math>p_{n + 2} \geqslant p_n + 6 > 3 n + 6 = 3 \cdot (n + 2)</math>
| |
| − |
| |
| − | Uwaga: inaczej mówiąc, dowodzimy twierdzenie osobno dla <math>n</math> parzystych <math>(n \geqslant 12)</math> i osobno dla <math>n</math> nieparzystych <math>(n \geqslant 13)</math>.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A6</span><br/>
| |
| − | Ciąg <math>a_n = \left( 1 + \frac{1}{n} \right)^n</math> jest rosnący i ograniczony. Dla wyrazów ciągu <math>(a_n)</math> prawdziwe jest oszacowanie <math>2 \leqslant a_n < 3</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | W artykule, w którym pojęcie współczynnika dwumianowego odgrywa główną rolę, nie mogło zabraknąć dowodu odwołującego się do wzoru dwumianowego
| |
| − |
| |
| − | ::<math>\left ( x + y \right )^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{n-k}y^{k} = \binom{n}{0} x^{n} + \binom{n}{1}x^{n-1}y + \binom{n}{2}x^{n-2}y^{2} + \ldots + \binom{n}{n}y^{n}</math>
| |
| − |
| |
| − | gdzie <math>\binom{n}{k} = \frac{n!}{k! \cdot (n - k)!}</math>.
| |
| − |
| |
| − |
| |
| − |
| |
| − | Dowód opiera się na spostrzeżeniu, że <math>e = \sum_{k=0}^{\infty} \frac{1}{k!} = 2.718281828 \ldots</math>, a wykorzystanie wzoru dwumianowego pozwala przekształcić wyrażenie <math>\left( 1 + \frac{1}{n} \right)^n</math> do postaci sumy z wyraźnie wydzielonym czynnikiem <math>\frac{1}{k!}</math>. Stosując wzór dwumianowy, możemy zapisać <math>n</math>-ty wyraz ciągu <math>(a_n)</math> w postaci
| |
| − |
| |
| − | ::<math>a_n = \left( 1 + \frac{1}{n} \right)^n =</math>
| |
| − |
| |
| − | ::<math>\quad \; = \sum_{k=0}^{n} \binom{n}{k} \frac{1}{n^k} =</math>
| |
| − |
| |
| − | ::<math>\quad \; = 2 + \sum_{k=2}^{n} \frac{n!}{k! \cdot (n - k)!} \cdot \frac{1}{n^k} =</math>
| |
| − |
| |
| − | ::<math>\quad \; = 2 + \sum_{k=2}^{n} \frac{1}{k!} \cdot \frac{n \cdot (n - 1) \cdot \ldots \cdot (n - (k - 1))}{n^k} =</math>
| |
| − |
| |
| − | ::<math>\quad \; = 2 + \sum_{k=2}^{n} \frac{1}{k!} \cdot \left( 1 - \frac{1}{n} \right) \cdot \ldots \cdot \left( 1 - \frac{k - 1}{n} \right) </math>
| |
| − |
| |
| − |
| |
| − | Odpowiednio dla wyrazu <math>a_{n + 1}</math> mamy
| |
| − |
| |
| − | ::<math>a_{n + 1} = \left( 1 + \frac{1}{n + 1} \right)^{n + 1} =</math>
| |
| − |
| |
| − | ::<math>\qquad \: = 2 + \sum_{k=2}^{n + 1} \frac{1}{k!} \cdot \left( 1 - \frac{1}{n + 1} \right) \cdot \ldots \cdot \left( 1 - \frac{k - 1}{n + 1} \right) ></math>
| |
| − |
| |
| − | ::<math>\qquad \: > 2 + \sum_{k=2}^{n} \frac{1}{k!} \cdot \left( 1 - \frac{1}{n + 1} \right) \cdot \ldots \cdot \left( 1 - \frac{k - 1}{n + 1} \right) ></math>
| |
| − |
| |
| − | ::<math>\qquad \: > 2 + \sum_{k=2}^{n} \frac{1}{k!} \cdot \left( 1 - \frac{1}{n} \right) \cdot \ldots \cdot \left( 1 - \frac{k - 1}{n} \right) =</math>
| |
| − |
| |
| − | ::<math>\qquad \: = a_n</math>
| |
| − |
| |
| − | Ostatnia nierówność jest prawdziwa, bo dla dowolnej liczby <math>x \in \mathbb{R}_+</math> jest <math>1 - \frac{x}{n + 1} > 1 - \frac{x}{n}</math>
| |
| − |
| |
| − | Zatem ciąg <math>(a_n)</math> jest rosnący. Musimy jeszcze wykazać, że jest ograniczony od góry. Pokazaliśmy wyżej, że wyraz <math>a_n</math> może być zapisany w postaci
| |
| − |
| |
| − | ::<math>a_n = 2 + \sum_{k=2}^{n} \frac{1}{k!} \cdot \left( 1 - \frac{1}{n} \right) \cdot \ldots \cdot \left( 1 - \frac{k - 1}{n} \right) </math>
| |
| − |
| |
| − |
| |
| − | Ponieważ czynniki w nawiasach są dodatnie i mniejsze od jedności, to
| |
| − |
| |
| − | ::<math>a_n \leqslant 2 + \sum_{k=2}^{n} \frac{1}{k!} =</math>
| |
| − |
| |
| − | ::<math>\quad \; \leqslant 1 + 1 + \sum_{k=2}^{n} \frac{1}{2^{k-1}} =</math>
| |
| − |
| |
| − | ::<math>\quad \; = 1 + \left ( 1 + \frac{1}{2} + \frac{1}{2^2} + \ldots + \frac{1}{2^{n-1}}\right ) =</math>
| |
| − |
| |
| − | ::<math>\quad \; = 1 + \frac{1 - \left ( \frac{1}{2} \right )^{n}}{1 - \frac{1}{2}} =</math>
| |
| − |
| |
| − | ::<math>\quad \; = 1 + 2 - \frac{1}{2^{n-1}} < </math>
| |
| − |
| |
| − | ::<math>\quad \; < 3</math>
| |
| − |
| |
| − |
| |
| − | Druga nierówność (nieostra) jest prawdziwa, bo dla <math>k \geqslant 2</math> zachodzi oczywista nierówność <math>k! \geqslant 2^{k - 1}</math>. Do sumy ujętej w nawiasy zastosowaliśmy wzór na sumę częściową szeregu geometrycznego.
| |
| − |
| |
| − | Ponieważ <math>a_1 = 2</math>, to prawdziwe jest oszacowanie <math>2 \leqslant a_n < 3</math>. Zauważmy jeszcze (już bez dowodu), że ciąg <math>(a_n)</math>, jako rosnący i ograniczony od góry<ref name="p1"/>, jest zbieżny. Granicą ciągu <math>(a_n)</math> jest liczba niewymierna <math>e = 2.718281828 \ldots</math>, która jest podstawą logarytmu naturalnego.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A7</span><br/>
| |
| − | Prawdziwe są następujące oszacowania:
| |
| − |
| |
| − | ::<math>n^n \underset{n \geqslant 13}{<} p_1 p_2 \cdot \ldots \cdot p_n \underset{n \geqslant 3}{<} (n \log n)^n</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Indukcja matematyczna. Udowodnimy tylko oszacowanie od dołu. Dowód oszacowania od góry przedstawimy po zakończeniu dowodu twierdzenia A1. Łatwo sprawdzamy, że twierdzenie jest prawdziwe dla <math>n = 13</math>. Zakładając prawdziwość twierdzenia dla liczb naturalnych <math>k \in [13, n]</math> mamy dla <math>n + 1</math>:
| |
| − |
| |
| − | ::<math>p_1 p_2 \cdot \ldots \cdot p_n p_{n + 1} > n^n \cdot p_{n + 1} > n^n \cdot 3 (n + 1) > n^n \cdot \left( 1 + \frac{1}{n} \right)^n \cdot (n + 1) = (n + 1)^{n + 1}</math>
| |
| − |
| |
| − | Gdzie skorzystaliśmy z faktu, że <math>p_n > 3 n</math> dla <math>n \geqslant 12</math> oraz z właściwości rosnącego ciągu <math>a_n = \left( 1 + \frac{1}{n} \right)^n < e =
| |
| − | 2.718281828 \ldots < 3</math> (zobacz twierdzenie A6).<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A8</span><br/>
| |
| − | Dla <math>n \geqslant 2</math> prawdziwe jest oszacowanie <math>\frac{P (2 n)}{P (n)} < 4^{n - 1}</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Rozważmy współczynnik dwumianowy
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = \frac{(2 n) !}{n! \cdot n!} = \frac{2 n \cdot (2 n - 1) \cdot \ldots \cdot (n + 1)}{n!}</math>
| |
| − |
| |
| − | Każda liczba pierwsza należąca do przedziału <math>[n + 1, 2 n]</math> występuje w liczniku wypisanego wyżej ułamka i nie występuje w mianowniku. Wynika stąd oszacowanie
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = C \cdot \underset{n + 1 \leqslant p_k \leqslant 2 n}{\prod p_k} > \underset{n + 1 \leqslant p_k \leqslant 2 n}{\prod p_k} = \frac{P (2 n)}{P (n)}</math>
| |
| − |
| |
| − | Zauważmy, że wypisany w powyższej nierówności iloczyn liczb pierwszych jest liczbą nieparzystą. Ponieważ współczynnik dwumianowy <math>\binom{2 n}{n}</math> jest dodatnią liczbą całkowitą parzystą, zatem również czynnik <math>C \geqslant 2</math> musi być dodatnią liczbą całkowitą parzystą. Łącząc uzyskaną nierówność z oszacowaniem z twierdzenia A4, otrzymujemy natychmiast:
| |
| − |
| |
| − | ::<math>\frac{P (2 n)}{P (n)} < \binom{2 n}{n} < 4^{n - 1}</math>
| |
| − |
| |
| − | Dla <math>n = 2, 3, 4</math> sprawdzamy uzyskany rezultat bezpośrednio.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A9</span><br/>
| |
| − | Dla <math>n \geqslant 1</math> prawdziwe jest oszacowanie <math>P(n) < 4^n</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Indukcja matematyczna. Oszacowanie <math>P(n) < 4^n</math> jest prawdziwe dla <math>n = 1, 2</math>. Zakładając prawdziwość oszacowania dla wszystkich liczb całkowitych nie większych od <math>n</math>, dla <math>n + 1</math> rozpatrzymy dwa przypadki. Jeżeli <math>n + 1 = 2 k + 1</math> jest liczbą nieparzystą większą lub równą <math>3</math>, to mamy
| |
| − |
| |
| − | ::<math>P(n + 1) = P (2 k + 1) = P (2 k + 2) = P (k + 1) \cdot \frac{P (2 k + 2)}{P (k + 1)} < 4^{k + 1} \cdot 4^k = 4^{2 k + 1} = 4^{n + 1}</math>
| |
| − |
| |
| − | gdzie skorzystaliśmy z założenia indukcyjnego i oszacowania z twierdzenia A8.
| |
| − |
| |
| − | Jeżeli <math>n + 1 = 2 k</math> jest liczbą parzystą większą lub równą <math>4</math>, to mamy
| |
| − |
| |
| − | ::<math>P(n + 1) = P (2 k) = P (k) \cdot \frac{P (2 k)}{P (k)} < 4^k \cdot 4^{k - 1} = 4^{2 k - 1} < 4^{2 k} = 4^{n + 1}</math>
| |
| − |
| |
| − | gdzie ponownie skorzystaliśmy z założenia indukcyjnego i oszacowania z twierdzenia A8.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A10</span><br/>
| |
| − | Dla <math>n \geqslant 1</math> prawdziwe jest oszacowanie <math>p_n > \frac{1}{2 \log 2} \cdot n \log n</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Ponieważ z definicji <math>P(p_n) = p_1 p_2 \cdot \ldots \cdot p_n</math>, to korzystając z oszacowań uzyskanych w twierdzeniach A5 i A8 dostajemy dla <math>n \geqslant 13</math>
| |
| − |
| |
| − | ::<math>n^n < p_1 p_2 \cdot \ldots \cdot p_n = P (p_n) < 4^{p_n}</math>
| |
| − |
| |
| − | Logarytmując obie strony nierówności, mamy
| |
| − |
| |
| − | ::<math>n \log n < p_n \cdot \log 4</math>
| |
| − |
| |
| − | Skąd natychmiast wynika dowodzone oszacowanie
| |
| − |
| |
| − | ::<math>p_n > \frac{1}{2 \log 2} \cdot n \log n > 0.72 \cdot n \log n</math>
| |
| − |
| |
| − | Prawdziwość powyższej nierówności dla <math>n \leqslant 12</math> sprawdzamy bezpośrednio.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A11</span><br/>
| |
| − | Dla <math>n \geqslant 2</math> prawdziwe jest oszacowanie <math>\pi (2 n) - \pi (n) < 2 \log 2 \cdot \frac{n}{\log n}</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Każda liczba pierwsza należąca do przedziału <math>[n + 1, 2 n]</math> jest dzielnikiem współczynnika dwumianowego
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = \frac{(2 n) !}{n! \cdot n!} = \frac{2 n \cdot (2 n - 1) \cdot \ldots \cdot (n + 1)}{n!}</math>
| |
| − |
| |
| − | bowiem dzieli licznik i nie dzieli mianownika. Ponieważ dla każdej z tych liczb jest <math>p > n</math>, to
| |
| − |
| |
| − | ::<math>n^{\pi (2 n) - \pi (n)} < \prod_{n < p_i \leqslant 2 n} p_i < \binom{2 n}{n} < 4^n</math>
| |
| − |
| |
| − | Ostatnia nierówność wynika z twierdzenia A4. Logarytmując, dostajemy
| |
| − |
| |
| − | ::<math>[\pi (2 n) - \pi (n)] \cdot \log n < 2 n \cdot \log 2</math>
| |
| − |
| |
| − | Czyli
| |
| − |
| |
| − | ::<math>\pi (2 n) - \pi (n) < 2 \log 2 \cdot \frac{n}{\log n}</math>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A12</span><br/>
| |
| − | Dla <math>n \geqslant 2</math> prawdziwe jest oszacowanie <math>\pi (n) < 2 \cdot \frac{n}{\log n}</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Indukcja matematyczna. Oszacowanie <math>\pi (n) < 2 \cdot \frac{n}{\log n}</math> jest prawdziwe dla <math>2 \leqslant n \leqslant 62</math>, co łatwo sprawdzamy przez bezpośrednie wyliczenie. W programie GP/PARI wystarczy wpisać polecenie:
| |
| − |
| |
| − | ::for(n=2, 62, if( primepi(n) >= 2 * n/log(n), print(n) ))
| |
| − |
| |
| − | Zakładając prawdziwość wzoru dla wszystkich liczb naturalnych należących do przedziału <math>[2, n]</math>, otrzymujemy dla <math>n + 1</math>
| |
| − |
| |
| − | a) jeżeli <math>n + 1</math> jest liczbą parzystą, to:
| |
| − |
| |
| − | ::<math>\pi (n + 1) = \pi (n) = 2 \cdot \frac{n}{\log n} < 2 \cdot \frac{n + 1}{\log (n + 1)}</math>
| |
| − |
| |
| − | ostania nierówność wynika ze spostrzeżenia, że funkcja <math>\frac{x}{\log x}</math> jest funkcją rosnącą dla <math>x > e \approx 2.71828</math>. Można też wykorzystać oszacowanie <math>\log(1 + x) < x</math> prawdziwe dla <math>x > 0</math>.
| |
| − |
| |
| − | b) jeżeli <math>n + 1</math> jest liczbą nieparzystą, to możemy położyć <math>n + 1 = 2 k + 1</math> i otrzymujemy:
| |
| − |
| |
| − | ::<math>\pi (n + 1) = \pi (2 k + 1) =</math>
| |
| − |
| |
| − | ::::<math>\quad = \pi (2 k + 2) =</math>
| |
| − |
| |
| − | ::::<math>\quad = \pi (k + 1) + [\pi (2 k + 2) - \pi (k + 1)] <</math>
| |
| − |
| |
| − | ::::<math>\quad < 2 \cdot \frac{k + 1}{\log (k + 1)} + 2 \log 2 \cdot \frac{k + 1}{\log (k + 1)} =</math>
| |
| − |
| |
| − | ::::<math>\quad = (1 + \log 2) \cdot \frac{2 k + 2}{\log (k + 1)} <</math>
| |
| − |
| |
| − | ::::<math>\quad < \left[ 1.7 \cdot \frac{2 k + 2}{\log (k + 1)} \cdot \frac{\log (2 k + 1)}{2 k + 1} \right] \cdot \frac{2 k + 1}{\log (2 k + 1)} <</math>
| |
| − |
| |
| − | ::::<math>\quad < \left[ 1.7 \cdot \frac{2 k + 2}{2 k + 1} \cdot \frac{\log (2 k + 2)}{\log (k + 1)} \right] \cdot \frac{2 k + 1}{\log (2 k + 1)} <</math>
| |
| − |
| |
| − | ::::<math>\quad = \left[ 1.7 \cdot \left( 1 + \frac{1}{2 k + 1} \right) \cdot \frac{\log (k + 1) + \log 2}{\log (k + 1)} \right] \cdot \frac{2 k + 1}{\log (2 k + 1)} =</math>
| |
| − |
| |
| − | ::::<math>\quad = \left[ 1.7 \cdot \left( 1 + \frac{1}{2 k + 1} \right) \cdot \left( 1 + \frac{\log 2}{\log (k + 1)} \right) \right] \cdot \frac{2 k + 1}{\log (2 k + 1)} <</math>
| |
| − |
| |
| − | ::::<math>\quad < 2 \cdot \frac{2 k + 1}{\log (2 k + 1)} =</math>
| |
| − |
| |
| − | ::::<math>\quad = 2 \cdot \frac{n + 1}{\log (n + 1)}</math>
| |
| − |
| |
| − | Ostatnia nierówność wynika z faktu, że czynnik w nawiasie kwadratowym maleje wraz ze wzrostem <math>k</math> i dla <math>k = 63</math> osiąga wartość <math>1.9989 \ldots</math><br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Wykładnik z jakim liczba pierwsza <math>p</math> występuje w <math>n!</math> ==
| |
| − |
| |
| − | Uzyskanie kolejnych oszacowań wymaga znalezienia wykładnika, z jakim liczba pierwsza <math>p</math> wchodzi do rozwinięcia współczynnika dwumianowego <math>\binom{2 n}{n} = \frac{(2 n) !}{(n!)^2}</math>.
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Definicja A13</span><br/>
| |
| − | Funkcję <math>\lfloor x \rfloor</math> (czytaj: całość z <math>x</math>) definiujemy jako największą liczbę całkowitą nie większą od <math>x</math>. Operacyjnie możemy ją zdefiniować następująco: niech liczby <math>x, \varepsilon \in \mathbb{R}</math>, liczba <math>k \in \mathbb{Z}</math> oraz <math>0 \leqslant \varepsilon < 1</math>, jeżeli <math>x = k + \varepsilon</math>, to <math>\lfloor x \rfloor = \lfloor k + \varepsilon \rfloor = k </math>.
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A14</span><br/>
| |
| − | Dla <math>n \in \mathbb{Z}_+</math>, <math>x \in \mathbb{R}</math> jest <math>\left \lfloor \frac{x}{n} \right\rfloor = \left \lfloor \frac{\left \lfloor x \right \rfloor}{n} \right \rfloor</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Korzystając z definicji A13, przedstawmy liczbę w postaci <math>x = k + \varepsilon</math>, gdzie <math>0 \leqslant \varepsilon < 1</math>.
| |
| − |
| |
| − | Z twierdzenia o dzieleniu z resztą liczbę <math>k</math> możemy zapisać w postaci <math>k = q n + r</math>, gdzie <math>0 \leqslant r \leqslant n - 1</math>, mamy zatem <math>x = q n + r + \varepsilon</math>. Ponieważ <math>0 \leqslant r + \varepsilon < n</math>, to po podzieleniu przez <math>n</math> dostajemy
| |
| − |
| |
| − | ::<math>0 \leqslant \frac{r + \varepsilon}{n} < 1</math>
| |
| − |
| |
| − | czyli
| |
| − |
| |
| − | ::<math>\left \lfloor \frac{x}{n} \right \rfloor = \left \lfloor \frac{qn + r + \varepsilon }{n} \right \rfloor = \left \lfloor q + \frac{r + \varepsilon }{n} \right \rfloor = q</math>
| |
| − |
| |
| − | Podobnie, ponieważ <math>0 \leqslant r < n</math>, to <math>0 \leqslant \frac{r}{n} < 1</math> i otrzymujemy
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{\left \lfloor x \right\rfloor}{n} \right\rfloor = \left \lfloor \frac{\left \lfloor qn + r + \varepsilon \right \rfloor}{n} \right \rfloor = \left \lfloor \frac{qn + r}{n} \right \rfloor = \left \lfloor q + \frac{r}{n} \right \rfloor = q</math>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A15</span><br/>
| |
| − | Niech <math>x \in \mathbb{R}</math>. Liczba <math>\lfloor 2 x \rfloor - 2 \lfloor x \rfloor</math> przyjmuje wartości <math>0</math> lub <math>1</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Niech <math>x = k + \varepsilon</math>, gdzie <math>0 \leqslant \varepsilon < 1</math>. Mamy
| |
| − |
| |
| − | ::<math> \lfloor 2 x \rfloor - 2 \lfloor x \rfloor = \lfloor 2 k + 2 \varepsilon \rfloor - 2 \lfloor k + \varepsilon \rfloor = 2 k + \lfloor 2 \varepsilon \rfloor - 2 k -2 \lfloor \varepsilon \rfloor = \lfloor 2 \varepsilon \rfloor</math>
| |
| − |
| |
| − | Ponieważ <math>0 \leqslant 2 \varepsilon < 2</math>, zatem <math>\lfloor 2 \varepsilon \rfloor = 0</math> lub <math>\lfloor 2 \varepsilon \rfloor = 1</math>.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | Bardzo istotnym rezultatem (z punktu widzenia przyszłych obliczeń) będzie znalezienie wykładnika, z jakim liczba pierwsza <math>p</math> występuje w iloczynie <math>1 \cdot 2 \cdot 3 \cdot \ldots \cdot n = n!</math>
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Definicja A16</span><br/>
| |
| − | Niech <math>p</math> będzie liczbą pierwszą, zaś <math>a</math> dowolną liczbą naturalną. Jeżeli liczba pierwsza <math>p</math> wchodzi do rozwinięcia liczby naturalnej <math>n \geqslant 2</math> na czynniki pierwsze z wykładnikiem <math>a</math>, to powiemy, że funkcja <math>W_p (n)</math> przyjmuje wartość <math>a</math>. Fakt ten możemy zapisać następująco
| |
| − |
| |
| − | ::<math>W_p (n) = a \qquad\qquad \iff \qquad\qquad p^{a} \mid n \qquad \text{i} \qquad p^{a + 1} \nmid n</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Przykład A17</span><br/>
| |
| − | <math>W_5 (100) = 2</math>, <math>W_7 (42) = 1</math>, ponieważ <math>11! = 2^8 \cdot 3^4 \cdot 5^2 \cdot 7 \cdot 11</math>, to <math>W_3 (11!) = 4</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − | Wprost z definicji funkcji <math>W_p (n)</math> wynikają następujące właściwości:
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A18</span><br/>
| |
| − |
| |
| − | Podstawowe własności funkcji <math>W_p (n)</math>
| |
| − |
| |
| − | ::# <math>\;\; W_p (n \cdot m) = W_p (n) + W_p (m)</math>
| |
| − | ::# <math>\;\; W_p (n \cdot p^a) = a + W_p (n)</math>
| |
| − | ::# <math>\;\; W_{p}\left ( \frac{n}{m} \right ) = W_{p}\left ( n \right ) - W_{p}\left ( m \right ) \quad \text{o ile} \quad \frac{n}{m}\in \mathbb{Z}_{+}</math>
| |
| − | ::# <math>\;\; p \nmid n \quad\quad \iff \quad\quad W_p (n) = 0</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A19</span><br/>
| |
| − | Niech <math>p</math> będzie liczbą pierwszą. Ilość liczb podzielnych przez <math>p</math> i występujących w ciągu <math>1, 2, 3, \ldots, n</math> wynosi <math>r = \left\lfloor \frac{n}{p} \right\rfloor</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Wśród liczb naturalnych <math>1, 2, 3, \ldots, n</math> istnieje pewna ilość liczb podzielnych przez <math>p</math>. Liczby te możemy z łatwością wypisać, będą nimi
| |
| − |
| |
| − | ::<math>1 \cdot p, 2 \cdot p, 3 \cdot p, \ldots, r \cdot p</math>
| |
| − |
| |
| − | Gdzie <math>r</math> jest największą liczbą całkowitą nie większą niż <math>\frac{n}{p}</math>, czyli <math>r = \left\lfloor \frac{n}{p} \right\rfloor</math>.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Przykład A20</span><br/>
| |
| − | Ilość liczb całkowitych dodatnich podzielnych przez <math>5</math> i nie większych od <math>63</math> wynosi <math>\left\lfloor \frac{63}{5} \right\rfloor = 12</math>. Liczby te to <math>5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60</math>.
| |
| − |
| |
| − |
| |
| − |
| |
| − | Twierdzenie A19 umożliwi nam określenie wykładnika, z jakim liczba pierwsza <math>p</math> występuje w <math>n!</math>
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A21</span><br/>
| |
| − | Liczba pierwsza <math>p</math> występuje w iloczynie <math>n!</math> z wykładnikiem <math>W_p (n!) = \sum_{k = 1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Dowód sprowadza się do znalezienia wartości funkcji <math>W_p (n!)</math>.
| |
| − |
| |
| − | ::<math>W_p (n!) = W_p (1 \cdot 2 \cdot 3 \cdot \ldots \cdot n) = W_p \left( p \cdot 2 p \cdot 3 p \cdot \ldots \cdot \left\lfloor \frac{n}{p} \right\rfloor \cdot p \right)</math>
| |
| − |
| |
| − | Pozostawiliśmy jedynie czynniki podzielne przez <math>p</math> (czynniki niepodzielne przez <math>p</math> nie dają wkładu do wykładnika, z jakim <math>p</math> występuje w <math>n!</math>), wyłączając czynnik <math>p</math> z każdej z liczb <math>p, 2 p, 3 p, \ldots, \left\lfloor \frac{n}{p} \right\rfloor \cdot p</math> mamy
| |
| − |
| |
| − | ::<math>W_p (n!) = W_p \left( p^{\lfloor n / p \rfloor} \cdot 1 \cdot 2 \cdot 3 \cdot \ldots \cdot \left\lfloor \frac{n}{p} \right\rfloor \right) = \left\lfloor \frac{n}{p} \right\rfloor + W_p \left( 1 \cdot 2 \cdot 3 \cdot \ldots \cdot \left\lfloor \frac{n}{p} \right\rfloor \right)</math>
| |
| − |
| |
| − | Otrzymane wyrażenie przekształcamy analogicznie jak wyżej
| |
| − |
| |
| − | ::<math>W_p (n!) = \left\lfloor \frac{n}{p} \right\rfloor + W_p \left( p \cdot 2 p \cdot 3 p \cdot \ldots \cdot \left\lfloor \frac{\lfloor n / p \rfloor}{p} \right\rfloor \cdot p \right)</math>
| |
| − |
| |
| − | Z twierdzenia A14 wiemy, że dla <math>x \in \mathbb{R}</math> i <math>n \in \mathbb{Z}_{+}</math> jest:
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{\lfloor x \rfloor}{n} \right\rfloor = \left \lfloor \frac{x}{n} \right \rfloor</math>
| |
| − |
| |
| − | zatem
| |
| − |
| |
| − | ::<math>W_p (n!) = \left\lfloor \frac{n}{p} \right\rfloor + W_p \left( p \cdot 2 p \cdot 3 p \cdot \ldots \cdot \left\lfloor \frac{n}{p^2} \right\rfloor \cdot p \right) =</math>
| |
| − |
| |
| − | ::::<math>\;\, = \left\lfloor \frac{n}{p} \right\rfloor + W_p \left( p^{\lfloor n / p^2 \rfloor} \cdot 1 \cdot 2 \cdot 3 \cdot \ldots \cdot \left\lfloor \frac{n}{p^2} \right\rfloor \right) =</math>
| |
| − |
| |
| − | ::::<math>\;\, = \left\lfloor \frac{n}{p} \right\rfloor + \left\lfloor \frac{n}{p^2} \right\rfloor + W_p \left( 1 \cdot 2 \cdot 3 \cdot \ldots \cdot \left\lfloor \frac{n}{p^2} \right\rfloor \right)</math>
| |
| − |
| |
| − | Oczywiście opisaną wyżej procedurę możemy powtarzać wielokrotnie. Zakończenie następuje wtedy, gdy wykładnik liczby pierwszej <math>p</math> osiągnie wartość tak dużą, że <math>\left\lfloor \frac{n}{p^k} \right\rfloor = 0</math>. Ponieważ nie wiemy, jaka to wartość (choć możemy ją oszacować), to stosujemy zapis
| |
| − |
| |
| − | ::<math>W_p (n!) = \sum_{k = 1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor</math>
| |
| − |
| |
| − | zdając sobie sprawę z tego, że w rzeczywistości sumowanie obejmuje jedynie skończoną liczbę składników.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Uwaga A22</span><br/>
| |
| − | Należy zauważyć, że liczba sumowań jest skończona, bowiem bardziej precyzyjnie możemy powyższy wzór zapisać w postaci
| |
| − |
| |
| − | ::<math>W_p (n!) = \sum_{k = 1}^B \left\lfloor \frac{n}{p^k} \right\rfloor</math>
| |
| − |
| |
| − | gdzie <math>B = \lfloor \log_2 (n) \rfloor</math>. Jest tak dlatego, że jeżeli <math>k</math> przekroczy <math>\lfloor \log_2 (n) \rfloor</math>, to dla liczby pierwszej <math>p = 2</math>, jak również dla wszystkich innych liczb pierwszych mamy
| |
| − |
| |
| − | ::<math>\frac{n}{p^k} < 1</math>
| |
| − |
| |
| − | czyli dla <math>k > B</math> sumujemy same zera.
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Przykład A23</span><br/>
| |
| − | Niech <math>n = 30</math>, <math>p = 3</math>
| |
| − |
| |
| − | ::<math>W_3 (30!) = W_3 (1 \cdot 2 \cdot 3 \cdot 4 \cdot \ldots \cdot 30) =</math>
| |
| − |
| |
| − | ::::<math>\quad = W_3 (3\cdot 6 \cdot 9 \cdot 12 \cdot 15 \cdot 18 \cdot 21 \cdot 24 \cdot 27 \cdot 30) =</math>
| |
| − |
| |
| − | ::::<math>\quad = W_3 (3^{10} \cdot 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10) =</math>
| |
| − |
| |
| − | ::::<math>\quad = 10 + W_3 (1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10) =</math>
| |
| − |
| |
| − | ::::<math>\quad = 10 + W_3 (3 \cdot 6 \cdot 9) =</math>
| |
| − |
| |
| − | ::::<math>\quad = 10 + W_3 (3^3 \cdot 1 \cdot 2 \cdot 3) =</math>
| |
| − |
| |
| − | ::::<math>\quad = 10 + 3 + W_3 (1 \cdot 2 \cdot 3) =</math>
| |
| − |
| |
| − | ::::<math>\quad = 10 + 3 + W_3 (3) =</math>
| |
| − |
| |
| − | ::::<math>\quad = 10 + 3 + 1 =</math>
| |
| − |
| |
| − | ::::<math>\quad = 14</math>
| |
| − |
| |
| − | Co jest zgodne ze wzorem:
| |
| − |
| |
| − | ::<math>W_3 (30!) = \left\lfloor \frac{30}{3} \right\rfloor + \left\lfloor \frac{30}{3^2} \right\rfloor + \left\lfloor \frac{30}{3^3} \right\rfloor = 10 + 3 + 1 = 14</math>
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | Podobnie jak w poprzednim podrozdziale będziemy badali współczynnik dwumianowy postaci <math>\binom{2 n}{n}</math>. Teraz już łatwo możemy policzyć wykładnik, z jakim liczba pierwsza <math>p</math> wchodzi do rozwinięcia na czynniki pierwsze tego współczynnika dwumianowego.
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A24</span><br/>
| |
| − | Liczba pierwsza <math>p</math> wchodzi do rozwinięcia na czynniki pierwsze liczby <math>\binom{2 n}{n}</math> z wykładnikiem
| |
| − |
| |
| − | ::<math>u = \sum^{\infty}_{k = 1} \left( \left \lfloor \frac{2n}{p^{k}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{k}} \right \rfloor \right)</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Ponieważ <math>\binom{2 n}{n} = \frac{(2 n) !}{(n!)^2}</math>, to liczba pierwsza <math>p</math> wchodzi do rozwinięcia na czynniki pierwsze liczby <math>\binom{2 n}{n}</math> z wykładnikiem:
| |
| − |
| |
| − | ::<math>W_p \left( \binom{2 n}{n} \right) = W_p ((2 n) !) - 2 W_p (n!) = \sum^{\infty}_{k = 1} \left \lfloor \frac{2n}{p^{k}} \right \rfloor - 2 \sum^{\infty}_{k = 1} \left \lfloor \frac{n}{p^{k}} \right \rfloor = \sum^{\infty}_{k = 1} \left( \left \lfloor \frac{2n}{p^{k}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{k}} \right \rfloor \right)</math>
| |
| − | <br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A25</span><br/>
| |
| − | Liczby pierwsze spełniające warunek <math>p > \sqrt{2 n}</math> występują w rozwinięciu liczby <math>\binom{2 n}{n}</math> na czynniki pierwsze z wykładnikiem <math>u = 1</math> lub <math>u = 0</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Jeżeli <math>p > \sqrt{2 n}</math>, to dla <math>k \geqslant 2</math> mamy <math>p^k \geqslant p^2 > 2 n > n</math>. Zatem dla <math>k \geqslant 2</math> jest <math>\left\lfloor \frac{2 n}{p^k} \right\rfloor = \left\lfloor \frac{n}{p^k} \right\rfloor = 0</math> i otrzymujemy
| |
| − |
| |
| − | ::<math>u = \sum^{\infty}_{k = 1} \left ( \left \lfloor \frac{2 n}{p^{k}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{k}} \right \rfloor \right ) = \left \lfloor \frac{2 n}{p} \right \rfloor - 2 \left \lfloor \frac{n}{p} \right \rfloor</math>
| |
| − |
| |
| − | Na mocy twierdzenia A15 (dla <math>x = \tfrac{n}{p}</math>), dostajemy natychmiast, że <math>u = 1</math> lub <math>u = 0</math>.
| |
| − | <br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A26</span><br/>
| |
| − | Niech <math>p</math> będzie liczbą pierwszą. Jeżeli <math>p^a \big\rvert \binom{2 n}{n}</math>, to <math>p^a \leqslant 2 n</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Niech <math>u</math> oznacza wykładnik, z jakim liczba pierwsza <math>p</math> wchodzi do rozwinięcia współczynnika dwumianowego <math>\binom{2 n}{n}</math> na czynniki pierwsze. Mamy
| |
| − |
| |
| − | ::<math>u = \sum_{k = 1}^{\infty} \left( \left\lfloor \frac{2 n}{p^k} \right\rfloor - 2 \left\lfloor \frac{n}{p^k} \right\rfloor \right)</math>
| |
| − |
| |
| − | gdzie sumowanie przebiega w rzeczywistości od <math>k = 1</math> do <math>k = s</math>, a wartość liczby <math>s</math> wynika z warunku <math>p^s \leqslant 2 n < p^{s + 1}</math>. Ponieważ sumowane wyrazy są równe <math>0</math> lub <math>1</math>, to otrzymujemy natychmiast oszacowanie <math>u \leqslant s</math>, skąd wynika następujący ciąg nierówności
| |
| − |
| |
| − | ::<math>p^a \leqslant p^u \leqslant p^s \leqslant 2 n</math>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Oszacowanie <math>p_n</math> od góry i <math>\pi (n)</math> od dołu ==
| |
| − |
| |
| − | Z twierdzenia A26 wynika natychmiast
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A27</span><br/>
| |
| − | Niech <math>\binom{2 n}{n} = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s</math> będzie rozkładem współczynnika dwumianowego na czynniki pierwsze. Dla każdej liczby pierwszej <math>q_i</math>, <math>i = 1, \ldots, s</math> prawdziwe jest oszacowanie <math>q^{\alpha_i}_i \leqslant 2 n</math>.
| |
| − |
| |
| − | Uwaga: w powyższym twierdzeniu <math>q_i</math> nie oznacza <math>i</math>-tej liczby pierwszej, a pewną liczbą pierwszą o indeksie <math>i</math> ze zboru liczb pierwszych <math>q_1, \ldots q_s</math>, które wchodzą do rozkładu współczynnika dwumianowego na czynniki pierwsze z wykładnikiem większym od zera.
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A28</span><br/>
| |
| − | Dla <math>n \geqslant 1</math> prawdziwe jest następujące oszacowanie współczynnika dwumianowego <math>\binom{2 n}{n}</math>
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} \leqslant (2 n)^{\pi (2 n)} < (2 n + 1)^{\pi (2 n + 1)}</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Dowód wynika natychmiast z twierdzenia A27, bowiem
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = q^{\alpha_1}_1 \cdot \ldots \cdot q^{\alpha_s}_s \leqslant (2 n)^s \leqslant (2 n)^{\pi (2 n)} < (2 n + 1)^{\pi (2 n + 1)}</math>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A29</span><br/>
| |
| − | Dla <math>n \geqslant 3</math> prawdziwe jest następujące oszacowanie
| |
| − |
| |
| − | ::<math>\pi (n) > \frac{2}{3} \cdot \frac{n}{\log n}</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | W twierdzeniu A4 oszacowaliśmy współczynnik dwumianowy <math>\binom{2 n}{n}</math>. Przepiszemy, to twierdzenie w postaci bardziej czytelnej dla potrzeb tego dowodu
| |
| − |
| |
| − | ::<math>\left( \sqrt{3.8} \right)^{2 n} < \left( \sqrt{3.8} \right)^{2 n + 1} < \left( \sqrt{3.8} \right)^{2 n + 2} = 3.8^{n + 1} < \binom{2 n}{n}</math>
| |
| − |
| |
| − | Nierówności te są prawdziwe dla <math>n \geqslant 80</math>. Z twierdzenia A28 mamy
| |
| − |
| |
| − | ::<math>\left( \sqrt{3.8} \right)^{2 n} < \left( \sqrt{3.8} \right)^{2 n + 1} < \binom{2 n}{n} \leqslant (2 n)^{\pi (2 n)} < (2 n + 1)^{\pi (2 n + 1)}</math>
| |
| − |
| |
| − | Łącząc odpowiednie oszacowania współczynnika dwumianowego <math>\binom{2 n}{n}</math> od góry z odpowiednimi oszacowaniami od dołu, dostajemy
| |
| − |
| |
| − | ::<math>(2 n + 1)^{\pi (2 n + 1)} > \left( \sqrt{3.8} \right)^{2 n + 1}</math>
| |
| − |
| |
| − | ::<math>(2 n)^{\pi (2 n)} > \left( \sqrt{3.8} \right)^{2 n}</math>
| |
| − |
| |
| − | Zatem zarówno dla parzystych, jak i nieparzystych liczb <math>m \geqslant 160</math> jest
| |
| − |
| |
| − | ::<math>m^{\pi (m)} > \left( \sqrt{3.8} \right)^m</math>
| |
| − |
| |
| − | ::<math>\pi (m) \cdot \log m > m \cdot \log \left( \sqrt{3.8} \right)</math>
| |
| − |
| |
| − | Czyli
| |
| − |
| |
| − | ::<math>\pi (m) > \frac{1}{2} \cdot \log \left ( 3.8 \right ) \cdot \frac{m}{\log m} > 0.6675 \cdot \frac{m}{\log m} > \frac{2}{3} \cdot \frac{m}{\log m}</math>
| |
| − |
| |
| − | Dla <math>m = 3, 4, \ldots, 159</math> prawdziwość nierówności sprawdzamy przez bezpośrednie wyliczenie. W programie GP/PARI wystarczy wykonać polecenie
| |
| − |
| |
| − | ::for( n=2, 200, if( primepi(n) <= 2/3*n/log(n), print(n) ))<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A30</span><br/>
| |
| − | Niech <math>n \geqslant 3</math>. Dla <math>n</math>-tej liczby pierwszej <math>p_n</math> prawdziwe jest oszacowanie <math>p_n < 2 n \log n</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Z twierdzenia A29 wiemy, że dla <math>n \geqslant 3</math> zachodzi <math>\pi (n) > \frac{2}{3} \cdot \frac{n}{\log n}</math>. Kładąc <math>n = p_s</math> otrzymujemy dla <math>s \geqslant 2</math>
| |
| − |
| |
| − | ::<math>s = \pi (p_s) > \frac{2}{3} \cdot \frac{p_s}{\log p_s}</math>
| |
| − |
| |
| − | Rozważmy funkcję
| |
| − |
| |
| − | ::<math>\frac{2}{3} \cdot \frac{x}{\log x} - x^{3 / 4} = \frac{2}{3} \cdot \frac{x^{3 / 4}}{\log x} \left( x^{1 / 4} - \frac{3}{2} \cdot \log x \right)</math>
| |
| − |
| |
| − | Zamieszczony niżej obrazek przedstawia wykres funkcji <math>x^{1 / 4} - \tfrac{3}{2} \cdot \log x</math>
| |
| − |
| |
| − | [[File: Czebyszew-wykres-1.png|center]]
| |
| − |
| |
| − | Wpisując w PARI/GP polecenie
| |
| − |
| |
| − | ::solve(x=10^4, 10^5, x^(1/4) - 3/2*log(x))
| |
| − |
| |
| − | łatwo sprawdzamy, że funkcja <math>x^{1 / 4} - \tfrac{3}{2} \cdot \log x</math> przecina oś <math>OX</math> w punkcie <math>x = 83499.136 \ldots</math> Wynika stąd, że dla <math>x > 83499.14</math> prawdziwe jest oszacowanie
| |
| − |
| |
| − | ::<math>\frac{2}{3} \cdot \frac{x}{\log x} > x^{3 / 4}</math>
| |
| − |
| |
| − | Zatem możemy napisać
| |
| − |
| |
| − | ::<math>s = \pi (p_s) > \frac{2}{3} \cdot \frac{p_s}{\log p_s} > (p_s)^{3 / 4}</math>
| |
| − |
| |
| − | Co oznacza, że dla <math>s \geqslant 8153</math> (bo <math>p_{8153} = 83537 > 83499.14</math>) mamy <math>p_s < s^{4 / 3}</math> i wpisując w PARI/GP polecenie
| |
| − |
| |
| − | ::for(n=1, 10^4, if( prime(n) >= n^(4/3), print(n) ))
| |
| − |
| |
| − | sprawdzamy, że otrzymane oszacowanie <math>p_s < s^{4 / 3}</math> jest prawdziwe dla <math>s \geqslant 255</math>. Wykorzystując ten rezultat i szacując po raz drugi dostajemy dla <math>s \geqslant 255</math>
| |
| − |
| |
| − | ::<math>p_s < \frac{3}{2} \cdot s \cdot \log p_s < \frac{3}{2} \cdot s \cdot \log s^{4 / 3} = 2 s \cdot \log s</math>
| |
| − |
| |
| − | Ponownie w GP/PARI sprawdzamy, że otrzymana nierówność jest prawdziwa dla <math>s \geqslant 3</math>
| |
| − |
| |
| − | ::for( s=1, 300, if( prime(s) >= 2*s*log(s), print(s) ))<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | Dowód twierdzenia A30 kończy dowód całego twierdzenia A1. Możemy teraz dokończyć dowód twierdzenia A7 i pokazać, że dla <math>n \geqslant 3</math> prawdziwe jest oszacowanie:
| |
| − |
| |
| − | ::<math>p_1 \cdot \ldots \cdot p_n < (n \log n)^n</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Indukcja matematyczna. Twierdzenie jest prawdziwe dla <math>n = 3</math>. Zakładając prawdziwość twierdzenia dla <math>n</math>, otrzymujemy dla <math>n + 1</math>:
| |
| − |
| |
| − | ::<math>p_1 \cdot \ldots \cdot p_n p_{n + 1} < (n \log n)^n \cdot p_{n + 1} < </math>
| |
| − |
| |
| − | ::::::<math>\quad < n^n \cdot (\log n)^n \cdot 2 (n + 1) \log (n + 1) \leqslant</math>
| |
| − |
| |
| − | ::::::<math>\quad \leqslant n^n \cdot \left( 1 + \frac{1}{n} \right)^n \cdot (n + 1) \cdot (\log n)^n \cdot \log (n + 1) <</math>
| |
| − |
| |
| − | ::::::<math>\quad < (n + 1)^{n + 1} \cdot [\log (n + 1)]^n \cdot \log (n + 1) =</math>
| |
| − |
| |
| − | ::::::<math>\quad = [(n + 1) \cdot \log (n + 1)]^{n + 1}</math>
| |
| − |
| |
| − | Gdzie skorzystaliśmy z twierdzenia A30 oraz z faktu, że ciąg <math>a_n = \left( 1 + \frac{1}{n} \right)^n</math> jest ciągiem ograniczonym <math>2 \leqslant a_n < 3</math> (zobacz twierdzenie A6).<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Uwagi do dowodu ==
| |
| − | Wydłużając znacząco czas obliczeń, moglibyśmy nieco poprawić uzyskane wyżej oszacowanie i udowodnić
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A31</span><br/>
| |
| − | Niech <math>n \geqslant 3</math>. Dla <math>n</math>-tej liczby pierwszej <math>p_n</math> prawdziwe jest oszacowanie
| |
| − |
| |
| − | ::<math>p_n < 1.875 \cdot n \log n</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Z twierdzenia A1 wiemy, że dla <math>n \geqslant 3</math> zachodzi <math>\pi (n) > \frac{2}{3} \cdot \frac{n}{\log n}</math>. Kładąc <math>n = p_s</math>, otrzymujemy dla <math>s \geqslant 2</math>
| |
| − |
| |
| − | ::<math>s = \pi (p_s) > \frac{2}{3} \cdot \frac{p_s}{\log p_s} > (p_s)^{4 / 5}</math>
| |
| − |
| |
| − | Ostatnia nierówność wynika z faktu, że dla <math>x > 7572437.223 \ldots</math> prawdziwe jest oszacowanie
| |
| − |
| |
| − | ::<math>\frac{2}{3} \cdot \frac{x}{\log x} > x^{4 / 5}</math>
| |
| − |
| |
| − | Zatem dla <math>s \geqslant 512830</math> (bo <math>p_{512830} = 7572449 > 7572437.223 \ldots</math>) mamy <math>p_s < s^{5 / 4}</math> i wpisując w PARI/GP polecenie
| |
| − |
| |
| − | ::for(s=1, 520000, if( prime(s) >= s^(5/4), print(s) ))
| |
| − |
| |
| − | sprawdzamy, że otrzymane oszacowanie <math>p_s < s^{5 / 4}</math> jest prawdziwe dla <math>s \geqslant 13760</math>. Wykorzystując ten rezultat i szacując po raz drugi, dostajemy dla <math>s \geqslant 13760</math>
| |
| − |
| |
| − | ::<math>p_s < \frac{3}{2} \cdot s \cdot \log p_s < \frac{3}{2} \cdot s \cdot \log s^{5 / 4} = 1.875 \cdot s \cdot \log s</math>
| |
| − |
| |
| − | Ponownie w GP/PARI sprawdzamy, że otrzymana nierówność jest prawdziwa dla <math>s \geqslant 3</math>:
| |
| − |
| |
| − | ::for(s=1, 15000, if( prime(s)>=1.875*s*log(s), print(s) ))<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A32</span><br/>
| |
| − | Niech <math>n \geqslant 2</math>. Dla funkcji <math>\pi (n)</math> prawdziwe jest oszacowanie
| |
| − |
| |
| − | ::<math>\pi (n) < 1.733 \cdot \frac{n}{\log n}</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Z twierdzenia A1 wiemy, że dla <math>n \geqslant 3</math> jest
| |
| − |
| |
| − | ::<math>\pi (n) > \frac{2}{3} \cdot \frac{n}{\log n} > n^{4 / 5}</math>
| |
| − |
| |
| − | Ostatnia nierówność wynika z faktu, że dla <math>x > 7572437.223 \ldots</math> prawdziwe jest oszacowanie
| |
| − |
| |
| − | ::<math>\frac{2}{3} \cdot \frac{x}{\log x} > x^{4 / 5}</math>
| |
| − |
| |
| − | Korzystając z twierdzenia A9 możemy napisać ciąg nierówności
| |
| − |
| |
| − | ::<math>4^n > P (n) = p_1 p_2 \cdot \ldots \cdot p_{\pi (n)} > \pi (n)^{\pi (n)} > (n^{4 / 5})^{\pi (n)} = n^{4 \pi (n) / 5}</math>
| |
| − |
| |
| − | skąd otrzymujemy, że dla <math>n \geqslant 7572438</math> prawdziwe jest oszacowanie
| |
| − |
| |
| − | ::<math>\pi (n) < 1.733 \cdot \frac{n}{\log n}</math>
| |
| − |
| |
| − | W GP/PARI sprawdzamy, że otrzymana nierówność jest prawdziwa dla <math>n \geqslant 2</math>
| |
| − |
| |
| − | ::for(n=2, 8*10^6, if( primepi(n) >= 1.733*n/log(n), print(n) ))<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Uwaga A33</span><br/>
| |
| − | Dowód twierdzenia A31 wymagał wykorzystania polecenia PARI/GP, w którym wielokrotnie była wywoływana funkcja prime(n). Analogiczna sytuacja miała miejsce w przypadku twierdzenia A32 – tam musieliśmy wielokrotnie wywoływać funkcję primepi(n). Znacznie lepiej w takim przypadku jest napisać krótki program, który zamiast wielokrotnie wywoływać te funkcje, będzie je obliczał w sposób ciągły w całym testowanym przedziale wartości. Taka zmiana znacząco skraca czas obliczeń. Podane niżej programy Test1(n) i Test2(n) wywołane z parametrami n = 520000 i odpowiednio n = 8*10^6 odpowiadają poleceniom:
| |
| − |
| |
| − | ::for(s=1, 520000, if( prime(s) >= s^(5/4), print(s) ))
| |
| − |
| |
| − | ::for(n=2, 8*10^6, if( primepi(n) >= 1.733*n/log(n), print(n) ))
| |
| − |
| |
| − | ale wykonywane są znacznie szybciej.
| |
| − |
| |
| − | Test1(n)=
| |
| − | \\test oszacowania: prime(k) >= k^(5/4) dla 1 <= k <= n
| |
| − | \\bez bezpośredniego odwoływania się do funkcji prime(k)
| |
| − | {local(p, k);
| |
| − | k=1;
| |
| − | p=2;
| |
| − | while(k <= n,
| |
| − | if( p >= k^(5/4), print(k) );
| |
| − | k = k + 1;
| |
| − | p = nextprime(p+1); \\liczba p ma wartość prime(k)
| |
| − | )
| |
| − | }
| |
| − |
| |
| − | Test2(n)=
| |
| − | \\test oszacowania: primepi(k) < 1.733*k/log(k) dla 2 <= k <= n
| |
| − | \\bez bezpośredniego odwoływania się do funkcji primepi(k)
| |
| − | {local(s, k);
| |
| − | s=1;
| |
| − | k=2;
| |
| − | while(k <= n,
| |
| − | if( s >= 1.733*k/log(k), print(k) );
| |
| − | k = k + 1;
| |
| − | s = s + isprime(k); \\ dla kolejnych k liczba s ma wartość primepi(k)
| |
| − | )
| |
| − | }
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Uwaga A34</span><br/>
| |
| − | Czytelnik nie powinien mieć złudzeń, że postępując podobnie, uzyskamy istotne polepszenie oszacowania funkcji <math>\pi (n)</math> lub <math>p_n</math>. Już osiągnięcie tą drogą oszacowania <math>p_n < 1.6 \cdot n \log n</math> przekracza możliwości obliczeniowe współczesnych komputerów. Wystarczy zauważyć, że nierówność
| |
| − |
| |
| − | ::<math>\frac{2}{3} \cdot \frac{x}{\log x} > x^{15 / 16}</math>
| |
| − |
| |
| − | jest prawdziwa dla <math>x > 7.671 \cdot 10^{32}</math>.
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Zastosowania ==
| |
| − |
| |
| − | Ciekawy rezultat wynika z twierdzenia A7, ale wcześniej musimy udowodnić twierdzenie o średniej arytmetycznej i geometrycznej.
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A35</span><br/>
| |
| − | Dla dowolnych liczb dodatnich <math>a_1, a_2, \ldots, a_n</math> średnia arytmetyczna jest nie mniejsza od średniej geometrycznej
| |
| − |
| |
| − | ::<math>\frac{a_1 + a_2 + \ldots + a_n}{n} \geqslant \sqrt[n]{a_1 a_2 \cdot \ldots \cdot a_n}</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Twierdzenie jest w sposób oczywisty prawdziwe dla <math>n = 1</math>. Równie łatwo stwierdzamy prawdziwość nierówności dla <math>n = 2</math>
| |
| − |
| |
| − | ::<math>(a_1 - a_2)^2 \geqslant 0</math>
| |
| − |
| |
| − | ::<math>a^2_1 - 2 a_1 a_2 + a^2_2 \geqslant 0</math>
| |
| − |
| |
| − | ::<math>a^2_1 + 2 a_1 a_2 + a^2_2 \geqslant 4 a_1 a_2</math>
| |
| − |
| |
| − | ::<math>(a_1 + a_2)^2 \geqslant 4 a_1 a_2</math>
| |
| − |
| |
| − | ::<math>\frac{a_1 + a_2}{2} \geqslant \sqrt{a_1 a_2}</math>
| |
| − |
| |
| − | Dla potrzeb dowodu zapiszemy dowodzoną nierówność w postaci
| |
| − |
| |
| − | ::<math>\left( \frac{a_1 + a_2 + \ldots + a_n}{n} \right)^n \geqslant a_1 a_2 \cdot \ldots \cdot a_n</math>
| |
| − |
| |
| − | Zakładając, że twierdzenie jest prawdziwe dla wszystkich liczb całkowitych dodatnich nie większych od <math>n</math> dla <math>n + 1</math> mamy
| |
| − |
| |
| − | a) w przypadku gdy <math>n + 1 = 2 k</math> jest liczbą parzystą
| |
| − |
| |
| − | ::<math>\left( \frac{a_1 + a_2 + \ldots + a_{n + 1}}{n + 1} \right)^{n + 1} = \left( \frac{a_1 + a_2 + \ldots + a_{2 k}}{2 k} \right)^{2 k} =</math>
| |
| − |
| |
| − | ::::::::::<math>\quad = \left[ \left( \frac{\frac{a_1 + a_2}{2} + \frac{a_3 + a_4}{2} + \ldots + \frac{a_{2 k - 1} + a_{2 k}}{2}}{k} \right)^k \right]^2 \geqslant</math>
| |
| − |
| |
| − | ::::::::::<math>\quad \geqslant \left( \frac{a_1 + a_2}{2} \cdot \frac{a_3 + a_4}{2} \cdot \ldots \cdot \frac{a_{2 k - 1} + a_{2 k}}{2} \right)^2 \geqslant</math>
| |
| − |
| |
| − | ::::::::::<math>\quad \geqslant \left( \sqrt{a_1 a_2} \cdot \sqrt{a_3 a_4} \cdot \ldots \cdot \sqrt{a_{2 k - 1} a_{2 k}} \right)^2 =</math>
| |
| − |
| |
| − | ::::::::::<math>\quad = a_1 a_2 \cdot \ldots \cdot a_{2 k} =</math>
| |
| − |
| |
| − | ::::::::::<math>\quad = a_1 a_2 \cdot \ldots \cdot a_{n + 1}</math>
| |
| − |
| |
| − | Gdzie skorzystaliśmy z założenia indukcyjnego i prawdziwości dowodzonego twierdzenia dla <math>n = 2</math>.
| |
| − |
| |
| − | b) w przypadku gdy <math>n + 1 = 2 k - 1</math> jest liczbą nieparzystą, możemy skorzystać z udowodnionego wyżej punktu a) dla '''parzystej''' ilości liczb
| |
| − |
| |
| − | ::<math>a_1, a_2, \ldots, a_{2 k - 1}, S</math>
| |
| − |
| |
| − | gdzie przez <math>S</math> oznaczyliśmy średnią arytmetyczną liczb <math>a_1, a_2, \ldots, a_{2 k - 1}</math>
| |
| − |
| |
| − | ::<math>S = \frac{a_1 + a_2 + \ldots + a_{2 k - 1}}{2 k - 1}</math>
| |
| − |
| |
| − | Na mocy punktu a) prawdziwa jest nierówność
| |
| − |
| |
| − | ::<math>\left( \frac{a_1 + a_2 + \ldots + a_{2 k - 1} + S}{2 k} \right)^{2 k} = \left( \frac{(2 k - 1) S + S}{2 k} \right)^{2 k} \geqslant a_1 a_2 \cdot \ldots \cdot a_{2 k - 1} \cdot S</math>
| |
| − |
| |
| − | Skąd otrzymujemy
| |
| − |
| |
| − | ::<math>S^{2 k} \geqslant a_1 a_2 \cdot \ldots \cdot a_{2 k - 1} \cdot S</math>
| |
| − |
| |
| − | ::<math>S^{2 k - 1} \geqslant a_1 a_2 \cdot \ldots \cdot a_{2 k - 1}</math>
| |
| − |
| |
| − | Co należało pokazać.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A36</span><br/>
| |
| − | Dla <math>n \geqslant 1</math> prawdziwa jest nierówność <math>p_1 + p_2 + \ldots + p_n > n^2</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Korzystając z twierdzeń A7 i A35 możemy napisać następujący ciąg nierówności dla <math>n</math> kolejnych liczb pierwszych
| |
| − |
| |
| − | ::<math>\frac{p_1 + p_2 + \ldots + p_n}{n} \geqslant \sqrt[n]{p_1 \cdot p_2 \cdot \ldots \cdot p_n} > \sqrt[n]{n^n} = n</math>
| |
| − |
| |
| − | Stąd otrzymujemy natychmiast tezę twierdzenia, którą sprawdzamy dla <math>n < 13</math>. Do sprawdzenia można wykorzystać proste polecenie w PARI/GP
| |
| − |
| |
| − | ::for(n=1, 20, s=0; for(k=1, n, s=s+prime(k)); if( s <= n^2, print(n) ))<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | Twierdzenie A1 pozwala nam udowodnić różne oszacowania funkcji <math>\pi (n)</math> i <math>p_n</math>, które byłyby trudne do uzyskania inną drogą. Wykorzystujemy do tego znany fakt, że dla dowolnego <math>\varepsilon > 0</math> istnieje takie <math>n_0</math>, że dla każdego <math>n > n_0</math> prawdziwa jest nierówność <math>\log x < x^{\varepsilon}</math>. Inaczej mówiąc, funkcja <math>\log x</math> rośnie wolniej niż najwolniej rosnąca funkcja potęgowa. Nim przejdziemy do dowodu takich przykładowych oszacowań, udowodnimy pomocnicze twierdzenie, które wykorzystamy przy szacowaniu.
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A37</span><br/>
| |
| − | Prawdziwe są następujące nierówności:
| |
| − |
| |
| − | ::1. <math>e^x > x</math>, dla każdego <math>x \in \mathbb{R}</math>
| |
| − |
| |
| − | ::2. <math>\log x < n \cdot x^{1 / n}</math>, dla każdego <math>x \in \mathbb{R}_+</math> i dowolnego <math>n \in \mathbb{Z}_+</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Można powiedzieć, że dowód pierwszej nierówności jest oczywisty, bo każdy z nas ma przed oczami przebieg funkcji <math>e^x</math> i <math>x</math>:
| |
| − |
| |
| − | [[File: Czebyszew-wykres-2.png|center]]
| |
| − |
| |
| − | Komu taki dowód obrazkowy nie wystarcza, może posłużyć się rozwinięciem funkcji <math>e^x</math> w szereg nieskończony
| |
| − |
| |
| − | ::<math>e^x = \underset{k = 0}{\overset{\infty}{\sum}} \frac{x^k}{k!} = 1 + x + \frac{1}{2} x^2 + \frac{1}{6} x^3 + \ldots</math>
| |
| − |
| |
| − | zbieżny dla dowolnego <math>x \in \mathbb{R}</math>. Teraz wystarczy zauważyć, że:
| |
| − |
| |
| − | ::* dla <math>x > 0</math> prawdziwe jest oszacowanie: <math>e^x > 1 + x > x</math>
| |
| − | ::* w punkcie <math>x = 0</math> mamy <math>e^x = 1</math> i <math>x = 0</math>
| |
| − | ::* dla <math>x < 0</math> funkcja <math>e^x</math> jest dodatnia, a funkcja <math>x</math> ujemna
| |
| − |
| |
| − |
| |
| − | W drugiej nierówności połóżmy zmienną pomocniczą <math>x = e^y</math>, gdzie <math>y \in \mathbb{R}</math>. Otrzymujemy
| |
| − |
| |
| − | ::<math>y < n \cdot (e^y)^{1 / n}</math>
| |
| − |
| |
| − | czyli
| |
| − |
| |
| − | ::<math>\frac{y}{n} < e^{y / n}</math>
| |
| − |
| |
| − | Kładąc <math>z = \frac{y}{n}</math>, gdzie <math>z \in \mathbb{R}</math>, mamy <math>z < e^z</math>. Otrzymana nierówność jest prawdziwa dla każdego <math>z \in \mathbb{R}</math> na mocy punktu 1 tego twierdzenia.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A38</span><br/>
| |
| − | Dla funkcji <math>p_n</math> i <math>\pi (n)</math> prawdziwe są następujące oszacowania:
| |
| − |
| |
| − | ::<math>10 n \underset{n \geqslant 6473}{<} p_n \underset{n \geqslant 2}{<} n^2</math>
| |
| − |
| |
| − | ::<math>\sqrt{n} \underset{n \geqslant 5}{<} \pi (n) \underset{n \geqslant 64721}{<} \frac{n}{10}</math>
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | <span style="border-bottom-style: double;">Lewa górna nierówność.</span> Z twierdzenia A1 wiemy, że dla <math>n \geqslant 1</math> jest <math>p_n > 0.72 \cdot n \log n</math>. Wystarczy rozwiązać nierówność:
| |
| − |
| |
| − | ::<math>0.72 \cdot \log n > 10</math>
| |
| − |
| |
| − | czyli <math>n > \exp \left( \frac{10}{0.72} \right) = 1076137.5</math>
| |
| − |
| |
| − | W PARI/GP wpisujemy polecenie:
| |
| − |
| |
| − | ::for(n=1, 11*10^5, if( prime(n) <= 10*n, print(n) ))
| |
| − |
| |
| − |
| |
| − | <span style="border-bottom-style: double;">Prawa górna nierówność.</span> Z twierdzenia A1 wiemy, że dla <math>n \geqslant 3</math> jest <math>p_n < 2 n \log n</math>. Zatem wystarczy pokazać, że <math>2 n \log n < n^2</math>. Korzystając z twierdzenia A37, łatwo zauważmy, że dla <math>n > 16</math> jest:
| |
| − |
| |
| − | ::<math>n - 2 \log n > n - 2 \cdot 2 \cdot n^{1 / 2} = \sqrt{n} \left( \sqrt{n} - 4 \right) > 0</math>
| |
| − |
| |
| − | Przypadki <math>n \leqslant 16</math> sprawdzamy bezpośrednio.
| |
| − |
| |
| − |
| |
| − | <span style="border-bottom-style: double;">Lewa dolna nierówność.</span> Z twierdzenia A1 wiemy, że dla <math>n \geqslant 3</math> jest <math>\pi (n) > \frac{2}{3} \cdot \frac{n}{\log n}</math>. Zatem wystarczy pokazać, że <math>\frac{2}{3} \cdot \frac{n}{\log n} > \sqrt{n}</math>. Korzystając z twierdzenia A37, łatwo zauważmy, że dla <math>n > 6^4 = 1296</math> jest:
| |
| − |
| |
| − | ::<math>\frac{2}{3} \cdot \frac{n}{\log n} - \sqrt{n} > \frac{2}{3} \cdot \frac{n}{4 \cdot n^{1 / 4}} - \sqrt{n} = \frac{1}{6} \cdot n^{3 / 4} - \sqrt{n} = \frac{1}{6} \sqrt{n} (n^{1 / 4} - 6) > 0</math>
| |
| − |
| |
| − | Sprawdzenie przypadków <math>n \leqslant 1296</math> sprowadza się do wpisania w PARI/GP polecenia:
| |
| − |
| |
| − | ::for(n=1, 2000, if( primepi(n) <= sqrt(n), print(n) ))
| |
| − |
| |
| − |
| |
| − | <span style="border-bottom-style: double;">Prawa dolna nierówność.</span> Z twierdzenia A1 wiemy, że dla <math>n \geqslant 2</math> jest <math>\pi (n) < \frac{2 n}{\log n}</math>. Zatem wystarczy pokazać, że <math>\frac{2 n}{\log n} < \frac{n}{10}</math>. Nierówność ta jest prawdziwa dla <math>\log n > 20</math>, czyli dla
| |
| − |
| |
| − | ::<math>n > e^{20} > 485165195.4</math>
| |
| − |
| |
| − | Sprawdzenie przypadków dla <math>n \leqslant 490 \cdot 10^6</math> będzie wymagało napisania w PARI/GP krótkiego programu i wywołania go z parametrem n = 490*10^6
| |
| − |
| |
| − | Test3(n)=
| |
| − | \\test oszacowania: primepi(k) < k/10 dla 2 <= k <= n
| |
| − | \\bez bezpośredniego odwoływania się do funkcji primepi(k)
| |
| − | {local(s, k);
| |
| − | s=1;
| |
| − | k=2;
| |
| − | while(k <= n,
| |
| − | if( s >= k/10, print(k) );
| |
| − | k = k + 1;
| |
| − | s = s + isprime(k); \\ dla kolejnych k liczba s ma wartość primepi(k)
| |
| − | )
| |
| − | }<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A39</span><br/>
| |
| − | Każda liczba pierwsza <math>p</math>, taka że <math>p \in \left( \frac{n}{2}, n \right]</math> występuje w rozwinięciu <math>n!</math> na czynniki pierwsze z wykładnikiem równym jeden.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | Z twierdzenia A21 wiemy, że każda liczba pierwsza <math>p</math> występuje w iloczynie <math>n!</math> z wykładnikiem <math>W_p (n!) = \sum_{k = 1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor</math>
| |
| − |
| |
| − | Z założenia <math>p \leqslant n</math> i <math>2 p > n</math>, zatem:
| |
| − |
| |
| − | ::1. <math>\frac{n}{p} \geqslant 1</math> oraz <math>\frac{n}{p} < 2</math>, czyli <math>\left\lfloor \frac{n}{p} \right\rfloor = 1</math>
| |
| − |
| |
| − | ::2. <math>\frac{n}{p^2} < \frac{2}{p} \leqslant 1</math>, czyli <math>\left\lfloor \frac{n}{p^2} \right\rfloor = 0</math> i tym bardziej <math>\left\lfloor \frac{n}{p^k} \right\rfloor = 0</math> dla <math>k \geqslant 3</math><br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | Rezultat uzyskany w twierdzeniu A25 zainspirował nas do postawienia pytania: jakie warunki musi spełniać liczba pierwsza <math>p</math>, aby występowała w rozwinięciu liczby <math>\binom{2 n}{n}</math> na czynniki pierwsze z wykładnikiem równym jeden lub równym zero? Twierdzenia A40 i A42 udzielają na to pytanie precyzyjnej odpowiedzi. Przykłady A41 i A43 to tylko twierdzenia A40 i A42 dla wybranych wartości liczby <math>k</math>. Jeśli Czytelnik nie miał problemów ze zrozumieniem dowodów twierdzeń A40 i A42, to może je pominąć.
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A40</span><br/>
| |
| − | Niech <math>k</math> będzie dowolną ustaloną liczbą naturalną. Jeżeli <math>n \geqslant 2 (k + 1) \left( k + \tfrac{1}{2} \right)</math> i liczba pierwsza <math>p \in \left(
| |
| − | \frac{n}{k + 1}, \frac{n}{k + \frac{1}{2}} \right]</math>, to <math>p</math> występuje w rozwinięciu liczby <math>\binom{2 n}{n}</math> na czynniki pierwsze z wykładnikiem równym jeden.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | '''Najpierw udowodnimy przypadek <math>k = 0</math>.'''
| |
| − |
| |
| − | Zauważmy, że każda liczba pierwsza <math>p \in (n, 2 n]</math> występuje dokładnie jeden raz w liczniku ułamka
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = \frac{(2 n) !}{(n!)^2} = \frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | i nie występuje w mianowniku. Zatem w rozwinięciu współczynnika dwumianowego <math>\binom{2 n}{n}</math> na czynniki pierwsze wystąpi z wykładnikiem równym <math>1</math>.
| |
| − |
| |
| − | Co kończy dowód twierdzenia w przypadku, gdy <math>k = 0</math>.
| |
| − |
| |
| − | '''Możemy teraz przejść do dowodu dla wszystkich <math>k \geqslant 1</math>.'''
| |
| − |
| |
| − |
| |
| − | <span style="border-bottom-style: double;">Dowód na podstawie analizy krotności pojawiania się liczby <math>p</math></span><br/><br/>
| |
| − | Zapiszmy współczynnik dwumianowy <math>\binom{2 n}{n}</math> w postaci ułamka
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = \frac{(2 n) !}{(n!)^2} = \frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | Rozważmy dowolną liczbę pierwszą występującą w mianowniku wypisanego wyżej ułamka. Potrzebujemy, aby <math>p</math> spełniała następujące warunki:
| |
| − |
| |
| − | * <math>k p \leqslant n</math> — warunek ten zapewnia nam, że liczba <math>p</math> pojawi się co najmniej <math>k</math> razy w mianowniku
| |
| − | * <math>(k + 1) p > n</math> — warunek ten zapewnia nam, że liczba <math>p</math> pojawi się dokładnie <math>k</math> razy w mianowniku (jako <math>p, 2 p, \ldots, k p</math>)
| |
| − | * <math>(2 k + 1) p \leqslant 2 n</math> — warunek ten (łącznie z warunkiem <math>(k + 1) p > n</math>) zapewnia nam, że liczba <math>p</math> pojawi się co najmniej <math>k + 1</math> razy w liczniku
| |
| − | * <math>(2 k + 2) p > 2 n</math> — warunek ten (łącznie z warunkiem <math>(2 k + 1) p \leqslant 2 n</math>) zapewnia nam, że liczba <math>p</math> pojawi się dokładnie <math>k + 1</math> razy w liczniku (jako <math>(k + 1) p, (k + 2) p, \ldots, (2 k + 1) p</math>)
| |
| − |
| |
| − | Łącząc otrzymane warunki, otrzymujemy, że liczba pierwsza <math>p \in \left(\frac{n}{k + 1}, \frac{n}{k + \frac{1}{2}} \right]</math> pojawia się dokładnie <math>k</math> razy w mianowniku i dokładnie <math>k + 1</math> razy w liczniku ułamka
| |
| − |
| |
| − | ::<math>\frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | Zatem występuje w rozwinięciu współczynnika dwumianowego <math>\binom{2 n}{n}</math> na czynniki pierwsze z wykładnikiem jeden.
| |
| − |
| |
| − | Niech <math>q</math> będzie największą liczbą pierwszą nie większą od ustalonej liczby <math>2 k + 1</math>. Rozpatrywane przez nas wielokrotności liczby zwiększają wykładniki, z jakimi występują liczby pierwsze <math>r_i \in \{ 2, 3, \ldots, q \}</math>. Dlatego twierdzenie nie może dotyczyć tych liczb i musimy nałożyć warunek
| |
| − |
| |
| − | ::<math>r_i \notin \left( \frac{n}{k + 1}, \frac{n}{k + \frac{1}{2}} \right]</math>
| |
| − |
| |
| − | Warunek ten będzie z pewnością spełniony, gdy
| |
| − |
| |
| − | ::<math>q \leqslant 2 k + 1 \leqslant \frac{n}{k + 1}</math>
| |
| − |
| |
| − | czyli dla <math>n</math> spełniających nierówność <math>n \geqslant (k + 1) (2 k + 1)</math>.
| |
| − |
| |
| − | Oczywiście nie wyklucza to możliwości, że istnieją liczby <math>n < 2 (k + 1) (k + \tfrac{1}{2})</math>, dla których twierdzenie jest prawdziwe. Pozostaje (przy ustalonej wartości liczby <math>k</math>) bezpośrednio sprawdzić prawdziwość twierdzenia dla <math>n < 2 (k + 1) (k + \tfrac{1}{2})</math>.
| |
| − |
| |
| − |
| |
| − | <span style="border-bottom-style: double;">Dowód na podstawie twierdzenia A24</span><br/><br/>
| |
| − | Rozważmy najpierw pierwszy składnik sumy
| |
| − |
| |
| − | ::<math>\sum^{\infty}_{s = 1} \left ( \left \lfloor \frac{2 n}{p^{s}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{s}} \right \rfloor \right )</math>
| |
| − |
| |
| − | Ponieważ przypuszczamy, że składnik ten będzie równy <math>1</math>, to będziemy szukali oszacowania od dołu. Z założenia mamy
| |
| − |
| |
| − | 1) <math>p > \frac{n}{k + 1} \quad\ \implies \quad \frac{n}{p} < k + 1 \quad\ \implies \quad \left\lfloor \frac{n}{p} \right\rfloor \leqslant k</math>
| |
| − |
| |
| − | 2) <math>p \leqslant \frac{n}{k + \tfrac{1}{2}} \quad\ \implies \quad \frac{2 n}{p} \geqslant 2 k + 1 \quad\ \implies \quad \left\lfloor \frac{2 n}{p} \right\rfloor \geqslant 2 k + 1</math>
| |
| − |
| |
| − | Zatem
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{2 n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \geqslant 2 k + 1 - 2 k = 1</math>
| |
| − |
| |
| − | Ponieważ każdy ze składników sumy może być równy tylko <math>0</math> lub <math>1</math>, to otrzymujemy
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{2 n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor = 1</math>
| |
| − |
| |
| − |
| |
| − | Założenie, że <math>n \geqslant 2 (k + 1)^2</math> pozwoli uprościć obliczenia dla drugiego i następnych składników sumy
| |
| − |
| |
| − | ::<math>p > \frac{n}{k + 1} \quad \implies \quad \frac{2 n}{p} < 2 k + 2 \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \! \! \implies \quad \frac{(2 n)^s}{p^s} < (2 k + 2)^s \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \! \! \implies \quad \frac{2 n}{p^s} < \frac{(2 k + 2)^2}{2 n} \cdot \left( \frac{2 k + 2}{2 n} \right)^{s - 2} \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \! \! \implies \quad \frac{2 n}{p^s} < \frac{(2 k + 2)^2}{2 n} \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \! \! \implies \quad \frac{2 n}{p^s} < 1 \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \! \! \implies \quad \left\lfloor \frac{2 n}{p^s} \right\rfloor = 0</math>
| |
| − |
| |
| − | Jeżeli <math>\left\lfloor \frac{2 n}{p^s} \right\rfloor = 0</math>, to również musi być <math>\left\lfloor \frac{n}{p^s} \right\rfloor = 0</math>. Pokazaliśmy, że dla <math>n \geqslant 2 (k + 1)^2</math> jest
| |
| − |
| |
| − | ::<math>\sum^{\infty}_{s = 1} \left ( \left \lfloor \frac{2 n}{p^{s}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{s}} \right \rfloor \right ) = 1</math>
| |
| − |
| |
| − | Pozostaje bezpośrednio sprawdzić, dla jakich wartości <math>n < 2 (k + 1)^2</math> twierdzenie pozostaje prawdziwe.
| |
| − |
| |
| − | Ponieważ analiza krotności pojawiania się liczby pierwszej <math>p</math> jest bardziej precyzyjna, to podajemy, że twierdzenie jest z pewnością prawdziwe dla <math>n \geqslant 2 (k + 1) (k + \tfrac{1}{2})</math>
| |
| − | <br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Przykład A41</span><br/>
| |
| − | Jeżeli <math>n \geqslant 6</math> i liczba pierwsza <math>p \in \left( \frac{n}{2}, \frac{2 n}{3} \right]</math>, to <math>p</math> występuje w rozwinięciu liczby <math>\binom{2 n}{n}</math> na czynniki pierwsze z wykładnikiem równym jeden.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | <span style="border-bottom-style: double;">Dowód na podstawie analizy krotności pojawiania się liczby <math>p</math></span><br/><br/>
| |
| − | Zapiszmy współczynnik dwumianowy <math>\binom{2 n}{n}</math> w postaci ułamka
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = \frac{(2 n) !}{(n!)^2} = \frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | Rozważmy dowolną liczbę pierwszą występującą w mianowniku wypisanego wyżej ułamka. Potrzebujemy, aby <math>p</math> spełniała następujące warunki:
| |
| − |
| |
| − | * <math>p \leqslant n</math> — warunek ten zapewnia nam, że liczba <math>p</math> pojawi się co najmniej jeden raz w mianowniku
| |
| − | * <math>2 p > n</math> — warunek ten zapewnia nam, że liczba <math>p</math> pojawi się dokładnie jeden raz w mianowniku (jako <math>p</math>)
| |
| − | * <math>3 p \leqslant 2 n</math> — warunek ten (łącznie z warunkiem <math>2 p > n</math>) zapewnia nam, że liczba <math>p</math> pojawi się co najmniej dwa razy w liczniku
| |
| − | * <math>4 p > 2 n</math> — warunek ten (łącznie z warunkiem <math>3 p \leqslant 2 n</math>) zapewnia nam, że liczba <math>p</math> pojawi się dokładnie dwa razy w liczniku (jako <math>2 p</math> i <math>3 p</math>)
| |
| − |
| |
| − | Łącząc otrzymane warunki, otrzymujemy, że liczba pierwsza <math>p \in \left( \tfrac{n}{2}, \tfrac{2 n}{3} \right]</math> pojawia się dokładnie jeden raz w mianowniku i dokładnie dwa razy w liczniku ułamka
| |
| − |
| |
| − | ::<math>\frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | Zatem występuje w rozwinięciu współczynnika dwumianowego <math>\binom{2 n}{n}</math> na czynniki pierwsze z wykładnikiem jeden.
| |
| − |
| |
| − | Wielokrotności liczby <math>p</math> podnoszą wykładniki, z jakimi występują liczby pierwsze <math>p = 2, 3</math>. Dlatego zakładamy, że <math>n \geqslant 6</math>, bo dla <math>n \geqslant 6</math> liczby pierwsze <math>p = 2, 3</math> nie spełniają warunku <math>p \in \left( \tfrac{n}{2}, \tfrac{2 n}{3} \right]</math>.
| |
| − |
| |
| − | Bezpośrednio sprawdzamy, że twierdzenie nie jest prawdziwe dla <math>n = 5</math> i liczba <math>3^2</math> dzieli liczbę <math>\binom{10}{5} = 252 = 9 \cdot 28</math>
| |
| − |
| |
| − |
| |
| − | <span style="border-bottom-style: double;">Dowód na podstawie twierdzenia A24</span><br/><br/>
| |
| − | Rozważmy najpierw pierwszy składnik sumy
| |
| − |
| |
| − | ::<math>\sum^{\infty}_{k = 1} \left ( \left \lfloor \frac{2 n}{p^{k}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{k}} \right \rfloor \right )</math>
| |
| − |
| |
| − | Ponieważ przypuszczamy, że składnik ten będzie równy <math>1</math>, to będziemy szukali oszacowania od dołu. Z założenia mamy
| |
| − |
| |
| − | ::1) <math>p > \frac{n}{2} \quad \implies \quad \frac{n}{p} < 2 \quad \implies \quad \left\lfloor \frac{n}{p} \right\rfloor \leqslant 1</math>
| |
| − |
| |
| − | ::2) <math>p \leqslant \frac{2 n}{3} \quad \implies \quad \frac{2 n}{p} \geqslant 3 \quad \implies \quad \left\lfloor \frac{2 n}{p} \right\rfloor \geqslant 3</math>
| |
| − |
| |
| − | Zatem
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{2 n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \geqslant 3 - 2 = 1</math>
| |
| − |
| |
| − | Ponieważ każdy ze składników sumy może być równy tylko <math>0</math> lub <math>1</math>, to otrzymujemy
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{2 n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor = 1</math>
| |
| − |
| |
| − |
| |
| − | Założenie, że <math>n \geqslant 9</math> pozwoli uprościć obliczenia dla drugiego i następnych składników sumy
| |
| − |
| |
| − | ::<math>p > \frac{n}{2} \quad \implies \quad \frac{(2 n)^k}{p^k} < 4^k \quad \implies \quad \frac{2 n}{p^k} < \frac{16}{2 n} \cdot \left( \frac{4}{2 n} \right)^{k - 2} \quad \implies \quad \frac{2 n}{p^k} \leqslant \frac{16}{2 n} \quad \implies \quad \frac{2 n}{p^k} \leqslant \frac{16}{18} \quad \implies \quad \left\lfloor \frac{2 n}{p^k} \right\rfloor = 0</math>
| |
| − |
| |
| − | Jeżeli <math>\left\lfloor \frac{2 n}{p^k} \right\rfloor = 0</math>, to również musi być <math>\left\lfloor \frac{n}{p^k} \right\rfloor = 0</math>. Pokazaliśmy, że dla <math>n \geqslant 9</math> jest
| |
| − |
| |
| − | ::<math>\sum^{\infty}_{k = 1} \left ( \left \lfloor \frac{2 n}{p^{k}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{k}} \right \rfloor \right ) = 1</math>
| |
| − |
| |
| − | Dla <math>n = 6, 7</math> żadna liczba pierwsza nie należy do <math>\left( \tfrac{n}{2}, \tfrac{2 n}{3} \right]</math>. Dla <math>n = 8</math> łatwo sprawdzamy, że liczba <math>5</math> wchodzi do rozkładu liczby <math>\binom{16}{8} = 12870</math> na czynniki pierwsze z wykładnikiem równym jeden.
| |
| − |
| |
| − | Zatem dla <math>n \geqslant 6</math> liczba pierwsza <math>p \in \left( \tfrac{n}{2}, \tfrac{2 n}{3} \right]</math> wchodzi do rozkładu liczby <math>\binom{2 n}{n}</math> na czynniki pierwsze z wykładnikiem równym jeden.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Twierdzenie A42</span><br/>
| |
| − | Niech <math>k</math> będzie dowolną ustaloną liczbą całkowitą dodatnią. Jeżeli liczba pierwsza <math>p \in \left( \frac{n}{k + \tfrac{1}{2}}, \frac{n}{k} \right]</math>, to dla <math>n \geqslant 2 k (k + \tfrac{1}{2})</math> liczba <math>p</math> nie występuje w rozwinięciu liczby <math>\binom{2 n}{n}</math> na czynniki pierwsze.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | <span style="border-bottom-style: double;">Dowód na podstawie analizy krotności pojawiania się liczby <math>p</math></span><br/><br/>
| |
| − | Zapiszmy współczynnik dwumianowy <math>\binom{2 n}{n}</math> w postaci ułamka
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = \frac{(2 n) !}{(n!)^2} = \frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | Rozważmy dowolną liczbę pierwszą <math>p</math> występującą w mianowniku wypisanego wyżej ułamka. Potrzebujemy, aby <math>p</math> spełniała następujące warunki:
| |
| − |
| |
| − | * <math>k p \leqslant n</math> — warunek ten zapewnia nam, że liczba <math>p</math> pojawi się co najmniej <math>k</math> razy w mianowniku
| |
| − | * <math>(k + 1) p > n</math> — warunek ten zapewnia nam, że liczba <math>p</math> pojawi się dokładnie <math>k</math> razy w mianowniku (jako <math>p, 2 p, \ldots, k p</math>)
| |
| − | * <math>2 k p \leqslant 2 n</math> — warunek ten (łącznie z warunkiem <math>(k + 1) p > n</math>) zapewnia nam, że liczba <math>p</math> pojawi się co najmniej <math>k</math> razy w liczniku
| |
| − | * <math>(2 k + 1) p > 2 n</math> — warunek ten (łącznie z warunkiem <math>2 k p \leqslant 2 n</math>) zapewnia nam, że liczba <math>p</math> pojawi się dokładnie <math>k</math> razy w liczniku (jako <math>(k + 1) p, (k + 2) p, \ldots, 2 k p</math>)
| |
| − |
| |
| − |
| |
| − | Łącząc otrzymane warunki, otrzymujemy, że liczba pierwsza <math>p \in \left( \frac{n}{k + \frac{1}{2}}, \frac{n}{k} \right]</math> pojawia się dokładnie <math>k</math> razy w mianowniku i dokładnie <math>k</math> razy w liczniku ułamka
| |
| − |
| |
| − | ::<math>\frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | Co oznacza, że <math>p</math> nie występuje w rozwinięciu współczynnika dwumianowego <math>\binom{2 n}{n}</math> na czynniki pierwsze.
| |
| − |
| |
| − | Niech <math>q</math> będzie największą liczbą pierwszą nie większą od ustalonej liczby <math>2 k</math>. Rozpatrywane przez nas wielokrotności liczby <math>p</math> zwiększają wykładniki, z jakimi występują liczby pierwsze <math>r_i \in \{ 2, 3, \ldots, q \}</math>. Dlatego twierdzenie nie może dotyczyć tych liczb i musimy nałożyć warunek
| |
| − |
| |
| − | ::<math>r_i \notin \left( \frac{n}{k + \frac{1}{2}}, \frac{n}{k} \right]</math>
| |
| − |
| |
| − | Warunek ten będzie z pewnością spełniony, gdy
| |
| − |
| |
| − | ::<math>q \leqslant 2 k \leqslant \frac{n}{k + \frac{1}{2}}</math>
| |
| − |
| |
| − | czyli dla <math>n</math> spełniających nierówność <math>n \geqslant 2 k (k + \tfrac{1}{2})</math>. Oczywiście nie wyklucza to możliwości, że istnieją liczby <math>n < 2 k (k + \tfrac{1}{2})</math>, dla których twierdzenie jest prawdziwe. Pozostaje (przy ustalonej wartości liczby <math>k</math>) bezpośrednio sprawdzić prawdziwość twierdzenia dla <math>n < 2 k (k + \tfrac{1}{2})</math>.
| |
| − |
| |
| − |
| |
| − | <span style="border-bottom-style: double;">Dowód na podstawie twierdzenia A24</span><br/><br/>
| |
| − | Rozważmy najpierw pierwszy składnik sumy
| |
| − |
| |
| − | ::<math>\sum^{\infty}_{s = 1} \left ( \left \lfloor \frac{2 n}{p^{s}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{s}} \right \rfloor \right )</math>
| |
| − |
| |
| − | Ponieważ przypuszczamy, że składnik ten będzie równy <math>0</math>, to będziemy szukali oszacowania od góry. Z założenia mamy
| |
| − |
| |
| − | 1) <math>p > \frac{n}{k + \frac{1}{2}} \quad\ \implies \quad \frac{2 n}{p} < 2 k + 1 \quad\ \implies \quad \left\lfloor \frac{2 n}{p} \right\rfloor \leqslant 2 k</math>
| |
| − |
| |
| − | 2) <math>p \leqslant \frac{n}{k} \quad\ \implies \quad \frac{n}{p} \geqslant k \quad\ \implies \quad \left\lfloor \frac{n}{p} \right\rfloor \geqslant k</math>
| |
| − |
| |
| − | Zatem
| |
| − | ::<math>\left\lfloor \frac{2 n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \leqslant 2 k - 2 k = 0</math>
| |
| − |
| |
| − | Ponieważ każdy ze składników sumy może być równy tylko <math>0</math> lub <math>1</math>, to otrzymujemy
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{2 n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor = 0</math>
| |
| − |
| |
| − |
| |
| − | Założenie, że <math>2 n \geqslant (2 k + 1)^2</math> pozwoli uprościć obliczenia dla drugiego i następnych składników sumy
| |
| − |
| |
| − | ::<math>p > \frac{2 n}{2 k + 1} \quad \implies \quad \frac{(2 n)^s}{p^s} < (2 k + 1)^s \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \; \implies \quad \frac{2 n}{p^s} < \frac{(2 k + 1)^2}{2 n} \cdot \left( \frac{2 k + 1}{2 n} \right)^{s - 2} \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \; \implies \quad \frac{2 n}{p^s} < \frac{(2 k + 1)^2}{2 n} \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \; \implies \quad \frac{2 n}{p^s} < 1 \quad \implies</math>
| |
| − |
| |
| − | ::<math>\qquad \qquad \qquad \; \implies \quad \left\lfloor \frac{2 n}{p^s} \right\rfloor = 0</math>
| |
| − |
| |
| − | Jeżeli <math>\left\lfloor \frac{2 n}{p^s} \right\rfloor = 0</math>, to również musi być <math>\left\lfloor \frac{n}{p^s} \right\rfloor = 0</math>. Pokazaliśmy, że dla <math>2 n \geqslant (2 k + 1)^2</math> jest
| |
| − |
| |
| − | ::<math>\sum^{\infty}_{s = 1} \left ( \left \lfloor \frac{2 n}{p^{s}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{s}} \right \rfloor \right ) = 0</math>
| |
| − |
| |
| − | Pozostaje bezpośrednio sprawdzić, dla jakich wartości <math>n < \frac{1}{2} (2 k + 1)^2</math> twierdzenie pozostaje prawdziwe.
| |
| − |
| |
| − | Ponieważ analiza krotności pojawiania się liczby pierwszej <math>p</math> jest bardziej precyzyjna, to podajemy, że twierdzenie jest z pewnością prawdziwe dla <math>n \geqslant 2 k (k + \tfrac{1}{2})</math>.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Przykład A43</span><br/>
| |
| − | Jeżeli <math>n \geqslant 8</math> i liczba pierwsza <math>p \in \left( \frac{2 n}{5}, \frac{n}{2} \right]</math>, to <math>p</math> nie występuje w rozwinięciu liczby <math>\binom{2 n}{n}</math> na czynniki pierwsze.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Dowód|Hide=Ukryj dowód}}
| |
| − | <span style="border-bottom-style: double;">Dowód na podstawie analizy krotności pojawiania się liczby <math>p</math></span><br/><br/>
| |
| − | Zapiszmy współczynnik dwumianowy <math>\binom{2 n}{n}</math> w postaci ułamka
| |
| − |
| |
| − | ::<math>\binom{2 n}{n} = \frac{(2 n) !}{(n!)^2} = \frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | Rozważmy dowolną liczbę pierwszą <math>p</math> występującą w mianowniku wypisanego wyżej ułamka. Potrzebujemy, aby <math>p</math> spełniała następujące warunki:
| |
| − |
| |
| − | * <math>2 p \leqslant n</math> — warunek ten zapewnia nam, że liczba <math>p</math> pojawi się co najmniej dwa razy w mianowniku
| |
| − | * <math>3 p > n</math> — warunek ten zapewnia nam, że liczba <math>p</math> pojawi się dokładnie dwa razy w mianowniku (jako <math>p</math> i <math>2 p</math>)
| |
| − | * <math>4 p \leqslant 2 n</math> — warunek ten (łącznie z warunkiem <math>3 p > n</math>) zapewnia nam, że liczba <math>p</math> pojawi się co najmniej dwa razy w liczniku
| |
| − | * <math>5 p > 2 n</math> — warunek ten (łącznie z warunkiem <math>4 p \leqslant 2 n</math>) zapewnia nam, że liczba <math>p</math> pojawi się dokładnie dwa razy w liczniku (jako <math>3 p</math> i <math>4 p</math>)
| |
| − |
| |
| − | Łącząc otrzymane warunki, otrzymujemy, że liczba pierwsza <math>p \in \left( \tfrac{2 n}{5}, \tfrac{n}{2} \right]</math> pojawia się dokładnie dwa razy w mianowniku i dokładnie dwa razy w liczniku ułamka
| |
| − |
| |
| − | ::<math>\frac{(n + 1) \cdot (n + 2) \cdot \ldots \cdot (2 n - 1) \cdot 2 n}{1 \cdot 2 \cdot \ldots \cdot (n - 1) \cdot n}</math>
| |
| − |
| |
| − | Zatem nie występuje w rozwinięciu współczynnika dwumianowego <math>\binom{2 n}{n}</math> na czynniki pierwsze.
| |
| − |
| |
| − | Wielokrotności liczby <math>p</math> podnoszą wykładniki, z jakimi występują liczby pierwsze <math>2</math> i <math>3</math>. Dlatego zakładamy, że <math>n \geqslant 8</math>, bo dla <math>n \geqslant 8</math> liczby pierwsze <math>2, 3</math> nie spełniają warunku <math>p \in \left( \tfrac{2 n}{5}, \tfrac{n}{2} \right]</math>.
| |
| − |
| |
| − | Bezpośrednio sprawdzamy, że twierdzenie nie jest prawdziwe dla <math>n = 7</math> i liczba <math>3</math> dzieli liczbę <math>\binom{14}{7} = 3432</math>
| |
| − |
| |
| − |
| |
| − | <span style="border-bottom-style: double;">Dowód na podstawie twierdzenia A24</span><br/><br/>
| |
| − | Rozważmy najpierw pierwszy składnik sumy
| |
| − |
| |
| − | ::<math>\sum^{\infty}_{k = 1} \left ( \left \lfloor \frac{2 n}{p^{k}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{k}} \right \rfloor \right )</math>
| |
| − |
| |
| − | Ponieważ przypuszczamy, że składnik ten będzie równy <math>0</math>, to będziemy szukali oszacowania od góry. Z założenia mamy
| |
| − |
| |
| − | ::1) <math>p > \frac{2 n}{5} \quad \implies \quad \frac{2 n}{p} < 5 \quad \implies \quad \left\lfloor \frac{2 n}{p} \right\rfloor \leqslant 4</math>
| |
| − |
| |
| − | ::2) <math>p \leqslant \frac{n}{2} \quad \implies \quad \frac{n}{p} \geqslant 2 \quad \implies \quad \left\lfloor \frac{n}{p} \right\rfloor \geqslant 2</math>
| |
| − |
| |
| − | Zatem
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{2 n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor \leqslant 4 - 4 = 0</math>
| |
| − |
| |
| − | Ponieważ każdy ze składników szukanej sumy może być równy tylko <math>0</math> lub <math>1</math>, to otrzymujemy
| |
| − |
| |
| − | ::<math>\left\lfloor \frac{2 n}{p} \right\rfloor - 2 \left\lfloor \frac{n}{p} \right\rfloor = 0</math>
| |
| − |
| |
| − |
| |
| − | Założenie, że <math>n \geqslant 13</math> pozwoli uprościć obliczenia dla drugiego i następnych składników sumy
| |
| − |
| |
| − | ::<math>p > \frac{2 n}{5} \quad \implies \quad \frac{(2 n)^k}{p^k} < 5^k \quad \implies \quad \frac{2 n}{p^k} < \frac{25}{2 n} \cdot \left( \frac{5}{2 n} \right)^{k - 2} \quad \implies \quad \frac{2 n}{p^k} \leqslant \frac{25}{2 n} \quad \implies \quad \frac{2 n}{p^k} \leqslant \frac{25}{26} \quad \implies \quad \left\lfloor \frac{2 n}{p^k} \right\rfloor = 0</math>
| |
| − |
| |
| − | Jeżeli <math>\left\lfloor \frac{2 n}{p^k} \right\rfloor = 0</math>, to również musi być <math>\left\lfloor \frac{n}{p^k} \right\rfloor = 0</math>. Pokazaliśmy, że dla <math>n \geqslant 13</math> jest
| |
| − |
| |
| − | ::<math>\sum^{\infty}_{k = 1} \left ( \left \lfloor \frac{2 n}{p^{k}} \right \rfloor - 2 \left \lfloor \frac{n}{p^{k}} \right \rfloor \right ) = 0</math>
| |
| − |
| |
| − | Dla <math>n = 8, 9</math> żadna liczba pierwsza nie należy do <math>\left( \tfrac{2 n}{5}, \tfrac{n}{2} \right]</math>.
| |
| − |
| |
| − | Dla <math>n = 10, 11, 12</math> łatwo sprawdzamy, że liczba <math>5</math> nie dzieli liczb <math>\binom{20}{10} = 184756</math>, <math>\binom{22}{11} = 705432</math> oraz <math>\binom{24}{12} = 2704156</math>.
| |
| − |
| |
| − | Zatem dla <math>n \geqslant 8</math> liczba pierwsza <math>p \in \left( \tfrac{2 n}{5}, \tfrac{n}{2} \right]</math> nie dzieli liczby <math>\binom{2 n}{n}</math>.<br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Uwaga A44</span><br/>
| |
| − | Z przykładu A41 nie wynika, że w przedziale <math>\left( \frac{n}{2}, \frac{2 n}{3} \right]</math> znajduje się choćby jedna liczba pierwsza <math>p</math>. Analogiczna uwaga jest prawdziwa w przypadku przykładu A43 oraz twierdzeń A40 i A42. Istnienie liczby pierwszej w określonym przedziale będzie tematem kolejnego artykułu.
| |
| − |
| |
| − |
| |
| − |
| |
| − | <span style="font-size: 110%; font-weight: bold;">Przykład A45</span><br/>
| |
| − | Pokazujemy i omawiamy wynik zastosowania twierdzeń A40 i A42 do współczynnika dwumianowego <math>\binom{2 \cdot 3284}{3284}</math>. Można udowodnić, że granicę stosowalności obu twierdzeń bardzo dokładnie opisuje warunek <math>p > \sqrt{2 n}</math>, co w naszym przypadku daje <math>p > \sqrt{2 \cdot 3284} \approx 81.04</math>.
| |
| − |
| |
| − | {{Spoiler|Style = font-style: italic; font-weight: bold; color: olive; text-decoration: underline;|Show=Pokaż przykład|Hide=Ukryj przykład}}
| |
| − | Wybraliśmy współczynnik dwumianowy <math>\binom{2 \cdot 3284}{3284}</math> dlatego, że w rozkładzie tego współczynnika na czynniki pierwsze występują wszystkie liczby pierwsze <math>p \leqslant 107</math>, co ułatwia analizowanie występowania liczb pierwszych. Tylko sześć liczb pierwszych: 2, 3, 59, 61, 73, 79 występuje z wykładnikiem większym niż jeden. Ponieważ <math>\sqrt{2 \cdot 3284} \approx 81.043</math>, zatem liczba 79 jest ostatnią liczbą pierwszą, która mogłaby wystąpić z wykładnikiem większym niż jeden i tak właśnie jest.<br/>
| |
| − |
| |
| − | Poniżej wypisaliśmy wszystkie liczby pierwsze <math>p \leqslant 3284</math>, które występują w rozwinięciu współczynnika dwumianowego <math>\binom{2 \cdot 3284}{3284}</math> na czynniki pierwsze. Pogrubienie oznacza, że dana liczba rozpoczyna nowy wiersz w tabeli. Ostatnią pogrubioną i dodatkowo podkreśloną liczbą jest liczba 107, bo wszystkie liczby pierwsze mniejsze od 107 powinny pojawić się w tabeli – oczywiście tak się nie stanie, bo twierdzeń A40 i A42 nie można stosować bez ograniczeń dla coraz większych liczb <math>k</math>.
| |
| − |
| |
| − |
| |
| − | 2<sup>6</sup>, 3<sup>8</sup>, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59<sup>2</sup>, 61<sup>2</sup>, 67, 71, 73<sup>2</sup>, 79<sup>2</sup>, 83, 89, 97, 101, 103, <span style="border-bottom-style: double;">'''107'''</span>, '''127''', '''137''', 139, '''151''', '''157''', '''167''', '''173''', '''197''', 199, '''211''', '''223''', '''239''', 241, '''257''', '''277''', 281, 283, '''307''', 311, '''331''', 337, '''367''', 373, 379, 383, '''419''', 421, 431, 433, '''479''', 487, 491, 499, 503, '''557''', 563, 569, 571, 577, 587, 593, '''659''', 661, 673, 677, 683, 691, 701, 709, 719, 727, '''823''', 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, '''1097''', 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301, 1303, 1307, '''1657''', 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161, 2179
| |
| − |
| |
| − |
| |
| − |
| |
| − | Liczba 821 została pogrubiona (w tabeli), bo jest liczbą pierwszą i wyznacza początek przedziału otwartego, konsekwentnie liczba 821 nie występuje w rozkładzie współczynnika dwumianowego <math>\binom{2 \cdot 3284}{3284}</math> na czynniki pierwsze.<br/>
| |
| − |
| |
| − | Czytelnik łatwo sprawdzi, że największą wartością liczby <math>k</math>, dla jakiej można jeszcze stosować twierdzenie A40, jest <math>k = 39</math>. Podobnie największą wartością liczby <math>k</math>, dla jakiej można jeszcze stosować twierdzenie A42, jest <math>k = 40</math>. Wartości te i odpowiadające im przedziały zostały pogrubione, aby uwidocznić granicę stosowania tych twierdzeń. Łatwo odczytujemy, że twierdzenia A40 i A42 można stosować dla liczb pierwszych <math>p</math> spełniających warunek <math>p > 81.09</math>. Co bardzo dokładnie pokrywa się z warunkiem <math>p > \sqrt{2 \cdot 3284} \approx 81.04</math><br/>
| |
| − |
| |
| − | Liczba 73 jest ostatnią poprawnie pokazaną liczbą pierwszą. Po niej nie pojawiają się liczby pierwsze 71 i 67, które występują w rozwinięciu współczynnika dwumianowego <math>\binom{2 \cdot 3284}{3284}</math> na czynniki pierwsze.<br/>
| |
| − |
| |
| − | {| class="wikitable" style="font-size: 90%; text-align: center; margin: 1em auto 1em auto;"
| |
| − | ! <math>k</math>||<math>\frac{3284}{k+1}</math>||<math>p \in \left ( \frac{3284}{k + 1}, \frac{3284}{k + \tfrac{1}{2}} \right ]</math>||<math>\frac{3284}{k+\tfrac{1}{2}}</math>||<math>\frac{3284}{k}</math>
| |
| − | |-
| |
| − | | 0||3284||{3299, 3301, ..., 6553, 6563}||6568||
| |
| − | |-
| |
| − | | 1||1642||{1657, 1663, ..., 2161, 2179}||2189,33||3284
| |
| − | |-
| |
| − | | 2||1094,67||{1097, 1103, ..., 1303, 1307}||1313,60||1642
| |
| − | |-
| |
| − | | 3||'''821'''||{823, 827, ..., 929, 937}||938,29||1094,67
| |
| − | |-
| |
| − | | 4||656,80||{659, 661, 673, 677, 683, 691, 701, 709, 719, 727}||729,78||821
| |
| − | |-
| |
| − | | 5||547,33||{557, 563, 569, 571, 577, 587, 593}||597,09||656,80
| |
| − | |-
| |
| − | | 6||469,14||{479, 487, 491, 499, 503}||505,23||547,33
| |
| − | |-
| |
| − | | 7||410,50||{419, 421, 431, 433}||437,87||469,14
| |
| − | |-
| |
| − | | 8||364,89||{367, 373, 379, 383}||386,35||410,50
| |
| − | |-
| |
| − | | 9||328,40||{331, 337}||345,68||364,89
| |
| − | |-
| |
| − | | 10||298,55||{307, 311}||312,76||328,40
| |
| − | |-
| |
| − | | 11||273,67||{277, 281, 283}||285,57||298,55
| |
| − | |-
| |
| − | | 12||252,62||{257}||262,72||273,67
| |
| − | |-
| |
| − | | 13||234,57||{239, 241}||243,26||252,62
| |
| − | |-
| |
| − | | 14||218,93||{223}||226,48||234,57
| |
| − | |-
| |
| − | | 15||205,25||{211}||211,87||218,93
| |
| − | |-
| |
| − | | 16||193,18||{197, 199}||199,03||205,25
| |
| − | |-
| |
| − | | 17||182,44||{}||187,66||193,18
| |
| − | |-
| |
| − | | 18||172,84||{173}||177,51||182,44
| |
| − | |-
| |
| − | | 19||164,20||{167}||168,41||172,84
| |
| − | |-
| |
| − | | 20||156,38||{157}||160,20||164,20
| |
| − | |-
| |
| − | | 21||149,27||{151}||152,74||156,38
| |
| − | |-
| |
| − | | 22||142,78||{}||145,96||149,27
| |
| − | |-
| |
| − | | 23||136,83||{137, 139}||139,74||142,78
| |
| − | |-
| |
| − | | 24||131,36||{}||134,04||136,83
| |
| − | |-
| |
| − | | 25||126,31||{127}||128,78||131,36
| |
| − | |-
| |
| − | | 26||121,63||{}||123,92||126,31
| |
| − | |-
| |
| − | | 27||117,29||{}||119,42||121,63
| |
| − | |-
| |
| − | | 28||113,24||{}||115,23||117,29
| |
| − | |-
| |
| − | | 29||109,47||{}||111,32||113,24
| |
| − | |-
| |
| − | | 30||105,94||{<span style="border-bottom-style: double;">'''107'''</span>}||107,67||109,47
| |
| − | |-
| |
| − | | 31||102,63||{103}||104,25||105,94
| |
| − | |-
| |
| − | | 32||99,52||{101}||101,05||102,63
| |
| − | |-
| |
| − | | 33||96,59||{97}||98,03||99,52
| |
| − | |-
| |
| − | | 34||93,83||{}||95,19||96,59
| |
| − | |-
| |
| − | | 35||91,22||{}||92,51||93,83
| |
| − | |-
| |
| − | | 36||88,76||{89}||89,97||91,22
| |
| − | |-
| |
| − | | 37||86,42||{}||87,57||88,76
| |
| − | |-
| |
| − | | 38||84,21||{}||85,30||86,42
| |
| − | |-
| |
| − | | '''39'''||'''82,10'''||{83}||'''83,14'''||84,21
| |
| − | |-
| |
| − | | '''40'''||80,10||{}||'''81,09'''||'''82,10'''
| |
| − | |-
| |
| − | | 41||78,19||{79}||79,13||80,10
| |
| − | |-
| |
| − | | 42||76,37||{}||77,27||78,19
| |
| − | |-
| |
| − | | 43||74,64||{}||75,49||76,37
| |
| − | |-
| |
| − | | 44||72,98||{'''73'''}||73,80||74,64
| |
| − | |-
| |
| − | | 45||71,39||{}||72,18||72,98
| |
| − | |-
| |
| − | | 46||69,87||{}||70,62||71,39
| |
| − | |-
| |
| − | | 47||68,42||{}||69,14||69,87
| |
| − | |-
| |
| − | | 48||67,02||{}||67,71||68,42
| |
| − | |-
| |
| − | | 49||65,68||{}||66,34||67,02
| |
| − | |-
| |
| − | | 50||64,39||{}||65,03||65,68
| |
| − | |-
| |
| − | | 51||63,15||{}||63,77||64,39
| |
| − | |-
| |
| − | | 52||61,96||{}||62,55||63,15
| |
| − | |-
| |
| − | | 53||60,81||{61}||61,38||61,96
| |
| − | |-
| |
| − | | 54||59,71||{}||60,26||60,81
| |
| − | |-
| |
| − | | 55||58,64||{59}||59,17||59,71
| |
| − | |-
| |
| − | | 56||57,61||{}||58,12||58,64
| |
| − | |-
| |
| − | | 57||56,62||{}||57,11||57,61
| |
| − | |-
| |
| − | | 58||55,66||{}||56,14||56,62
| |
| − | |-
| |
| − | | 59||54,73||{}||55,19||55,66
| |
| − | |-
| |
| − | | 60||53,84||{}||54,28||54,73
| |
| − | |-
| |
| − | | 61||52,97||{53}||53,40||53,84
| |
| − | |-
| |
| − | | 62||52,13||{}||52,54||52,97
| |
| − | |-
| |
| − | | 63||51,31||{}||51,72||52,13
| |
| − | |-
| |
| − | | 64||50,52||{}||50,91||51,31
| |
| − | |-
| |
| − | | 65||49,76||{}||50,14||50,52
| |
| − | |-
| |
| − | | 66||49,01||{}||49,38||49,76
| |
| − | |-
| |
| − | | 67||48,29||{}||48,65||49,01
| |
| − | |-
| |
| − | | 68||47,59||{}||47,94||48,29
| |
| − | |-
| |
| − | | 69||46,91||{47}||47,25||47,59
| |
| − | |-
| |
| − | | 70||46,25||{}||46,58||46,91
| |
| − | |}
| |
| − | <br/>
| |
| − | □
| |
| − | {{\Spoiler}}
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − | == Przypisy ==
| |
| − |
| |
| − | <references>
| |
| − |
| |
| − | <ref name="PARIGP">Wikipedia, ''PARI/GP'', ([https://en.wikipedia.org/wiki/PARI/GP Wiki-en])</ref>
| |
| − |
| |
| − | <ref name="Czebyszew1">Wikipedia, ''Pafnuty Czebyszew (1821 - 1893)'', ([https://pl.wikipedia.org/wiki/Pafnutij_Czebyszow Wiki-pl]), ([https://ru.wikipedia.org/wiki/%D0%A7%D0%B5%D0%B1%D1%8B%D1%88%D1%91%D0%B2,_%D0%9F%D0%B0%D1%84%D0%BD%D1%83%D1%82%D0%B8%D0%B9_%D0%9B%D1%8C%D0%B2%D0%BE%D0%B2%D0%B8%D1%87 Wiki-ru])</ref>
| |
| − |
| |
| − | <ref name="Czebyszew2">P. L. Chebyshev, ''Mémoire sur les nombres premiers'', J. de Math. Pures Appl. (1) 17 (1852), 366-390, ([http://sites.mathdoc.fr/JMPA/PDF/JMPA_1852_1_17_A19_0.pdf LINK])</ref>
| |
| − |
| |
| − | <ref name="Erdos">P. Erdos, ''Beweis eines Satzes von Tschebyschef'', Acta Litt. Sci. Szeged 5 (1932), 194-198, ([https://old.renyi.hu/~p_erdos/1932-01.pdf LINK1]), ([http://acta.bibl.u-szeged.hu/13396/1/math_005_194-198.pdf LINK2])</ref>
| |
| − |
| |
| − | <ref name="Dusart99">P. Dusart, ''The <math>k^{th}</math> prime is greater than <math>k (\ln k + \ln \ln k - 1)</math> for <math>k \geqslant 2</math>'', Math. Of Computation, Vol. 68, Number 225 (January 1999), pp. 411-415.</ref>
| |
| − |
| |
| − | <ref name="Dusart06">P. Dusart, ''Sharper bounds for <math>\psi</math>, <math>\theta</math>, <math>\pi</math>, <math>p_k</math>'', Rapport de recherche no. 1998-06, Université de Limoges, ([http://www.unilim.fr/laco/rapports/1998/R1998_06.pdf LINK])</ref>
| |
| − |
| |
| − | <ref name="Dusart10">P. Dusart, ''Estimates of some functions over primes without R.H.'', (2010), ([https://arxiv.org/abs/1002.0442 LINK])</ref>
| |
| − |
| |
| − | <ref name="Dusart18">P. Dusart, ''Explicit estimates of some functions over primes'', Ramanujan Journal. 45 (1) (January 2018) pp. 225-234.</ref>
| |
| − |
| |
| − | <ref name="p1">Wikipedia, ''Twierdzenie o zbieżności ciągu monotonicznego'', ([https://pl.wikipedia.org/wiki/Twierdzenie\_o\_zbie\%C5\%BCno\%C5\%9Bci\_ci\%C4\%85gu\_monotonicznego LINK])</ref>
| |
| − |
| |
| − | </references>
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
| − |
| |
