Twierdzenie Czebyszewa o funkcji π(n)

07.11.2021

Oznaczenia

Będziemy stosowali następujące oznaczenia:

$\mathbb{Z}$ — zbiór liczb całkowitych

${\mathbb{Z}}_{+}$ — zbiór liczb całkowitych dodatnich

$\mathbb{N}$ — zbiór liczb naturalnych $\mathbb{N}={\mathbb{Z}}_{+}$

${\mathbb{N}}_0$ — zbiór liczb całkowitych nieujemnych ${\mathbb{N}}_0={\mathbb{Z}}_{+}\cup \left\{0\right\}$

$\mathbb{R}$ — zbiór liczb rzeczywistych

$d\mid n$ — czytaj: d dzieli n ($d$ jest dzielnikiem liczby $n$)

$d\nmid n$ — czytaj: d nie dzieli n ($d$ nie jest dzielnikiem liczby $n$)

$p_n$ — $n$-ta liczba pierwsza

$\pi (n)$ — ilość liczb pierwszych nie większych od $n$

$P(n)$ — iloczyn liczb pierwszych nie większych od $n$

$\lfloor x\rfloor$ — największa liczba całkowita nie większa od $x$

$(\genfrac{}{}{0ex}{}{n}{m})$ — współczynnik dwumianowy (symbol Newtona), $(\genfrac{}{}{0ex}{}{n}{m})=\frac{n!}{m!\cdot (n-m)!}$

$\log (x)$ — logarytm naturalny liczby $x>0$

$W_p(n)$ — wykładnik z jakim liczba pierwsza $p$ wchodzi do rozwinięcia na czynniki pierwsze liczby $n$

$n$ — oznacza zawsze liczbę naturalną

$p$ — oznacza zawsze liczbę pierwszą

Przykładowe wartości niektórych wypisanych wyżej funkcji:

$p_2=3$,   $p_{10}=29$,   $p_{100}=541$

$\pi (10)=4$,   $\pi (100)=25$,   $\pi (541)=100$

$P(5)=30$,   $P(10)=210$,   $P(50)=614889782588491410$

$\lfloor 1.2\rfloor =1$,   $\lfloor 2.8\rfloor =2$,   $\lfloor -1.5\rfloor =-2$

$(\genfrac{}{}{0ex}{}{5}{2})=10$,   $(\genfrac{}{}{0ex}{}{10}{5})=252$,   $(\genfrac{}{}{0ex}{}{9}{3})=84$

$W_2(8)=3$,   $W_3(18)=2$,   $W_7(28)=1$

Funkcje te są zaimplementowane w PARI/GP

$p_n$ = prime(n)

$\pi (n)$ = primepi(n)

$P(n)$ = prodeuler(p=2, n, p)

$\lfloor x\rfloor$ = floor(x)

$(\genfrac{}{}{0ex}{}{n}{m})$ = binomial(n, m)

$W_p(n)$ = valuation(n, p)

Twierdzenie Czebyszewa

W 1852 roku rosyjski matematyk Czebyszew udowodnił, że dla funkcji $\pi (n)$ prawdziwe jest następujące oszacowanie

$a\cdot \frac{n}{\log n}\underset{n⩾11}{<}\pi (n)\underset{n⩾96098}{<}b\cdot \frac{n}{\log n}$

gdzie

$a=\log (2^{1/2}\cdot 3^{1/3}\cdot 5^{1/5}\cdot {30}^{-1/30})=0.921292022b=\frac{6}{5}a=1.105550428$

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 $\pi (n)$”

Twierdzenie Czebyszewa o funkcji $\pi (n)$ nabrało nowego życia, gdy w 1936 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 funkcji $\pi (n)$ oraz $p_n$

$\frac{n}{\log n}(1+\frac{1}{\log n})\underset{n⩾599}{<}\pi (n)\underset{n⩾2}{<}\frac{n}{\log n}(1+\frac{1.28}{\log n})$

$n(\log n+\log \log n-1)\underset{n⩾2}{<}{p}_n\underset{n⩾6}{<}n(\log n+\log \log n)$

Przedstawimy tutaj elementarny dowód twierdzenia Czebyszewa o funkcji $\pi (n)$ oraz analogiczne oszacowanie dla funkcji $p_n$.

Twierdzenie A1
Prawdziwe są następujące oszacowania:

$0.72\cdot n\log n\underset{n⩾1}{<}{p}_n\underset{n⩾3}{<}2n\log n$

$\frac{2}{3}\cdot \frac{n}{\log n}\underset{n⩾3}{<}\pi (n)\underset{n⩾2}{<}\frac{2n}{\log n}$

Dowód powyższego twierdzenia jest łatwy, ale wymaga udowodnienia kolejno wielu, przeważnie bardzo prostych, twierdzeń pomocniczych.

Oszacowanie $p_n$ od dołu i $\pi (n)$ od góry

Rozpoczniemy od oszacowania liczby $(\genfrac{}{}{0ex}{}{2n}{n})$. Badanie właściwości tego współczynnika dwumianowego jest kluczowe dla naszego dowodu.

Twierdzenie A2
Niech $n,k\in \mathbb{N}$. Współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{n}{k})$ jest zawsze liczbą całkowitą dodatnią.

Dowód

Indukcja matematyczna. Ponieważ

$(\genfrac{}{}{0ex}{}{0}{0})=(\genfrac{}{}{0ex}{}{1}{0})=(\genfrac{}{}{0ex}{}{1}{1})=1$

to twierdzenie jest prawdziwe dla $n=1$. Zakładając prawdziwość twierdzenia dla wszystkich liczb całkowitych należących do przedziału $[1,n]$ mamy dla $n+1$

$(\genfrac{}{}{0ex}{}{n+1}{0})=(\genfrac{}{}{0ex}{}{n+1}{n+1})=1$

Dla $k$ spełniającego warunek $1⩽k⩽n$, jest

$(\genfrac{}{}{0ex}{}{n+1}{k})=(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k-1})$

Na podstawie założenia indukcyjnego liczby po prawej stronie są liczbami całkowitymi dodatnimi, zatem $(\genfrac{}{}{0ex}{}{n+1}{k})$ dla wszystkich wartości $k$ jest liczbą całkowitą dodatnią. Co należało pokazać.
□

Twierdzenie A3
Niech $n\in {\mathbb{Z}}_{+}$. Współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2n}{n})$ jest liczbą parzystą.

Dowód

Łatwo zauważamy, że

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{n!\cdot n!}=\frac{2n\cdot (2n-1)!}{n\cdot (n-1)!\cdot n!}=2\cdot (\genfrac{}{}{0ex}{}{2n-1}{n-1})$

□

Twierdzenie A4
Prawdziwe są następujące oszacowania współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$

${3.8}^{n+1}\underset{n⩾80}{<}(\genfrac{}{}{0ex}{}{2n}{n})\underset{n⩾5}{<}{4}^{n-1}$

Dowód

Indukcja matematyczna. W przypadku lewej nierówności łatwo sprawdzamy, że ${3.8}^{81}<(\genfrac{}{}{0ex}{}{160}{80})$. Zakładając prawdziwość nierówności dla $n⩾80$, otrzymujemy dla $n+1$

$(\genfrac{}{}{0ex}{}{2(n+1)}{n+1})=(\genfrac{}{}{0ex}{}{2n}{n})\cdot \frac{(2n+2)(2n+1)}{(n+1)(n+1)}>{3.8}^{n+1}\cdot 2\cdot (2-\frac{1}{n+1})⩾{3.8}^{n+1}\cdot 2\cdot (2-\frac{1}{80+1})>{3.8}^{n+1}\cdot 3.9753>{3.8}^{n+2}$

Prawa nierówność jest prawdziwa dla $n=5$. Zakładając prawdziwość nierówności dla $n$, otrzymujemy dla $n+1$:

$(\genfrac{}{}{0ex}{}{2(n+1)}{n+1})=(\genfrac{}{}{0ex}{}{2n}{n})\cdot \frac{(2n+2)(2n+1)}{(n+1)(n+1)}<4^{n-1}\cdot 2\cdot (2-\frac{1}{n+1})<4^n$

□

Twierdzenie A5
Dla $n⩾12$ prawdziwe jest oszacowanie $p_n>3n$.

Dowód

Indukcja matematyczna. Dowód oprzemy na spostrzeżeniu, że wśród kolejnych sześciu liczb naturalnych $6k,6k+1,6k+2,6k+3,6k+4,6k+5$ jedynie dwie: $6k+1$ i $6k+5$ mogą być pierwsze. Wynika stąd, że $p_{n+2}⩾p_n+6$ dla $n⩾4$. Dowód indukcyjny przeprowadzimy, stosując krok równy $2$. Twierdzenie jest oczywiście prawdziwe dla $n=12$, bowiem $p_{12}=37>3\cdot 12=36$, podobnie $p_{13}=41>3\cdot 13=39$. Zakładając prawdziwość twierdzenia dla wszystkich liczb naturalnych $k\in [12,n]$, otrzymujemy dla $n+2$:

$p_{n+2}⩾p_n+6>3n+6=3\cdot (n+2)$

Uwaga: inaczej mówiąc, dowodzimy twierdzenie osobno dla $n$ parzystych $(n⩾12)$ i osobno dla $n$ nieparzystych $(n⩾13)$.
□

Twierdzenie A6
Ciąg $a_n={(1+\frac{1}{n})}^n$ jest rosnący i ograniczony. Dla wyrazów ciągu $(a_n)$ prawdziwe jest oszacowanie $2⩽a_n<3$.

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

${(x+y)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^{n-k}{y}^k=(\genfrac{}{}{0ex}{}{n}{0})x^n+(\genfrac{}{}{0ex}{}{n}{1})x^{n-1}y+(\genfrac{}{}{0ex}{}{n}{2})x^{n-2}{y}^2+\dots +(\genfrac{}{}{0ex}{}{n}{n})y^n$

gdzie $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!\cdot (n-k)!}$.

Dowód opiera się na spostrzeżeniu, że $e=\sum _{k=0}^{\mathrm{\infty }}\frac{1}{k!}=2.718281828\dots$, a wykorzystanie wzoru dwumianowego pozwala przekształcić wyrażenie ${(1+\frac{1}{n})}^n$ do postaci sumy z wyraźnie wydzielonym czynnikiem $\frac{1}{k!}$. Stosując wzór dwumianowy, możemy zapisać $n$-ty wyraz ciągu $(a_n)$ w postaci

$a_n={(1+\frac{1}{n})}^n=$

$=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})\frac{1}{n^k}=$

$=2+\sum _{k=2}^n\frac{n!}{k!\cdot (n-k)!}\cdot \frac{1}{n^k}=$

$=2+\sum _{k=2}^n\frac{1}{k!}\cdot \frac{n\cdot (n-1)\cdot \dots \cdot (n-(k-1))}{n^k}=$

$=2+\sum _{k=2}^n\frac{1}{k!}\cdot (1-\frac{1}{n})\cdot \dots \cdot (1-\frac{k-1}{n})$

Odpowiednio dla wyrazu $a_{n+1}$ mamy

$a_{n+1}={(1+\frac{1}{n+1})}^{n+1}=$

$=2+\sum _{k=2}^{n+1}\frac{1}{k!}\cdot (1-\frac{1}{n+1})\cdot \dots \cdot (1-\frac{k-1}{n+1})>$

$>2+\sum _{k=2}^n\frac{1}{k!}\cdot (1-\frac{1}{n+1})\cdot \dots \cdot (1-\frac{k-1}{n+1})>$

$>2+\sum _{k=2}^n\frac{1}{k!}\cdot (1-\frac{1}{n})\cdot \dots \cdot (1-\frac{k-1}{n})=$

$=a_n$

Ostatnia nierówność jest prawdziwa, bo dla dowolnej liczby $x\in {\mathbb{R}}_{+}$ jest $1-\frac{x}{n+1}>1-\frac{x}{n}$

Zatem ciąg $(a_n)$ jest rosnący. Musimy jeszcze wykazać, że jest ograniczony od góry. Pokazaliśmy wyżej, że wyraz $a_n$ może być zapisany w postaci

$a_n=2+\sum _{k=2}^n\frac{1}{k!}\cdot (1-\frac{1}{n})\cdot \dots \cdot (1-\frac{k-1}{n})$

Ponieważ czynniki w nawiasach są dodatnie i mniejsze od jedności, to

$a_n⩽2+\sum _{k=2}^n\frac{1}{k!}=$

$⩽1+1+\sum _{k=2}^n\frac{1}{2^{k-1}}=$

$=1+(1+\frac{1}{2}+\frac{1}{2^2}+\dots +\frac{1}{2^{n-1}})=$

$=1+\frac{1-{\left(\frac{1}{2}\right)}^n}{1-\frac{1}{2}}=$

$=1+2-\frac{1}{2^{n-1}}<$

$<3$

Druga nierówność (nieostra) jest prawdziwa, bo dla $k⩾2$ zachodzi oczywista nierówność $k!⩾2^{k-1}$. Do sumy ujętej w nawiasy zastosowaliśmy wzór na sumę częściową szeregu geometrycznego.

Ponieważ $a_1=2$, to prawdziwe jest oszacowanie $2⩽a_n<3$. Zauważmy jeszcze (już bez dowodu), że ciąg $(a_n)$, jako rosnący i ograniczony od góry, jest zbieżny. Granicą ciągu $(a_n)$ jest liczba niewymierna $e=2.718281828\dots$, która jest podstawą logarytmu naturalnego.
□

Twierdzenie A7
Prawdziwe są następujące oszacowania:

$n^n\underset{n⩾13}{<}{p}_1{p}_2\cdot \dots \cdot p_n\underset{n⩾3}{<}(n\log n{)}^n$

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 $n=13$. Zakładając prawdziwość twierdzenia dla liczb naturalnych $k\in [13,n]$ mamy dla $n+1$:

$p_1{p}_2\cdot \dots \cdot p_n{p}_{n+1}>n^n\cdot p_{n+1}>n^n\cdot 3(n+1)>n^n\cdot {(1+\frac{1}{n})}^n\cdot (n+1)=(n+1{)}^{n+1}$

Gdzie skorzystaliśmy z faktu, że $p_n>3n$ dla $n⩾12$ oraz z właściwości rosnącego ciągu $a_n={(1+\frac{1}{n})}^n<e=2.718281828\dots <3$ (zobacz twierdzenie A6).
□

Twierdzenie A8
Dla $n⩾2$ prawdziwe jest oszacowanie $\frac{P(2n)}{P(n)}<4^{n-1}$, gdzie $P(n)$ oznacza iloczyn wszystkich liczb pierwszych nie większych od $n$.

Dowód

Rozważmy współczynnik dwumianowy

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{n!\cdot n!}=\frac{2n\cdot (2n-1)\cdot \dots \cdot (n+1)}{n!}$

Każda liczba pierwsza należąca do przedziału $[n+1,2n]$ występuje w liczniku wypisanego wyżej ułamka i nie występuje w mianowniku. Wynika stąd oszacowanie

$(\genfrac{}{}{0ex}{}{2n}{n})=C\cdot \underset{n+1⩽p_k⩽2n}{\prod p_k}>\underset{n+1⩽p_k⩽2n}{\prod p_k}=\frac{P(2n)}{P(n)}$

Zauważmy, że wypisany w powyższej nierówności iloczyn liczb pierwszych jest liczbą nieparzystą. Ponieważ współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2n}{n})$ jest dodatnią liczbą całkowitą parzystą, zatem również czynnik $C⩾2$ musi być dodatnią liczbą całkowitą parzystą. Łącząc uzyskaną nierówność z oszacowaniem z twierdzenia A4, otrzymujemy natychmiast:

$\frac{P(2n)}{P(n)}<(\genfrac{}{}{0ex}{}{2n}{n})<4^{n-1}$

Dla $n=2,3,4$ sprawdzamy uzyskany rezultat bezpośrednio.
□

Twierdzenie A9
Dla $n⩾1$ prawdziwe jest oszacowanie $P(n)<4^n$

Dowód

Indukcja matematyczna. Oszacowanie $P(n)<4^n$ jest prawdziwe dla $n=1,2$. Zakładając prawdziwość oszacowania dla wszystkich liczb całkowitych nie większych od $n$, dla $n+1$ rozpatrzymy dwa przypadki. Jeżeli $n+1=2k+1$ jest liczbą nieparzystą większą lub równą $3$, to mamy

$P(n+1)=P(2k+1)=P(2k+2)=P(k+1)\cdot \frac{P(2k+2)}{P(k+1)}<4^{k+1}\cdot 4^k=4^{2k+1}=4^{n+1}$

gdzie skorzystaliśmy z założenia indukcyjnego i oszacowania z twierdzenia A8.

Jeżeli $n+1=2k$ jest liczbą parzystą większą lub równą $4$, to mamy

$P(n+1)=P(2k)=P(k)\cdot \frac{P(2k)}{P(k)}<4^k\cdot 4^{k-1}=4^{2k-1}<4^{2k}=4^{n+1}$

gdzie ponownie skorzystaliśmy z założenia indukcyjnego i oszacowania z twierdzenia A8.
□

Twierdzenie A10
Dla $n⩾1$ prawdziwe jest oszacowanie $p_n>\frac{1}{2\log 2}\cdot n\log n$.

Dowód

Ponieważ z definicji $P(p_n)=p_1{p}_2\cdot \dots \cdot p_n$, to korzystając z oszacowań uzyskanych w twierdzeniach A7 i A9 dostajemy dla $n⩾13$

$n^n<p_1{p}_2\cdot \dots \cdot p_n=P(p_n)<4^{p_n}$

Logarytmując obie strony nierówności, mamy

$n\log n<p_n\cdot \log 4$

Skąd natychmiast wynika dowodzone oszacowanie

$p_n>\frac{1}{2\log 2}\cdot n\log n>0.72\cdot n\log n$

Prawdziwość powyższej nierówności dla $n⩽12$ sprawdzamy bezpośrednio.
□

Twierdzenie A11
Dla $n⩾2$ prawdziwe jest oszacowanie $\pi (2n)-\pi (n)<2\log 2\cdot \frac{n}{\log n}$.

Dowód

Każda liczba pierwsza należąca do przedziału $[n+1,2n]$ jest dzielnikiem współczynnika dwumianowego

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{n!\cdot n!}=\frac{2n\cdot (2n-1)\cdot \dots \cdot (n+1)}{n!}$

bowiem dzieli licznik i nie dzieli mianownika. Ponieważ dla każdej z tych liczb jest $p>n$, to

$n^{\pi (2n)-\pi (n)}<\prod _{n<p_i⩽2n}{p}_i<(\genfrac{}{}{0ex}{}{2n}{n})<4^n$

Ostatnia nierówność wynika z twierdzenia A4. Logarytmując, dostajemy

$[\pi (2n)-\pi (n)]\cdot \log n<2n\cdot \log 2$

Czyli

$\pi (2n)-\pi (n)<2\log 2\cdot \frac{n}{\log n}$

□

Twierdzenie A12
Dla $n⩾2$ prawdziwe jest oszacowanie $\pi (n)<2\cdot \frac{n}{\log n}$.

Dowód

Indukcja matematyczna. Oszacowanie $\pi (n)<2\cdot \frac{n}{\log n}$ jest prawdziwe dla $2⩽n⩽62$, 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 $[2,n]$, otrzymujemy dla $n+1$

a) jeżeli $n+1$ jest liczbą parzystą, to:

$\pi (n+1)=\pi (n)=2\cdot \frac{n}{\log n}<2\cdot \frac{n+1}{\log (n+1)}$

Ostatnia nierówność wynika ze spostrzeżenia, że funkcja $\frac{x}{\log x}$ jest funkcją rosnącą dla $x>e\approx 2.71828$. Można też wykorzystać oszacowanie $\log (1+x)<x$ prawdziwe dla $x>0$.

b) jeżeli $n+1$ jest liczbą nieparzystą, to możemy położyć $n+1=2k+1$ i otrzymujemy:

$\pi (n+1)=\pi (2k+1)$

$=\pi (2k+2)$

$=\pi (k+1)+[\pi (2k+2)-\pi (k+1)]$

$<2\cdot \frac{k+1}{\log (k+1)}+2\log 2\cdot \frac{k+1}{\log (k+1)}$

$=(1+\log 2)\cdot \frac{2k+2}{\log (k+1)}$

$<[1.7\cdot \frac{2k+2}{\log (k+1)}\cdot \frac{\log (2k+1)}{2k+1}]\cdot \frac{2k+1}{\log (2k+1)}$

$=[1.7\cdot \frac{2k+2}{2k+1}\cdot \frac{\log (2k+2)}{\log (k+1)}]\cdot \frac{2k+1}{\log (2k+1)}$

$=[1.7\cdot (1+\frac{1}{2k+1})\cdot \frac{\log (k+1)+\log 2}{\log (k+1)}]\cdot \frac{2k+1}{\log (2k+1)}$

$=[1.7\cdot (1+\frac{1}{2k+1})\cdot (1+\frac{\log 2}{\log (k+1)})]\cdot \frac{2k+1}{\log (2k+1)}$

$<2\cdot \frac{2k+1}{\log (2k+1)}$

$=2\cdot \frac{n+1}{\log (n+1)}$

Ostatnia nierówność wynika z faktu, że czynnik w nawiasie kwadratowym maleje wraz ze wzrostem $k$ i dla $k=63$ osiąga wartość $1.9989\dots$
□

Wykładnik z jakim liczba pierwsza $p$ występuje w $n!$

Uzyskanie kolejnych oszacowań wymaga znalezienia wykładnika, z jakim liczba pierwsza $p$ wchodzi do rozwinięcia współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n!{)}^2}$.

Definicja A13
Funkcję $\lfloor x\rfloor$ (czytaj: całość z $x$) definiujemy jako największą liczbę całkowitą nie większą od $x$. Operacyjnie możemy ją zdefiniować następująco: niech liczby $x,\epsilon \in \mathbb{R}$, liczba $k\in \mathbb{Z}$ oraz $0⩽\epsilon <1$, jeżeli $x=k+\epsilon$, to $\lfloor x\rfloor =\lfloor k+\epsilon \rfloor =k$.

Twierdzenie A14
Dla $n\in {\mathbb{Z}}_{+}$, $x\in \mathbb{R}$ jest $\lfloor \frac{x}{n}\rfloor =\lfloor \frac{\lfloor x\rfloor }{n}\rfloor$.

Dowód

Korzystając z definicji A13, przedstawmy liczbę w postaci $x=k+\epsilon$, gdzie $0⩽\epsilon <1$.

Z twierdzenia o dzieleniu z resztą liczbę $k$ możemy zapisać w postaci $k=qn+r$, gdzie $0⩽r⩽n-1$, mamy zatem $x=qn+r+\epsilon$. Ponieważ $0⩽r+\epsilon <n$, to po podzieleniu przez $n$ dostajemy

$0⩽\frac{r+\epsilon }{n}<1$

czyli

$\lfloor \frac{x}{n}\rfloor =\lfloor \frac{qn+r+\epsilon }{n}\rfloor =\lfloor q+\frac{r+\epsilon }{n}\rfloor =q$

Podobnie, ponieważ $0⩽r<n$, to $0⩽\frac{r}{n}<1$ i otrzymujemy

$\lfloor \frac{\lfloor x\rfloor }{n}\rfloor =\lfloor \frac{\lfloor qn+r+\epsilon \rfloor }{n}\rfloor =\lfloor \frac{qn+r}{n}\rfloor =\lfloor q+\frac{r}{n}\rfloor =q$

□

Twierdzenie A15
Niech $x\in \mathbb{R}$. Liczba $\lfloor 2x\rfloor -2\lfloor x\rfloor$ przyjmuje wartości $0$ lub $1$.

Dowód

Niech $x=k+\epsilon$, gdzie $0⩽\epsilon <1$. Mamy

$\lfloor 2x\rfloor -2\lfloor x\rfloor =\lfloor 2k+2\epsilon \rfloor -2\lfloor k+\epsilon \rfloor =2k+\lfloor 2\epsilon \rfloor -2k-2\lfloor \epsilon \rfloor =\lfloor 2\epsilon \rfloor$

Ponieważ $0⩽2\epsilon <2$, zatem $\lfloor 2\epsilon \rfloor =0$ lub $\lfloor 2\epsilon \rfloor =1$.
□

Bardzo istotnym rezultatem (z punktu widzenia przyszłych obliczeń) będzie znalezienie wykładnika, z jakim liczba pierwsza $p$ występuje w iloczynie $1\cdot 2\cdot 3\cdot \dots \cdot n=n!$

Definicja A16
Niech $p$ będzie liczbą pierwszą, zaś $a$ dowolną liczbą naturalną. Jeżeli liczba pierwsza $p$ wchodzi do rozwinięcia liczby naturalnej $n⩾2$ na czynniki pierwsze z wykładnikiem $a$, to powiemy, że funkcja $W_p(n)$ przyjmuje wartość $a$. Fakt ten możemy zapisać następująco

$W_p(n)=a⟺p^a\mid n\text{i}{p}^{a+1}\nmid n$

Przykład A17
$W_5(100)=2$,   $W_7(42)=1$,   ponieważ $11!=2^8\cdot 3^4\cdot 5^2\cdot 7\cdot 11$, to $W_3(11!)=4$

Wprost z definicji funkcji $W_p(n)$ wynikają następujące właściwości:

Twierdzenie A18

Podstawowe własności funkcji $W_p(n)$

1. $W_p(n\cdot m)=W_p(n)+W_p(m)$
2. $W_p(n\cdot p^a)=a+W_p(n)$
3. $W_p\left(\frac{n}{m}\right)=W_p\left(n\right)-W_p\left(m\right)\text{o ile}\frac{n}{m}\in {\mathbb{Z}}_{+}$
4. $p\nmid n⟺W_p(n)=0$

Twierdzenie A19
Niech $p$ będzie liczbą pierwszą. Ilość liczb podzielnych przez $p$ i występujących w ciągu $1,2,3,\dots ,n$ wynosi $r=\lfloor \frac{n}{p}\rfloor$.

Dowód

Wśród liczb naturalnych $1,2,3,\dots ,n$ istnieje pewna ilość liczb podzielnych przez $p$. Liczby te możemy z łatwością wypisać, będą nimi

$1\cdot p,2\cdot p,3\cdot p,\dots ,r\cdot p$

Gdzie $r$ jest największą liczbą całkowitą nie większą niż $\frac{n}{p}$, czyli $r=\lfloor \frac{n}{p}\rfloor$.
□

Przykład A20
Ilość liczb całkowitych dodatnich podzielnych przez $5$ i nie większych od $63$ wynosi $\lfloor \frac{63}{5}\rfloor =12$. Liczby te to $5,10,15,20,25,30,35,40,45,50,55,60$.

Twierdzenie A19 umożliwi nam określenie wykładnika, z jakim liczba pierwsza $p$ występuje w $n!$

Twierdzenie A21
Liczba pierwsza $p$ występuje w iloczynie $n!$ z wykładnikiem $W_p(n!)=\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor$

Dowód

Dowód sprowadza się do znalezienia wartości funkcji $W_p(n!)$.

$W_p(n!)=W_p(1\cdot 2\cdot 3\cdot \dots \cdot n)=W_p(p\cdot 2p\cdot 3p\cdot \dots \cdot \lfloor \frac{n}{p}\rfloor \cdot p)$

Pozostawiliśmy jedynie czynniki podzielne przez $p$ (czynniki niepodzielne przez $p$ nie dają wkładu do wykładnika, z jakim $p$ występuje w $n!$), wyłączając czynnik $p$ z każdej z liczb $p,2p,3p,\dots ,\lfloor \frac{n}{p}\rfloor \cdot p$ mamy

$W_p(n!)=W_p(p^{\lfloor n/p\rfloor }\cdot 1\cdot 2\cdot 3\cdot \dots \cdot \lfloor \frac{n}{p}\rfloor )=\lfloor \frac{n}{p}\rfloor +W_p(1\cdot 2\cdot 3\cdot \dots \cdot \lfloor \frac{n}{p}\rfloor )$

Otrzymane wyrażenie przekształcamy analogicznie jak wyżej

$W_p(n!)=\lfloor \frac{n}{p}\rfloor +W_p(p\cdot 2p\cdot 3p\cdot \dots \cdot \lfloor \frac{\lfloor n/p\rfloor }{p}\rfloor \cdot p)$

Z twierdzenia A14 wiemy, że dla $x\in \mathbb{R}$ i $n\in {\mathbb{Z}}_{+}$ jest:

$\lfloor \frac{\lfloor x\rfloor }{n}\rfloor =\lfloor \frac{x}{n}\rfloor$

zatem

$W_p(n!)=\lfloor \frac{n}{p}\rfloor +W_p(p\cdot 2p\cdot 3p\cdot \dots \cdot \lfloor \frac{n}{p^2}\rfloor \cdot p)=$

$=\lfloor \frac{n}{p}\rfloor +W_p(p^{\lfloor n/p^2\rfloor }\cdot 1\cdot 2\cdot 3\cdot \dots \cdot \lfloor \frac{n}{p^2}\rfloor )=$

$=\lfloor \frac{n}{p}\rfloor +\lfloor \frac{n}{p^2}\rfloor +W_p(1\cdot 2\cdot 3\cdot \dots \cdot \lfloor \frac{n}{p^2}\rfloor )$

Oczywiście opisaną wyżej procedurę możemy powtarzać wielokrotnie. Zakończenie następuje wtedy, gdy wykładnik liczby pierwszej $p$ osiągnie wartość tak dużą, że $\lfloor \frac{n}{p^k}\rfloor =0$. Ponieważ nie wiemy, jaka to wartość (choć możemy ją oszacować), to stosujemy zapis

$W_p(n!)=\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor$

zdając sobie sprawę z tego, że w rzeczywistości sumowanie obejmuje jedynie skończoną liczbę składników.
□

Uwaga A22
Należy zauważyć, że liczba sumowań jest skończona, bowiem bardziej precyzyjnie możemy powyższy wzór zapisać w postaci

$W_p(n!)=\sum _{k=1}^B\lfloor \frac{n}{p^k}\rfloor$

gdzie $B=\lfloor {\log }_2(n)\rfloor$. Jest tak dlatego, że jeżeli $k$ przekroczy $\lfloor {\log }_2(n)\rfloor$, to dla liczby pierwszej $p=2$, jak również dla wszystkich innych liczb pierwszych mamy

$\frac{n}{p^k}<1$

czyli dla $k>B$ sumujemy same zera.

Przykład A23
Niech $n=30$, $p=3$

$W_3(30!)=W_3(1\cdot 2\cdot 3\cdot 4\cdot \dots \cdot 30)=$

$=W_3(3\cdot 6\cdot 9\cdot 12\cdot 15\cdot 18\cdot 21\cdot 24\cdot 27\cdot 30)=$

$=W_3(3^{10}\cdot 1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10)=$

$=10+W_3(1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10)=$

$=10+W_3(3\cdot 6\cdot 9)=$

$=10+W_3(3^3\cdot 1\cdot 2\cdot 3)=$

$=10+3+W_3(1\cdot 2\cdot 3)=$

$=10+3+W_3(3)=$

$=10+3+1=$

$=14$

Co jest zgodne ze wzorem:

$W_3(30!)=\lfloor \frac{30}{3}\rfloor +\lfloor \frac{30}{3^2}\rfloor +\lfloor \frac{30}{3^3}\rfloor =10+3+1=14$

Podobnie jak w poprzednim podrozdziale będziemy badali współczynnik dwumianowy postaci $(\genfrac{}{}{0ex}{}{2n}{n})$. Teraz już łatwo możemy policzyć wykładnik, z jakim liczba pierwsza $p$ wchodzi do rozwinięcia na czynniki pierwsze tego współczynnika dwumianowego.

Twierdzenie A24
Liczba pierwsza $p$ wchodzi do rozwinięcia na czynniki pierwsze liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ z wykładnikiem

$u=\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )$

Dowód

Ponieważ $(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n!{)}^2}$, to liczba pierwsza $p$ wchodzi do rozwinięcia na czynniki pierwsze liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ z wykładnikiem:

$W_p\left((\genfrac{}{}{0ex}{}{2n}{n})\right)=W_p((2n)!)-2W_p(n!)=\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{2n}{p^k}\rfloor -2\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor =\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )$

□

Twierdzenie A25
Liczby pierwsze spełniające warunek $p>\sqrt{2n}$ występują w rozwinięciu liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze z wykładnikiem $u=1$ lub $u=0$.

Dowód

Jeżeli $p>\sqrt{2n}$, to dla $k⩾2$ mamy $p^k⩾p^2>2n>n$. Zatem dla $k⩾2$ jest $\lfloor \frac{2n}{p^k}\rfloor =\lfloor \frac{n}{p^k}\rfloor =0$ i otrzymujemy

$u=\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )=\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor$

Na mocy twierdzenia A15 (dla $x=\frac{n}{p}$), dostajemy natychmiast, że $u=1$ lub $u=0$.
□

Twierdzenie A26
Niech $p$ będzie liczbą pierwszą. Jeżeli $p^a|(\genfrac{}{}{0ex}{}{2n}{n})$, to $p^a⩽2n$.

Dowód

Niech $u$ oznacza wykładnik, z jakim liczba pierwsza $p$ wchodzi do rozwinięcia współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze. Mamy

$u=\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )$

gdzie sumowanie przebiega w rzeczywistości od $k=1$ do $k=s$, a wartość liczby $s$ wynika z warunku $p^s⩽2n<p^{s+1}$. Ponieważ sumowane wyrazy są równe $0$ lub $1$, to otrzymujemy natychmiast oszacowanie $u⩽s$, skąd wynika następujący ciąg nierówności

$p^a⩽p^u⩽p^s⩽2n$

□

Oszacowanie $p_n$ od góry i $\pi (n)$ od dołu

Z twierdzenia A26 wynika natychmiast

Twierdzenie A27
Niech $(\genfrac{}{}{0ex}{}{2n}{n})=q_1^{{\alpha }_1}\cdot \dots \cdot q_s^{{\alpha }_s}$ będzie rozkładem współczynnika dwumianowego na czynniki pierwsze. Dla każdej liczby pierwszej $q_i$, $i=1,\dots ,s$ prawdziwe jest oszacowanie $q_i^{{\alpha }_i}⩽2n$.

Uwaga: w powyższym twierdzeniu $q_i$ nie oznacza $i$-tej liczby pierwszej, a pewną liczbą pierwszą o indeksie $i$ ze zboru liczb pierwszych $q_1,\dots q_s$, które wchodzą do rozkładu współczynnika dwumianowego na czynniki pierwsze z wykładnikiem większym od zera.

Twierdzenie A28
Dla $n⩾1$ prawdziwe jest następujące oszacowanie współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$

$(\genfrac{}{}{0ex}{}{2n}{n})⩽(2n{)}^{\pi (2n)}<(2n+1{)}^{\pi (2n+1)}$

Dowód

Dowód wynika natychmiast z twierdzenia A27, bowiem

$(\genfrac{}{}{0ex}{}{2n}{n})=q_1^{{\alpha }_1}\cdot \dots \cdot q_s^{{\alpha }_s}⩽(2n{)}^s⩽(2n{)}^{\pi (2n)}<(2n+1{)}^{\pi (2n+1)}$

□

Twierdzenie A29
Dla $n⩾3$ prawdziwe jest następujące oszacowanie

$\pi (n)>\frac{2}{3}\cdot \frac{n}{\log n}$

Dowód

W twierdzeniu A4 oszacowaliśmy współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2n}{n})$. Przepiszemy, to twierdzenie w postaci bardziej czytelnej dla potrzeb tego dowodu

${\left(\sqrt{3.8}\right)}^{2n}<{\left(\sqrt{3.8}\right)}^{2n+1}<{\left(\sqrt{3.8}\right)}^{2n+2}={3.8}^{n+1}<(\genfrac{}{}{0ex}{}{2n}{n})$

Nierówności te są prawdziwe dla $n⩾80$. Z twierdzenia A28 mamy

${\left(\sqrt{3.8}\right)}^{2n}<{\left(\sqrt{3.8}\right)}^{2n+1}<(\genfrac{}{}{0ex}{}{2n}{n})⩽(2n{)}^{\pi (2n)}<(2n+1{)}^{\pi (2n+1)}$

Łącząc odpowiednie oszacowania współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$ od góry z odpowiednimi oszacowaniami od dołu, dostajemy

$(2n+1{)}^{\pi (2n+1)}>{\left(\sqrt{3.8}\right)}^{2n+1}$

$(2n{)}^{\pi (2n)}>{\left(\sqrt{3.8}\right)}^{2n}$

Zatem zarówno dla parzystych, jak i nieparzystych liczb $m⩾160$ jest

$m^{\pi (m)}>{\left(\sqrt{3.8}\right)}^m$

$\pi (m)\cdot \log m>m\cdot \log \left(\sqrt{3.8}\right)$

Czyli

$\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}$

Dla $m=3,4,\dots ,159$ 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) ))

□

Twierdzenie A30
Niech $n⩾3$. Dla $n$-tej liczby pierwszej $p_n$ prawdziwe jest oszacowanie $p_n<2n\log n$

Dowód

Rozpoczniemy od pokazania, że dla $x>83499.14$ prawdziwe jest następujące oszacowanie funkcji $\log x$ od góry

$\log x<\frac{2}{3}\cdot x^{1/4}$

Wiemy, że dla dowolnego $n\in {\mathbb{Z}}_{+}$ istnieje takie $x_0$, że dla $x>x_0$ jest $\log x<x^{1/n}$. Zatem dla odpowiednio dużych $x$ z pewnością będzie $\frac{2}{3}\cdot x^{1/4}>\log x$^[a]. Zamieszczony niżej obrazek przedstawia wykres funkcji $f(x)=\frac{2}{3}\cdot x^{1/4}-\log x$.

Wpisując w PARI/GP polecenie

solve(x = 80000, 10^5, 2/3 * x^(1/4) - log(x))

wyliczamy, że funkcja $f(x)$ przecina oś $OX$ w punkcie $x=83499.136\dots$ Wynika stąd, że dla $x>83499.14$ prawdziwa jest nierówność

$\log x<\frac{2}{3}\cdot x^{1/4}$

Z twierdzenia A29 wiemy, że dla $n⩾3$ prawdziwe jest oszacowanie $\pi (n)>\frac{2}{3}\cdot \frac{n}{\log n}$. Kładąc $n=p_k$, otrzymujemy dla $k⩾2$

$k=\pi (p_k)>\frac{2}{3}\cdot \frac{p_k}{\log p_k}$

Zatem

$p_k<\frac{3}{2}\cdot k\cdot \log p_k(1)$

Korzystając z wcześniej pokazanego oszacowania, otrzymujemy nierówność prawdziwą dla $p_k>83499$

$p_k<\frac{3}{2}\cdot k\cdot \frac{2}{3}\cdot (p_k{)}^{1/4}$

czyli

$(p_k{)}^{3/4}<k$

$p_k<k^{4/3}$

Wstawiając to oszacowanie ponownie do $(1)$, dostajemy

$p_k<\frac{3}{2}\cdot k\cdot \frac{4}{3}\cdot \log k=2k\log k$

Wpisując w PARI/GP polecenie

for(k = 1, 10^5, p = prime(k); if( p > 83499, print("end"); break() ); if( p >= 2 * k * log(k), print(k) ))

łatwo sprawdzamy, że oszacowanie $p_k<2k\log k$ jest prawdziwe dla $k⩾3$.

---

[a] Bardziej precyzyjnie: pochodna funkcji $f(x)=\frac{2}{3}\cdot x^{1/4}-\log x$ jest równa $\frac{1}{6x^{3/4}}-\frac{1}{x}$ (zobacz WolframAlpha). Łatwo sprawdzamy, że pochodna jest ujemna w przedziale $(0,1296)$ i dodatnia w przedziale $(1296,\mathrm{\infty })$. Wynika stąd, że funkcja $f(x)$ jest funkcją malejącą dla $x<1296$ i rosnącą dla $x>1296$.
□

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 $n⩾3$ prawdziwe jest oszacowanie:

$p_1\cdot \dots \cdot p_n<(n\log n{)}^n$

Dowód

Indukcja matematyczna. Twierdzenie jest prawdziwe dla $n=3$. Zakładając prawdziwość twierdzenia dla $n$, otrzymujemy dla $n+1$:

$p_1\cdot \dots \cdot p_n{p}_{n+1}<(n\log n{)}^n\cdot p_{n+1}<$

$<n^n\cdot (\log n{)}^n\cdot 2(n+1)\log (n+1)⩽$

$⩽n^n\cdot {(1+\frac{1}{n})}^n\cdot (n+1)\cdot (\log n{)}^n\cdot \log (n+1)<$

$<(n+1{)}^{n+1}\cdot [\log (n+1){]}^n\cdot \log (n+1)=$

$=[(n+1)\cdot \log (n+1){]}^{n+1}$

Gdzie skorzystaliśmy z twierdzenia A30 oraz z faktu, że ciąg $a_n={(1+\frac{1}{n})}^n$ jest ciągiem ograniczonym $2⩽a_n<3$ (zobacz twierdzenie A6).
□

Uwagi do dowodu

Wydłużając znacząco czas obliczeń, moglibyśmy nieco poprawić uzyskane wyżej oszacowanie i udowodnić

Twierdzenie A31
Niech $n⩾3$. Dla $n$-tej liczby pierwszej $p_n$ prawdziwe jest oszacowanie $p_n<1.875\cdot n\log n$

Dowód

Rozpoczniemy od pokazania, że dla $x>7572437.23$ prawdziwe jest następujące oszacowanie funkcji $\log x$ od góry

$\log x<\frac{2}{3}\cdot x^{1/5}$

Wiemy, że dla dowolnego $n\in {\mathbb{Z}}_{+}$ istnieje takie $x_0$, że dla $x>x_0$ jest $\log x<x^{1/n}$. Zatem dla odpowiednio dużych $x$ z pewnością będzie $\frac{2}{3}\cdot x^{1/5}>\log x$^[a]. Wpisując w PARI/GP polecenie

solve(x = 10^6, 10^7, 2/3 * x^(1/5) - log(x))

wyliczamy, że funkcja $f(x)=\frac{2}{3}\cdot x^{1/5}-\log x$ przecina oś $OX$ w punkcie $x=7572437.223\dots$ Wynika stąd, że dla $x>7572437.23$ prawdziwa jest nierówność

$\log x<\frac{2}{3}\cdot x^{1/5}$

Z twierdzenia A29 wiemy, że dla $n⩾3$ prawdziwe jest oszacowanie $\pi (n)>\frac{2}{3}\cdot \frac{n}{\log n}$. Kładąc $n=p_k$, otrzymujemy dla $k⩾2$

$k=\pi (p_k)>\frac{2}{3}\cdot \frac{p_k}{\log p_k}$

Zatem

$p_k<\frac{3}{2}\cdot k\cdot \log p_k(1)$

Korzystając z wcześniej pokazanego oszacowania, otrzymujemy nierówność prawdziwą dla $p_k>7572437$

$p_k<\frac{3}{2}\cdot k\cdot \frac{2}{3}\cdot (p_k{)}^{1/5}$

czyli

$(p_k{)}^{4/5}<k$

$p_k<k^{5/4}$

Wstawiając to oszacowanie ponownie do $(1)$, dostajemy

$p_k<\frac{3}{2}\cdot k\cdot \frac{5}{4}\cdot \log k=1.875\cdot k\log k$

Wpisując w PARI/GP polecenie

for(k = 1, 10^7, p = prime(k); if( p > 7572437, print("end"); break() ); if( p >= 2 * k * log(k), print(k) ))

łatwo sprawdzamy, że oszacowanie $p_k<1.875\cdot k\log k$ jest prawdziwe dla $k⩾3$.

---

[a] Bardziej precyzyjnie: pochodna funkcji $f(x)=\frac{2}{3}\cdot x^{1/5}-\log x$ jest równa $\frac{2}{15x^{4/5}}-\frac{1}{x}$ (zobacz WolframAlpha). Łatwo sprawdzamy, że pochodna jest ujemna w przedziale $(0,23730.46875)$ i dodatnia w przedziale $(23730.46875,\mathrm{\infty })$. Wynika stąd, że funkcja $f(x)$ jest funkcją malejącą dla $x<23730.46875$ i rosnącą dla $x>23730.46875$.
□

Twierdzenie A32
Niech $n⩾2$. Dla funkcji $\pi (n)$ prawdziwe jest oszacowanie

$\pi (n)<1.733\cdot \frac{n}{\log n}$

Dowód

Z twierdzenia A1 wiemy, że dla $n⩾3$ jest

$\pi (n)>\frac{2}{3}\cdot \frac{n}{\log n}>n^{4/5}$

Ostatnia nierówność wynika z faktu, że dla $x>7572437.223\dots$ prawdziwe jest oszacowanie

$\frac{2}{3}\cdot \frac{x}{\log x}>x^{4/5}$

Korzystając z twierdzenia A9 możemy napisać ciąg nierówności

$4^n>P(n)=p_1{p}_2\cdot \dots \cdot p_{\pi (n)}>\pi (n{)}^{\pi (n)}>(n^{4/5}{)}^{\pi (n)}=n^{4\pi (n)/5}$

skąd otrzymujemy, że dla $n⩾7572438$ prawdziwe jest oszacowanie

$\pi (n)<1.733\cdot \frac{n}{\log n}$

W GP/PARI sprawdzamy, że otrzymana nierówność jest prawdziwa dla $n⩾2$

for(n = 2, 8*10^6, if( primepi(n) >= 1.733 * n/log(n), print(n) ))

□

Uwaga A33
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)
     );
}

Uwaga A34
Czytelnik nie powinien mieć złudzeń, że postępując podobnie, uzyskamy istotne polepszenie oszacowania funkcji $\pi (n)$ lub $p_n$. Już osiągnięcie tą drogą oszacowania $p_n<1.6\cdot n\log n$ przekracza możliwości obliczeniowe współczesnych komputerów. Wystarczy zauważyć, że nierówność

$\log x<\frac{2}{3}\cdot x^{1/16}$

jest prawdziwa dla $x>7.671\cdot {10}^{32}$.

Zastosowania

Ciekawy rezultat wynika z twierdzenia A7, ale wcześniej musimy udowodnić twierdzenie o średniej arytmetycznej i geometrycznej.

Twierdzenie A35
Dla dowolnych liczb dodatnich $a_1,a_2,\dots ,a_n$ średnia arytmetyczna jest nie mniejsza od średniej geometrycznej

$\frac{a_1+a_2+\dots +a_n}{n}⩾\sqrt[n]{a_1{a}_2\cdot \dots \cdot a_n}$

Dowód

Twierdzenie jest w sposób oczywisty prawdziwe dla $n=1$. Równie łatwo stwierdzamy prawdziwość nierówności dla $n=2$

$(a_1-a_2{)}^2⩾0$

$a_1^2-2a_1{a}_2+a_2^2⩾0$

$a_1^2+2a_1{a}_2+a_2^2⩾4a_1{a}_2$

$(a_1+a_2{)}^2⩾4a_1{a}_2$

$\frac{a_1+a_2}{2}⩾\sqrt{a_1{a}_2}$

Dla potrzeb dowodu zapiszemy dowodzoną nierówność w postaci

${\left(\frac{a_1+a_2+\dots +a_n}{n}\right)}^n⩾a_1{a}_2\cdot \dots \cdot a_n$

Zakładając, że twierdzenie jest prawdziwe dla wszystkich liczb całkowitych dodatnich nie większych od $n$ dla $n+1$ mamy

a) w przypadku gdy $n+1=2k$ jest liczbą parzystą

${\left(\frac{a_1+a_2+\dots +a_{n+1}}{n+1}\right)}^{n+1}={\left(\frac{a_1+a_2+\dots +a_{2k}}{2k}\right)}^{2k}=$

$={\left[{\left(\frac{\frac{a_1+a_2}{2}+\frac{a_3+a_4}{2}+\dots +\frac{a_{2k-1}+a_{2k}}{2}}{k}\right)}^k\right]}^2⩾$

$⩾{(\frac{a_1+a_2}{2}\cdot \frac{a_3+a_4}{2}\cdot \dots \cdot \frac{a_{2k-1}+a_{2k}}{2})}^2⩾$

$⩾{(\sqrt{a_1{a}_2}\cdot \sqrt{a_3{a}_4}\cdot \dots \cdot \sqrt{a_{2k-1}{a}_{2k}})}^2=$

$=a_1{a}_2\cdot \dots \cdot a_{2k}=$

$=a_1{a}_2\cdot \dots \cdot a_{n+1}$

Gdzie skorzystaliśmy z założenia indukcyjnego i prawdziwości dowodzonego twierdzenia dla $n=2$.

b) w przypadku gdy $n+1=2k-1$ jest liczbą nieparzystą, możemy skorzystać z udowodnionego wyżej punktu a) dla parzystej ilości liczb

$a_1,a_2,\dots ,a_{2k-1},S$

gdzie przez $S$ oznaczyliśmy średnią arytmetyczną liczb $a_1,a_2,\dots ,a_{2k-1}$

$S=\frac{a_1+a_2+\dots +a_{2k-1}}{2k-1}$

Na mocy punktu a) prawdziwa jest nierówność

${\left(\frac{a_1+a_2+\dots +a_{2k-1}+S}{2k}\right)}^{2k}={\left(\frac{(2k-1)S+S}{2k}\right)}^{2k}⩾a_1{a}_2\cdot \dots \cdot a_{2k-1}\cdot S$

Skąd otrzymujemy

$S^{2k}⩾a_1{a}_2\cdot \dots \cdot a_{2k-1}\cdot S$

$S^{2k-1}⩾a_1{a}_2\cdot \dots \cdot a_{2k-1}$

Co należało pokazać.
□

Twierdzenie A36
Dla $n⩾1$ prawdziwa jest nierówność $p_1+p_2+\dots +p_n>n^2$.

Dowód

Korzystając z twierdzeń A7 i A35 możemy napisać następujący ciąg nierówności dla $n$ kolejnych liczb pierwszych

$\frac{p_1+p_2+\dots +p_n}{n}⩾\sqrt[n]{p_1\cdot p_2\cdot \dots \cdot p_n}>\sqrt[n]{n^n}=n$

Stąd otrzymujemy natychmiast tezę twierdzenia, którą sprawdzamy dla $n<13$. 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) ))

□

Twierdzenie A1 pozwala nam udowodnić różne oszacowania funkcji $\pi (n)$ i $p_n$, które byłyby trudne do uzyskania inną drogą. Wykorzystujemy do tego znany fakt, że dla dowolnego $\epsilon >0$ istnieje takie $n_0$, że dla każdego $n>n_0$ prawdziwa jest nierówność $\log x<x^{\epsilon }$. Inaczej mówiąc, funkcja $\log x$ 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.

Twierdzenie A37
Prawdziwe są następujące nierówności:

1.    $e^x>x$ dla każdego $x\in \mathbb{R}$

2.    $e^x>2x$ dla każdego $x\in \mathbb{R}$

3.    $\log x<n\cdot x^{1/n}$ dla każdego $x\in {\mathbb{R}}_{+}$ i dowolnego $n\in {\mathbb{Z}}_{+}$

4.    $\log x⩽n(x^{1/n}-1)$ dla każdego $x\in {\mathbb{R}}_{+}$ i dowolnego $n\in {\mathbb{Z}}_{+}$

Dowód

Punkt 1. i punkt 2.

Ponieważ funkcję $\exp (x)$ możemy zdefiniować w sposób równoważny wzorem

$e^x=\sum _{k=0}^{\mathrm{\infty }}\frac{x^k}{k!}=1+x+\frac{x^2}{2}+\frac{x^3}{6}+\frac{x^4}{24}+\frac{x^5}{120}+\dots$

to funkcja $e^x$ jest funkcją dodatnią, bo dla $x>0$ sumujemy tylko wyrazy dodatnie, dla $x=0$ mamy $e^0=1$, a dla $x<0$ możemy napisać $e^x=\frac{1}{e^{|x|}}>0$.

Ponieważ funkcje $x$ i $2x$ są ujemne lub równe zero dla $x⩽0$, to pozostaje rozważyć jedynie przypadek, gdy $x>0$. Łatwo zauważmy, że

$e^x-x=\sum _{k=0}^{\mathrm{\infty }}\frac{x^k}{k!}-x=1+\sum _{k=2}^{\mathrm{\infty }}\frac{x^k}{k!}>0$

$e^x-2x=\sum _{k=0}^{\mathrm{\infty }}\frac{x^k}{k!}-2x=1-x+\frac{x^2}{2}+\sum _{k=3}^{\mathrm{\infty }}\frac{x^k}{k!}=\frac{1}{2}+\frac{(x-1{)}^2}{2}+\sum _{k=3}^{\mathrm{\infty }}\frac{x^k}{k!}>0$

Punkt 3.

W rozpatrywanej nierówności połóżmy zmienną pomocniczą $x=e^y$, gdzie $y\in \mathbb{R}$. Otrzymujemy

$y<n\cdot (e^y{)}^{1/n}$

Czyli

$\frac{y}{n}<e^{y/n}$

Otrzymana nierówność jest prawdziwa dla dowolnego $\frac{y}{n}\in \mathbb{R}$ na mocy punktu 1. tego twierdzenia.

Punkt 4.

Rozważmy funkcję

$f(x)=n\cdot x^{1/n}-\log x$

Pochodna tej funkcji jest równa

$f^{\prime }(x)=\frac{x^{1/n}-1}{x}$

Pochodna jest równa zero dla $x=1$. Dla $0<x<1$ pochodna jest ujemna, a dla $x>1$ jest dodatnia, zatem w punkcie $x=1$ funkcja $f(x)$ ma minimum i $f(1)=n$. Wynika stąd oszacowanie

$f(x)=n\cdot x^{1/n}-\log x⩾n$

Skąd otrzymujemy

$\log x⩽n(x^{1/n}-1)$

□

Zadanie A38
Niech $x\in {\mathbb{R}}_{+}$. Pokazać, że dla dowolnego $n\in {\mathbb{Z}}_{+}$ istnieje takie $x_0$, że dla każdego $x>x_0$ jest $\log x<x^{1/n}$.

Rozwiązanie

Pierwszy sposób
Rozważmy ciąg nierówności

$\log x<2n\cdot x^{1/2n}<x^{1/n}$

Z twierdzenia A37 wiemy, że pierwsza nierówność jest prawdziwa dla dowolnych $x\in {\mathbb{R}}_{+}$ i $n\in {\mathbb{Z}}_{+}$. Podnosząc strony drugiej nierówności do potęgi $2n$ otrzymujemy $(2n{)}^{2n}\cdot x<x^2$, czyli nierówność ta jest prawdziwa dla $x>(2n{)}^{2n}$. Wynika stąd, że wystarczy przyjąć $x_0=(2n{)}^{2n}$.

Drugi sposób
Nierówność $\log x<x^{1/n}$ możemy równoważnie zapisać w postaci $x<\exp (x^{1/n})$. Jeżeli położymy $x=t^n$, to otrzymamy nierówność $t^n<e^t$. Ponieważ

$e^t=\sum _{k=0}^{\mathrm{\infty }}\frac{t^k}{k!}=1+t+\frac{t^2}{2}+\frac{t^3}{6}+\frac{t^4}{24}+\frac{t^5}{120}+\dots$

to

$e^t>\frac{t^{n+1}}{(n+1)!}>t^n$

Pierwsza nierówność jest prawdziwa dla $t>0$, bo pomijamy wyrazy dodatnie, a druga dla $t>(n+1)!$ Wystarczy zatem przyjąć $x_0=[(n+1)!{]}^n$. Ponieważ $[(n+1)!{]}^n>(2n{)}^{2n}$ dla $n⩾4$, to jest to gorsze oszacowanie wartości $x_0$.
□

Twierdzenie A39
Dla funkcji $p_n$ i $\pi (n)$ prawdziwe są następujące oszacowania:

$10n\underset{n⩾6473}{<}{p}_n\underset{n⩾2}{<}{n}^2$

$\sqrt{n}\underset{n⩾5}{<}\pi (n)\underset{n⩾64721}{<}\frac{n}{10}$

Dowód

Lewa górna nierówność. Z twierdzenia A1 wiemy, że dla $n⩾1$ jest $p_n>0.72\cdot n\log n$. Wystarczy rozwiązać nierówność:

$0.72\cdot \log n>10$

czyli $n>\exp \left(\frac{10}{0.72}\right)=1076137.5$

W PARI/GP wpisujemy polecenie:

for(n=1, 11*10^5, if( prime(n) <= 10*n, print(n) ))

Prawa górna nierówność. Z twierdzenia A1 wiemy, że dla $n⩾3$ jest $p_n<2n\log n$. Zatem wystarczy pokazać, że $2n\log n<n^2$. Korzystając z twierdzenia A37, łatwo zauważmy, że dla $n>16$ jest:

$n-2\log n>n-2\cdot 2\cdot n^{1/2}=\sqrt{n}(\sqrt{n}-4)>0$

Przypadki $n⩽16$ sprawdzamy bezpośrednio.

Lewa dolna nierówność. Z twierdzenia A1 wiemy, że dla $n⩾3$ jest $\pi (n)>\frac{2}{3}\cdot \frac{n}{\log n}$. Zatem wystarczy pokazać, że $\frac{2}{3}\cdot \frac{n}{\log n}>\sqrt{n}$. Korzystając z twierdzenia A37, łatwo zauważmy, że dla $n>6^4=1296$ jest:

$\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$

Sprawdzenie przypadków $n⩽1296$ sprowadza się do wpisania w PARI/GP polecenia:

for(n=1, 2000, if( primepi(n) <= sqrt(n), print(n) ))

Prawa dolna nierówność. Z twierdzenia A1 wiemy, że dla $n⩾2$ jest $\pi (n)<\frac{2n}{\log n}$. Zatem wystarczy pokazać, że $\frac{2n}{\log n}<\frac{n}{10}$. Nierówność ta jest prawdziwa dla $\log n>20$, czyli dla

$n>e^{20}>485165195.4$

Sprawdzenie przypadków dla $n⩽490\cdot {10}^6$ 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)
     );
}

□

Twierdzenie A40
Dla $n⩾1$ prawdziwe jest oszacowanie

$p_1{p}_2\cdot \dots \cdot p_n>(p_{n^2}{)}^{n/3}$

Dowód

Korzystając kolejno z twierdzeń A30, A37 i A7, łatwo otrzymujemy

$(p_{n^2}{)}^{n/3}<(2\cdot n^2\cdot \log n^2{)}^{n/3}$

$=(4\cdot n^2\cdot \log n{)}^{n/3}$

$<(8\cdot n^{5/2}{)}^{n/3}$

$=(2\cdot n^{5/6}{)}^n$

$<n^n$

$<p_1{p}_2\cdot \dots \cdot p_n$

Zauważmy, że nierówność $2\cdot n^{5/6}<n$ jest prawdziwa dla $n>2^6$. Sprawdzając bezpośrednio dla $n⩽64$ stwierdzamy, że dowodzona nierówność jest prawdziwa dla $n⩾1$.
□

Zadanie A41
Korzystając z twierdzenia A40 pokazać, że

•    $p_1{p}_2\cdot \dots \cdot p_n>(p_{n+1}{)}^2\text{dla }n⩾4$
•    $p_1{p}_2\cdot \dots \cdot p_n>(p_{2n}{)}^3\text{dla }n⩾7$

Rozwiązanie

Punkt 1.

Ponieważ $n^2>n+1$ dla $n⩾2$ oraz $\frac{n}{3}>2$ dla $n>6$, to dla $n>6$ jest

$p_1{p}_2\cdot \dots \cdot p_n>(p_{n^2}{)}^{n/3}>(p_{n+1}{)}^2$

Sprawdzając bezpośrednio dla $n⩽6$, łatwo stwierdzamy prawdziwość oszacowania dla $n⩾4$.

Punkt 2.

Ponieważ $n^2>2n$ dla $n>2$ oraz $\frac{n}{3}>3$ dla $n>9$, to dla $n>9$ jest

$p_1{p}_2\cdot \dots \cdot p_n>(p_{n^2}{)}^{n/3}>(p_{2n}{)}^3$

Sprawdzając bezpośrednio dla $n⩽9$, łatwo stwierdzamy prawdziwość oszacowania dla $n⩾7$.
□

Twierdzenie A42
Każda liczba pierwsza $p$, taka że $p\in (\frac{n}{2},n]$ występuje w rozwinięciu $n!$ na czynniki pierwsze z wykładnikiem równym jeden.

Dowód

Z twierdzenia A21 wiemy, że każda liczba pierwsza $p$ występuje w iloczynie $n!$ z wykładnikiem $W_p(n!)=\sum _{k=1}^{\mathrm{\infty }}\lfloor \frac{n}{p^k}\rfloor$

Z założenia $p⩽n$ i $2p>n$, zatem:

1.    $\frac{n}{p}⩾1$   oraz   $\frac{n}{p}<2$,   czyli   $\lfloor \frac{n}{p}\rfloor =1$

2.    $\frac{n}{p^2}<\frac{2}{p}⩽1$,   czyli   $\lfloor \frac{n}{p^2}\rfloor =0$   i tym bardziej   $\lfloor \frac{n}{p^k}\rfloor =0$   dla   $k⩾3$

□

Rezultat uzyskany w twierdzeniu A25 zainspirował nas do postawienia pytania: jakie warunki musi spełniać liczba pierwsza $p$, aby występowała w rozwinięciu liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze z wykładnikiem równym jeden lub równym zero? Twierdzenia A43 i A45 udzielają na to pytanie precyzyjnej odpowiedzi. Przykłady A44 i A46 to tylko twierdzenia A43 i A45 dla wybranych wartości liczby $k$. Jeśli Czytelnik nie miał problemów ze zrozumieniem dowodów twierdzeń A43 i A45, to może je pominąć.

Twierdzenie A43
Niech $k$ będzie dowolną ustaloną liczbą naturalną. Jeżeli $n⩾2(k+1)(k+\frac{1}{2})$ i liczba pierwsza $p\in (\frac{n}{k+1},\frac{n}{k+\frac{1}{2}}]$, to $p$ występuje w rozwinięciu liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze z wykładnikiem równym jeden.

Dowód

Najpierw udowodnimy przypadek $k=0$.

Zauważmy, że każda liczba pierwsza $p\in (n,2n]$ występuje dokładnie jeden raz w liczniku ułamka

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n!{)}^2}=\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

i nie występuje w mianowniku. Zatem w rozwinięciu współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze wystąpi z wykładnikiem równym $1$.

Co kończy dowód twierdzenia w przypadku, gdy $k=0$.

Możemy teraz przejść do dowodu dla wszystkich $k⩾1$.

Dowód na podstawie analizy krotności pojawiania się liczby $p$

Zapiszmy współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2n}{n})$ w postaci ułamka

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n!{)}^2}=\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

Rozważmy dowolną liczbę pierwszą występującą w mianowniku wypisanego wyżej ułamka. Potrzebujemy, aby $p$ spełniała następujące warunki:

• $kp⩽n$ — warunek ten zapewnia nam, że liczba $p$ pojawi się co najmniej $k$ razy w mianowniku
• $(k+1)p>n$ — warunek ten zapewnia nam, że liczba $p$ pojawi się dokładnie $k$ razy w mianowniku (jako $p,2p,\dots ,kp$)
• $(2k+1)p⩽2n$ — warunek ten (łącznie z warunkiem $(k+1)p>n$) zapewnia nam, że liczba $p$ pojawi się co najmniej $k+1$ razy w liczniku
• $(2k+2)p>2n$ — warunek ten (łącznie z warunkiem $(2k+1)p⩽2n$) zapewnia nam, że liczba $p$ pojawi się dokładnie $k+1$ razy w liczniku (jako $(k+1)p,(k+2)p,\dots ,(2k+1)p$)

Łącząc otrzymane warunki, otrzymujemy, że liczba pierwsza $p\in (\frac{n}{k+1},\frac{n}{k+\frac{1}{2}}]$ pojawia się dokładnie $k$ razy w mianowniku i dokładnie $k+1$ razy w liczniku ułamka

$\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

Zatem występuje w rozwinięciu współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze z wykładnikiem jeden.

Niech $q$ będzie największą liczbą pierwszą nie większą od ustalonej liczby $2k+1$. Rozpatrywane przez nas wielokrotności liczby zwiększają wykładniki, z jakimi występują liczby pierwsze $r_i\in \{2,3,\dots ,q\}$. Dlatego twierdzenie nie może dotyczyć tych liczb i musimy nałożyć warunek

$r_i\notin (\frac{n}{k+1},\frac{n}{k+\frac{1}{2}}]$

Warunek ten będzie z pewnością spełniony, gdy

$q⩽2k+1⩽\frac{n}{k+1}$

czyli dla $n$ spełniających nierówność $n⩾(k+1)(2k+1)$.

Oczywiście nie wyklucza to możliwości, że istnieją liczby $n<2(k+1)(k+\frac{1}{2})$, dla których twierdzenie jest prawdziwe. Pozostaje (przy ustalonej wartości liczby $k$) bezpośrednio sprawdzić prawdziwość twierdzenia dla $n<2(k+1)(k+\frac{1}{2})$.

Dowód na podstawie twierdzenia A24

Rozważmy najpierw pierwszy składnik sumy

$\sum _{s=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^s}\rfloor -2\lfloor \frac{n}{p^s}\rfloor )$

Ponieważ przypuszczamy, że składnik ten będzie równy $1$, to będziemy szukali oszacowania od dołu. Z założenia mamy

1)    $p>\frac{n}{k+1}⟹\frac{n}{p}<k+1⟹\lfloor \frac{n}{p}\rfloor ⩽k$

2)    $p⩽\frac{n}{k+\frac{1}{2}}⟹\frac{2n}{p}⩾2k+1⟹\lfloor \frac{2n}{p}\rfloor ⩾2k+1$

Zatem

$\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor ⩾2k+1-2k=1$

Ponieważ każdy ze składników sumy może być równy tylko $0$ lub $1$, to otrzymujemy

$\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor =1$

Założenie, że $n⩾2(k+1{)}^2$ pozwoli uprościć obliczenia dla drugiego i następnych składników sumy

$p>\frac{n}{k+1}⟹\frac{2n}{p}<2k+2⟹$

$⟹\frac{(2n{)}^s}{p^s}<(2k+2{)}^s⟹$

$⟹\frac{2n}{p^s}<\frac{(2k+2{)}^2}{2n}\cdot {\left(\frac{2k+2}{2n}\right)}^{s-2}⟹$

$⟹\frac{2n}{p^s}<\frac{(2k+2{)}^2}{2n}⟹$

$⟹\frac{2n}{p^s}<1⟹$

$⟹\lfloor \frac{2n}{p^s}\rfloor =0$

Jeżeli $\lfloor \frac{2n}{p^s}\rfloor =0$, to również musi być $\lfloor \frac{n}{p^s}\rfloor =0$. Pokazaliśmy, że dla $n⩾2(k+1{)}^2$ jest

$\sum _{s=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^s}\rfloor -2\lfloor \frac{n}{p^s}\rfloor )=1$

Pozostaje bezpośrednio sprawdzić, dla jakich wartości $n<2(k+1{)}^2$ twierdzenie pozostaje prawdziwe.

Ponieważ analiza krotności pojawiania się liczby pierwszej $p$ jest bardziej precyzyjna, to podajemy, że twierdzenie jest z pewnością prawdziwe dla $n⩾2(k+1)(k+\frac{1}{2})$
□

Przykład A44
Jeżeli $n⩾6$ i liczba pierwsza $p\in (\frac{n}{2},\frac{2n}{3}]$, to $p$ występuje w rozwinięciu liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze z wykładnikiem równym jeden.

Dowód

Dowód na podstawie analizy krotności pojawiania się liczby $p$

Zapiszmy współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2n}{n})$ w postaci ułamka

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n!{)}^2}=\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

Rozważmy dowolną liczbę pierwszą występującą w mianowniku wypisanego wyżej ułamka. Potrzebujemy, aby $p$ spełniała następujące warunki:

• $p⩽n$ — warunek ten zapewnia nam, że liczba $p$ pojawi się co najmniej jeden raz w mianowniku
• $2p>n$ — warunek ten zapewnia nam, że liczba $p$ pojawi się dokładnie jeden raz w mianowniku (jako $p$)
• $3p⩽2n$ — warunek ten (łącznie z warunkiem $2p>n$) zapewnia nam, że liczba $p$ pojawi się co najmniej dwa razy w liczniku
• $4p>2n$ — warunek ten (łącznie z warunkiem $3p⩽2n$) zapewnia nam, że liczba $p$ pojawi się dokładnie dwa razy w liczniku (jako $2p$ i $3p$)

Łącząc otrzymane warunki, otrzymujemy, że liczba pierwsza $p\in (\frac{n}{2},\frac{2n}{3}]$ pojawia się dokładnie jeden raz w mianowniku i dokładnie dwa razy w liczniku ułamka

$\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

Zatem występuje w rozwinięciu współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze z wykładnikiem jeden.

Wielokrotności liczby $p$ podnoszą wykładniki, z jakimi występują liczby pierwsze $p=2,3$. Dlatego zakładamy, że $n⩾6$, bo dla $n⩾6$ liczby pierwsze $p=2,3$ nie spełniają warunku $p\in (\frac{n}{2},\frac{2n}{3}]$.

Bezpośrednio sprawdzamy, że twierdzenie nie jest prawdziwe dla $n=5$ i liczba $3^2$ dzieli liczbę $(\genfrac{}{}{0ex}{}{10}{5})=252=9\cdot 28$

Dowód na podstawie twierdzenia A24

Rozważmy najpierw pierwszy składnik sumy

$\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )$

Ponieważ przypuszczamy, że składnik ten będzie równy $1$, to będziemy szukali oszacowania od dołu. Z założenia mamy

1)    $p>\frac{n}{2}⟹\frac{n}{p}<2⟹\lfloor \frac{n}{p}\rfloor ⩽1$

2)    $p⩽\frac{2n}{3}⟹\frac{2n}{p}⩾3⟹\lfloor \frac{2n}{p}\rfloor ⩾3$

Zatem

$\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor ⩾3-2=1$

Ponieważ każdy ze składników sumy może być równy tylko $0$ lub $1$, to otrzymujemy

$\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor =1$

Założenie, że $n⩾9$ pozwoli uprościć obliczenia dla drugiego i następnych składników sumy

$p>\frac{n}{2}⟹\frac{(2n{)}^k}{p^k}<4^k⟹\frac{2n}{p^k}<\frac{16}{2n}\cdot {\left(\frac{4}{2n}\right)}^{k-2}⟹\frac{2n}{p^k}⩽\frac{16}{2n}⟹\frac{2n}{p^k}⩽\frac{16}{18}⟹\lfloor \frac{2n}{p^k}\rfloor =0$

Jeżeli $\lfloor \frac{2n}{p^k}\rfloor =0$, to również musi być $\lfloor \frac{n}{p^k}\rfloor =0$. Pokazaliśmy, że dla $n⩾9$ jest

$\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )=1$

Dla $n=6,7$ żadna liczba pierwsza nie należy do $(\frac{n}{2},\frac{2n}{3}]$. Dla $n=8$ łatwo sprawdzamy, że liczba $5$ wchodzi do rozkładu liczby $(\genfrac{}{}{0ex}{}{16}{8})=12870$ na czynniki pierwsze z wykładnikiem równym jeden.

Zatem dla $n⩾6$ liczba pierwsza $p\in (\frac{n}{2},\frac{2n}{3}]$ wchodzi do rozkładu liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze z wykładnikiem równym jeden.
□

Twierdzenie A45
Niech $k$ będzie dowolną ustaloną liczbą całkowitą dodatnią. Jeżeli liczba pierwsza $p\in (\frac{n}{k+\frac{1}{2}},\frac{n}{k}]$, to dla $n⩾2k(k+\frac{1}{2})$ liczba $p$ nie występuje w rozwinięciu liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze.

Dowód

Dowód na podstawie analizy krotności pojawiania się liczby $p$

Zapiszmy współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2n}{n})$ w postaci ułamka

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n!{)}^2}=\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

Rozważmy dowolną liczbę pierwszą $p$ występującą w mianowniku wypisanego wyżej ułamka. Potrzebujemy, aby $p$ spełniała następujące warunki:

• $kp⩽n$ — warunek ten zapewnia nam, że liczba $p$ pojawi się co najmniej $k$ razy w mianowniku
• $(k+1)p>n$ — warunek ten zapewnia nam, że liczba $p$ pojawi się dokładnie $k$ razy w mianowniku (jako $p,2p,\dots ,kp$)
• $2kp⩽2n$ — warunek ten (łącznie z warunkiem $(k+1)p>n$) zapewnia nam, że liczba $p$ pojawi się co najmniej $k$ razy w liczniku
• $(2k+1)p>2n$ — warunek ten (łącznie z warunkiem $2kp⩽2n$) zapewnia nam, że liczba $p$ pojawi się dokładnie $k$ razy w liczniku (jako $(k+1)p,(k+2)p,\dots ,2kp$)

Łącząc otrzymane warunki, otrzymujemy, że liczba pierwsza $p\in (\frac{n}{k+\frac{1}{2}},\frac{n}{k}]$ pojawia się dokładnie $k$ razy w mianowniku i dokładnie $k$ razy w liczniku ułamka

$\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

Co oznacza, że $p$ nie występuje w rozwinięciu współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze.

Niech $q$ będzie największą liczbą pierwszą nie większą od ustalonej liczby $2k$. Rozpatrywane przez nas wielokrotności liczby $p$ zwiększają wykładniki, z jakimi występują liczby pierwsze $r_i\in \{2,3,\dots ,q\}$. Dlatego twierdzenie nie może dotyczyć tych liczb i musimy nałożyć warunek

$r_i\notin (\frac{n}{k+\frac{1}{2}},\frac{n}{k}]$

Warunek ten będzie z pewnością spełniony, gdy

$q⩽2k⩽\frac{n}{k+\frac{1}{2}}$

czyli dla $n$ spełniających nierówność $n⩾2k(k+\frac{1}{2})$. Oczywiście nie wyklucza to możliwości, że istnieją liczby $n<2k(k+\frac{1}{2})$, dla których twierdzenie jest prawdziwe. Pozostaje (przy ustalonej wartości liczby $k$) bezpośrednio sprawdzić prawdziwość twierdzenia dla $n<2k(k+\frac{1}{2})$.

Dowód na podstawie twierdzenia A24

Rozważmy najpierw pierwszy składnik sumy

$\sum _{s=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^s}\rfloor -2\lfloor \frac{n}{p^s}\rfloor )$

Ponieważ przypuszczamy, że składnik ten będzie równy $0$, to będziemy szukali oszacowania od góry. Z założenia mamy

1)    $p>\frac{n}{k+\frac{1}{2}}⟹\frac{2n}{p}<2k+1⟹\lfloor \frac{2n}{p}\rfloor ⩽2k$

2)    $p⩽\frac{n}{k}⟹\frac{n}{p}⩾k⟹\lfloor \frac{n}{p}\rfloor ⩾k$

Zatem

$\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor ⩽2k-2k=0$

Ponieważ każdy ze składników sumy może być równy tylko $0$ lub $1$, to otrzymujemy

$\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor =0$

Założenie, że $2n⩾(2k+1{)}^2$ pozwoli uprościć obliczenia dla drugiego i następnych składników sumy

$p>\frac{2n}{2k+1}⟹\frac{(2n{)}^s}{p^s}<(2k+1{)}^s⟹$

$⟹\frac{2n}{p^s}<\frac{(2k+1{)}^2}{2n}\cdot {\left(\frac{2k+1}{2n}\right)}^{s-2}⟹$

$⟹\frac{2n}{p^s}<\frac{(2k+1{)}^2}{2n}⟹$

$⟹\frac{2n}{p^s}<1⟹$

$⟹\lfloor \frac{2n}{p^s}\rfloor =0$

Jeżeli $\lfloor \frac{2n}{p^s}\rfloor =0$, to również musi być $\lfloor \frac{n}{p^s}\rfloor =0$. Pokazaliśmy, że dla $2n⩾(2k+1{)}^2$ jest

$\sum _{s=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^s}\rfloor -2\lfloor \frac{n}{p^s}\rfloor )=0$

Pozostaje bezpośrednio sprawdzić, dla jakich wartości $n<\frac{1}{2}(2k+1{)}^2$ twierdzenie pozostaje prawdziwe.

Ponieważ analiza krotności pojawiania się liczby pierwszej $p$ jest bardziej precyzyjna, to podajemy, że twierdzenie jest z pewnością prawdziwe dla $n⩾2k(k+\frac{1}{2})$.
□

Przykład A46
Jeżeli $n⩾8$ i liczba pierwsza $p\in (\frac{2n}{5},\frac{n}{2}]$, to $p$ nie występuje w rozwinięciu liczby $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze.

Dowód

Dowód na podstawie analizy krotności pojawiania się liczby $p$

Zapiszmy współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2n}{n})$ w postaci ułamka

$(\genfrac{}{}{0ex}{}{2n}{n})=\frac{(2n)!}{(n!{)}^2}=\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

Rozważmy dowolną liczbę pierwszą $p$ występującą w mianowniku wypisanego wyżej ułamka. Potrzebujemy, aby $p$ spełniała następujące warunki:

• $2p⩽n$ — warunek ten zapewnia nam, że liczba $p$ pojawi się co najmniej dwa razy w mianowniku
• $3p>n$ — warunek ten zapewnia nam, że liczba $p$ pojawi się dokładnie dwa razy w mianowniku (jako $p$ i $2p$)
• $4p⩽2n$ — warunek ten (łącznie z warunkiem $3p>n$) zapewnia nam, że liczba $p$ pojawi się co najmniej dwa razy w liczniku
• $5p>2n$ — warunek ten (łącznie z warunkiem $4p⩽2n$) zapewnia nam, że liczba $p$ pojawi się dokładnie dwa razy w liczniku (jako $3p$ i $4p$)

Łącząc otrzymane warunki, otrzymujemy, że liczba pierwsza $p\in (\frac{2n}{5},\frac{n}{2}]$ pojawia się dokładnie dwa razy w mianowniku i dokładnie dwa razy w liczniku ułamka

$\frac{(n+1)\cdot (n+2)\cdot \dots \cdot (2n-1)\cdot 2n}{1\cdot 2\cdot \dots \cdot (n-1)\cdot n}$

Zatem nie występuje w rozwinięciu współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2n}{n})$ na czynniki pierwsze.

Wielokrotności liczby $p$ podnoszą wykładniki, z jakimi występują liczby pierwsze $2$ i $3$. Dlatego zakładamy, że $n⩾8$, bo dla $n⩾8$ liczby pierwsze $2,3$ nie spełniają warunku $p\in (\frac{2n}{5},\frac{n}{2}]$.

Bezpośrednio sprawdzamy, że twierdzenie nie jest prawdziwe dla $n=7$ i liczba $3$ dzieli liczbę $(\genfrac{}{}{0ex}{}{14}{7})=3432$

Dowód na podstawie twierdzenia A24

Rozważmy najpierw pierwszy składnik sumy

$\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )$

Ponieważ przypuszczamy, że składnik ten będzie równy $0$, to będziemy szukali oszacowania od góry. Z założenia mamy

1)    $p>\frac{2n}{5}⟹\frac{2n}{p}<5⟹\lfloor \frac{2n}{p}\rfloor ⩽4$

2)    $p⩽\frac{n}{2}⟹\frac{n}{p}⩾2⟹\lfloor \frac{n}{p}\rfloor ⩾2$

Zatem

$\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor ⩽4-4=0$

Ponieważ każdy ze składników szukanej sumy może być równy tylko $0$ lub $1$, to otrzymujemy

$\lfloor \frac{2n}{p}\rfloor -2\lfloor \frac{n}{p}\rfloor =0$

Założenie, że $n⩾13$ pozwoli uprościć obliczenia dla drugiego i następnych składników sumy

$p>\frac{2n}{5}⟹\frac{(2n{)}^k}{p^k}<5^k⟹\frac{2n}{p^k}<\frac{25}{2n}\cdot {\left(\frac{5}{2n}\right)}^{k-2}⟹\frac{2n}{p^k}⩽\frac{25}{2n}⟹\frac{2n}{p^k}⩽\frac{25}{26}⟹\lfloor \frac{2n}{p^k}\rfloor =0$

Jeżeli $\lfloor \frac{2n}{p^k}\rfloor =0$, to również musi być $\lfloor \frac{n}{p^k}\rfloor =0$. Pokazaliśmy, że dla $n⩾13$ jest

$\sum _{k=1}^{\mathrm{\infty }}(\lfloor \frac{2n}{p^k}\rfloor -2\lfloor \frac{n}{p^k}\rfloor )=0$

Dla $n=8,9$ żadna liczba pierwsza nie należy do $(\frac{2n}{5},\frac{n}{2}]$.

Dla $n=10,11,12$ łatwo sprawdzamy, że liczba $5$ nie dzieli liczb $(\genfrac{}{}{0ex}{}{20}{10})=184756$, $(\genfrac{}{}{0ex}{}{22}{11})=705432$ oraz $(\genfrac{}{}{0ex}{}{24}{12})=2704156$.

Zatem dla $n⩾8$ liczba pierwsza $p\in (\frac{2n}{5},\frac{n}{2}]$ nie dzieli liczby $(\genfrac{}{}{0ex}{}{2n}{n})$.
□

Uwaga A47
Z przykładu A44 nie wynika, że w przedziale $(\frac{n}{2},\frac{2n}{3}]$ znajduje się choćby jedna liczba pierwsza $p$. Analogiczna uwaga jest prawdziwa w przypadku przykładu A46 oraz twierdzeń A43 i A45. Istnienie liczby pierwszej w określonym przedziale będzie tematem kolejnego artykułu.

Przykład A48
Pokazujemy i omawiamy wynik zastosowania twierdzeń A43 i A45 do współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2\cdot 3284}{3284})$. Można udowodnić, że granicę stosowalności obu twierdzeń bardzo dokładnie opisuje warunek $p>\sqrt{2n}$, co w naszym przypadku daje $p>\sqrt{2\cdot 3284}\approx 81.04$.

Pokaż przykład

Wybraliśmy współczynnik dwumianowy $(\genfrac{}{}{0ex}{}{2\cdot 3284}{3284})$ dlatego, że w rozkładzie tego współczynnika na czynniki pierwsze występują wszystkie liczby pierwsze $p⩽107$, 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ż $\sqrt{2\cdot 3284}\approx 81.043$, 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.

Poniżej wypisaliśmy wszystkie liczby pierwsze $p⩽3284$, które występują w rozwinięciu współczynnika dwumianowego $(\genfrac{}{}{0ex}{}{2\cdot 3284}{3284})$ 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ń A43 i A45 nie można stosować bez ograniczeń dla coraz większych liczb $k$.

2⁶, 3⁸, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59², 61², 67, 71, 73², 79², 83, 89, 97, 101, 103, 107, 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 $(\genfrac{}{}{0ex}{}{2\cdot 3284}{3284})$ na czynniki pierwsze.

Czytelnik łatwo sprawdzi, że największą wartością liczby $k$, dla jakiej można jeszcze stosować twierdzenie A43, jest $k=39$. Podobnie największą wartością liczby $k$, dla jakiej można jeszcze stosować twierdzenie A45, jest $k=40$. Wartości te i odpowiadające im przedziały zostały pogrubione, aby uwidocznić granicę stosowania tych twierdzeń. Łatwo odczytujemy, że twierdzenia A43 i A45 można stosować dla liczb pierwszych $p$ spełniających warunek $p>81.09$. Co bardzo dokładnie pokrywa się z warunkiem $p>\sqrt{2\cdot 3284}\approx 81.04$

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 $(\genfrac{}{}{0ex}{}{2\cdot 3284}{3284})$ na czynniki pierwsze.

$k$	$\frac{3284}{k+1}$	$p\in (\frac{3284}{k+1},\frac{3284}{k+\frac{1}{2}}]$	$\frac{3284}{k+\frac{1}{2}}$	$\frac{3284}{k}$
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	{107}	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

□