Алгебра и теория чисел :: занятие 11 (04.05.2010)

Занятие 1 (04.05.2010)
Практические задачи. Задачи про простые числа
Лекция. (Теория) Аналитическая теория чисел
Лекция. (Практика) Вычисление $\pi(x)$

Занятие 1 (04.05.2010)
Задачи про простые числа ps pdf
primepi.Число простых чиселps pdf
primeset.Простые разбиенияps pdf
(Теория) Аналитическая теория чисел
План лекции
  1. Факты из математического анализа
    1. Оценка ряда $f(1) + f(2) + \cdots + f(n)$ с помощью $\int\limits_{1}^{n}f(x) dx$ для монотонных функций
    2. Теорема о $\sum\limits_{n \le x} \ln{n} = x\ln{x} - x + O(\ln{x})$
    3. Теорема о $\sum\limits_{n \le x} \frac{1}{n\ln{n}} = \ln{\ln{x}} + c + o(1)$
    4. Формула Тейлора
    5. Теорема о $\frac{1}{\ln{(n + 1)}} = \frac{1}{\ln{n}} - \frac{1}{n\ln^2{n}} + O(\frac{1}{n^2})$
  2. Теорема Чебыш\"ева
    1. Функция $\theta(n) = \sum\limits_{p \le n} \log p$, теорема о $\theta(n) = O(n)$
    2. Теорема о $\sum\limits_{p \le n} \frac{\log p}{p} = \log n + O(1)$
    3. Существование констант $c_1$ и $c_2$, таких что $c_1 n < \theta(x) < c_2 n$
    4. Существование констант $c_1$ и $c_2$, таких что $c_1 \frac{x}{\log x} < \pi(x) < c_2 \frac{x}{\log x}$
  3. Постулат Бертрана
    1. Теорема о $C_{2n}^{n} > \frac{4^n}{2\sqrt{n}}$
    2. Теорема о $\prod_{p \le n} < 4^n$
    3. Теорема о $\pi(2n) - \pi(n) \ge 1$
    4. Теорема Финслера о $\frac{n}{3 \log{2n}} < \pi(2n) - \pi(n) < \frac{7n}{5\log{n}}$ при $n > 1$
  4. Уточнение констант в теореме Чебыш\"ева
    1. * Теорема о $\pi(x) > \frac{2}{3} \frac{x}{\log x}$ при $x > 3$
    2. * Теорема о $\pi(x) < \frac{8}{5} \frac{x}{\log x}$ при $x > 3$
  5. Сумма обратных к простым
    1. Преобразование Абеля для $\sum_{i=1}^{n} a_i b_i$
    2. Теорема о $\sum \frac{1}{p} = \log \log p + c + o(1)$
  6. Асимптотический закон распределения простых чисел
    1. Теорема о $\pi(x) \sim \frac{x}{\ln{x}}$ (без док-ва)
    2. * Теорема о $p_n \sim n\ln{n}$
    3. * Теорема о $n\ln{n} < p_n < n(\ln{n} + (1 + o(1))\ln{\ln{n}})$ (без док-ва)
(Практика) Вычисление $\pi(x)$
План лекции
  1. Алгоритм вычисления $\pi(x)$