Две проблемы (теория чисел, вычеты)

[Sonic86]

DVN в сообщении #519199 писал(а):

Для меня очевидно, что такого не может быть, но как все это выразить математически?

Ну будем повторяться: в этом и состоит Ваша задача А я буду помогать.
Вот будем разбираться с $a_n=3+5n. n \in \mathbb{N} \cup \{ 0\}, 3,5$ - простые.
Сначала выберем $A$ и рассмотрим все $a_n \leqslant A$. У Вас $A=100$. Для каждого $a_n \leqslant A$ есть наименьшее $p:p \mid a_n$. У Вас $p=3;2;13;...$.

DVN в сообщении #519199 писал(а):

Всего пройдено 19 чисел

Обозначим количество $a_n:a_n \leqlsant A$ буквой $r$. У Вас $r=19$. Чему равно $r$ в общем случае? Напишите формулу.
Обозначим список простых $P(A)$

DVN в сообщении #519199 писал(а):

все простые не большие 19 уже должны быть отмечены.

А есть ли в списке

DVN в сообщении #519199 писал(а):

3,2,13,23,7,11,19,43,53,29,17,73,83,31.

число $5$? Почему? В случае произвольной прогрессии $mn+l$ каких чисел не будет в этом списке.
Еще заметим, что в $P(A)$ попадают числа $p:p>r$. Можно ли их как-то описать? Нужны ли эти числа $p$ нам при доказательстве того, что если $a_n \leqslant r^2$ и для всех $p$ $p \not \mid a_n$, то $a_n$ - простое?

DVN в сообщении #519199 писал(а):

Если мы предположим, что число простых конечно и число обработанных чисел равно наибольшему простому, то в таком промежутке неотмеченных быть не должно, просто потому, что простые уже кончились. Если продолжать процедуру, то такой промежуток растет и очень быстро.

Мы рассматриваем промежуток $[1;r^2]$. Сколько натуральных чисел в этом промежутке? Сколько чисел $a_n$ в этом промежутке? Напишите формулу - это и будет точное описание того, насколько быстро растет промежуток.

DVN в сообщении #519199 писал(а):

В этом промежутке все неотмеченные числа должны быть простыми: (до 93 нетмеченных просто нет

Так, то есть числа $a_n: a_n \leqslant A$ мы исключаем из рассмотрения сразу (иначе пропадет равномерность распределения на краю). Значит рассматриваем промежуток $[A;r^2]$, причем у нас $r=r(A)$ (точнее $r = \pi (A)$). Какова длина этого промежутка? сколько в нем чисел $a_n$ - напишите опять же формулу.

DVN в сообщении #519199 писал(а):

Неотмеченные числа располагаются приблизительно равномерно. Чтобы узнать вероятное возможное число неотмеченных чисел на каком-то сравнительно большом промежутке, надо плотность неотмеченных чисел умножить на количество чисел в промежутке. При отработке нового сомножителя плотность уменьшается в $p_{n+1}-1/ p_{n+1}$ раз, а промежуток чисел без отмеченных увеличивается в $p_{n+1}^2/ p_n^2$ раз. Поэтому вероятное число неотмеченных чисел на промежутке такой длинны вырастет в $p_{n+1}(p_{n+1}-1)/ p_n^2$раз, больше чем в 1 раз, что противоречит отсутствию на нем неотмеченных.

Это начните сначала формализовывать сами. Тут смысл в том, что у плотность распределения - она в среднем, и у нее есть отклонения. Чем меньше отрезок, тем сильнее заметно отклонение. Ну самый простой и несколько даже глупый пример, что возьмем отрезок $[8 -\frac{1}{2};8+\frac{1}{2}]$ длиной $1$. $8+\frac{1}{2}<3^2$, а значит плотность простых на нем равна $1-\frac{1}{2}=\frac{1}{2}$. Однако $\frac{1}{2}$ - нецелое число, должно быть $0$ или $1$. Но это мы знали с самого начала - это следует из того, что длина отрезка равна $1$, т.е. плотность нам вообще никакой информации не дала.
Чуть более сложный пример: рассмотрим отрезок $[114-\frac{1}{2};126+\frac{1}{2}]$ длиной $14$. $127<13^2$, значит средняя плотность простых в нем равна $\rho = \left( 1-\frac{1}{2}\right)\left( 1-\frac{1}{3}\right)\left( 1-\frac{1}{5}\right)\left( 1-\frac{1}{7}\right)\left( 1-\frac{1}{11}\right) \approx 0,208$, а значит среднее число простых $=\rho L \approx 14 \cdot 0,208 \approx 2,9$, однако Вы можете проверить - в отрезке нет простых чисел вообще.
Если мы обозначим $\pi (x,P,a_n) = \sum\limits_{n:a_n \leqslant x, (\forall p \in P)p \not | a_n} 1$ - число чисел $a_n$, не превосходящих $x$, причем $a_n$ не делятся на все простые из конечного множества $P$, то функция $\pi (x,P,a_n)$ представляется в виде суммы линейной функции $\rho x$ и периодической компоненты. Если $T$ - период периодической компоненты, то мы можем утверждать, что любой отрезок длиной $T$ стабильно будет содержать $\rho \cdot T$ чисел $a_n$, не кратных всем $p \in P$ (если непонятно, простой пример: любой отрезок содержащий $30=2 \cdot 3 \cdot 5$ последовательных чисел содержит ровно $8$ чисел (а значит $\rho = \frac{8}{30}$) не кратных $p \in P =\{ 2;3;5\}$. Например: в $[1;29]$ - это $1;7;11;13;17;19;23;29$, в $[20;49]$ - это $23;29;31;37;41;43;47;49$ и т.п.). И тогда, если бы было $T<|[A;r^2]|$, то мы бы могли утверждать, что все-таки наш отрезок "слишком длинный" и значит стабильно содержит $\rho T$ простых. Вот длину отрезка вычислите Вы , а я вычислю $T$ в самом простом случае: $P=\{ p_1;\ldots;p_r\} \Rightarrow T=p_1 \cdot \ldots \cdot p_r >r!$. Вот и сравните, что растет быстрее.
Т.е. рассуждение с плотностью простых без учета оценки отклонений от этой плотности не проходит ну никак. Значит надо заниматься оценкой отклонений - насколько она велика. У Вас в доказательстве этого точно нет Тем более неясно, как меняется плотность, когда Вы увеличиваете отрезок с добавлением нового простого числа $p_{n+1}$ в $P$

UPD:

DVN в сообщении #519199 писал(а):

Неотмеченные числа располагаются приблизительно равномерно. Чтобы узнать вероятное возможное число неотмеченных чисел на каком-то сравнительно большом промежутке, надо плотность неотмеченных чисел умножить на количество чисел в промежутке. При отработке нового сомножителя плотность уменьшается в $p_{n+1}-1/ p_{n+1}$ раз, а промежуток чисел без отмеченных увеличивается в $p_{n+1}^2/ p_n^2$ раз. Поэтому вероятное число неотмеченных чисел на промежутке такой длинны вырастет в $p_{n+1}(p_{n+1}-1)/ p_n^2$раз, больше чем в 1 раз, что противоречит отсутствию на нем неотмеченных.

Вообще, интересный подход. При добавлении в 1-й отрезок (к которому применяется решето) 2-й отрезок $I_A=[A;r^2]$ изменяется как $I_{A+1}=(I_A \setminus [A;A+m]) \cup [r^2;(r+m)^2]$, длина последнего отрезка получается $2mr+m^2$ - линейно зависит от $r$. Можно пытаться доказать, что каждый такой отрезок достаточно длинный, что содержит простое число (при $a_n=n$) получается, что мы пытаемся доказать что-то вроде гипотезы Лежандра о $(\exists p)p \in [x;x+\sqrt{x}]$, а для прочих прогрессий - что-то вроде обобщенной гипотезы Лежандра, которую еще сформулировать надо...

[DVN]

прогрессия $l=3$, $m=5$.
$a_n=3+5n. n \in \mathbb{N} \cup \{ 0\}$
Обозначим количество $a_n:a_n\leqlsant A$ буквой $r$ ,$ r\sim an/m$.
Обозначим список простых $P(A)$
В случае произвольной прогрессии $mn+l$ в $P(A)$ не будет делителей числа $m$. Все простые не больше $r$ попадут в $P(A)$ .
Типа доказательство: возьмем $p$($p$- простое) чисел подряд $0,1,…,p-1$. Умножим каждое на $m$. Каждое из полученных делится на какое-то из чисел $1,…,p$. Прибавим к каждому произведению$ l=3$. По идее каждое из вновь полученных чисел должно делиться на какое-то из чисел $1,…,p$. И среди них должно быть число, делящееся на $p$. Поскольку получившиеся числа есть p первых числа прогрессии, то значит число кратное $p$ встретися не позже p-го числа. (Знал бы теорию групп – привел бы подходящую теорему)
При $A \to \infty$ в $P(A)$ попадут все простые числа (кроме делителей $m$)
В $P(A)$ попадают числа $p:p>r$ . На них можно не заморачиваться.
Мы рассматриваем промежуток $[1;r^2]$ . Натуральных чисел в этом промежутке,как ни странно, ровно $r^2$ . Чисел $a_n$ в этом промежутке $\sim r^2/m$.
Не думаю, что числа $a_n: a_n \leqslant A$ нужно исключать из рассмотрения сразу (иначе пропадет равномерность распределения на краю).
Я сначала тоже думал так, но потом изменил точку зрения. Во-первых, нет никакого края, прогрессию легко продолжить на отрицательные числа. Мы имеем дело с произвольными прогрессиями с различными $m$ и $l$, как-то странно было бы, если бы они имели какую-то особенность для неотмеченных чисел все сразу в начале (или в какой-то другой выделенной точке, все точки равноправны по отношению к отмеченным числам). Если на прямой каждое натуральное число обозначить членом какой-то прогрессии, отметить классы для $P(A)$ , а затем убрать числа, оставив только отметки, то уже невозможно будет определить, где было начало, какое было $l$, разве что $m$ определяется по отсутствию некоторых классов отметин.
Во-вторых, у нас всегда $A \to \infty$, мы его стремимся сделать как можно большим (это только в примерах оно маленькое). Я знаю, что в данном промежутке может встретится участок без неотмеченных длиной как минимум $r$, но есть еще $r-1$ участков такой же длинны, которые скомпенсируют этот. И при росте $r$ их количество растет. Когда я говорил о равномерности неотмеченных чисел, то я имел ввиду такую же равномерность, как например у простых чисел. Хотя они распределены неравномерно, но когда переходим к пределам, то некая относительная равномерность таки наблюдается.
Ну и в-третих, эта добавка по сути не повлияет, только формулы станут более громоздкими (подробности ниже).
Если мы обозначим $\pi (x,P,a_n) = \sum\limits_{n:a_n \leqslant x, (\forall p \in P)p \not | a_n} 1$ - число чисел $x$ , не превосходящих $a_n$ , причем $a_n$ не делятся на все простые из конечного множества $P(A)$ , то функция $\pi (x,P,a_n)$ представляется в виде суммы линейной функции $\rho x$ и периодической компоненты. $T$ - период периодической компоненты.
При таком обозначении отношение $\pi (x,P,a_n)/x$ и есть плотность неотмеченных на промежутке $[1;x]$. При $x \to \infty$ плотность будет стремиться к $\rho$ – этой буквой и обзовем предел плотности. ($\rho_x$ будем обозначать плотность на промежутке $[1;x]$, $\pi (x,P,a_n)=\rho x$ ). Этот предел просто подсчитать. Отдельное непомеченное число есть решение системы сравнений из китайской теоремы об остатках. Количество всевозможных таких систем и есть количество неотмеченных чисел. Всего в системе столько сравнений, сколько простых в $P(A)$ . Каждое сравнение можно записать$p_j-1$ способом. Итого на один период $T$ приходится $\prod\limits_{p_j:P(x)} (p_j-1)$ неотмеченных чисел. Отсюда легко понять, как меняется плотность, когда мы увеличиваем отрезок с добавлением нового простого числа $p_{n+1}$ в $P$. Период $T$ увеличивается в $p_{n+1}$ раз, а число неотмеченных в $p_{n+1}-1$ раз. Так я и написал вчера. Мысль пришла почти в последний момент, с моей скоростью печатания расписывать не было никакой возможности. Одна надежда была на телепатию. Но видать недостаток времени на телепатии сказывается губительно.
Как меняется промежуток $[1;r^2]$ при добавлении $p_{n+1}$ в $P$:
Предыдущее значение $r^2= p_n^2$, промежуток был длинной $p_n^2 /m$, стал $p_{n+1}^2 /m$. На $m$ можно сократить переходя с отношению, что я и сделал. И опять во вред пониманию. После указанных разъяснений можно повторить сказанное вчера.

-- Вс дек 25, 2011 12:51:47 --

При отработке нового сомножителя плотность уменьшается в $p_{n+1}-1/ p_{n+1}$ раз, а промежуток чисел без отмеченных увеличивается в $p_{n+1}^2/ p_n^2$ раз. Поэтому вероятное число неотмеченных чисел на промежутке такой длинны (это $\pi (r^2,P,a_n) /x$ ) вырастет в $p_{n+1}(p_{n+1}-1)/ p_n^2$ раз, больше чем в 1 раз, что противоречит отсутствию на нем неотмеченных.

-- Вс дек 25, 2011 13:01:20 --

Помните в-третих? Если промежуток начинать не с 1 , а с $p_n$, то промежуток чисел без отмеченных увеличивается в
$p_{n+1}^2-p_{n+1}/p_n^2-p_n$ раз. Сократить на $p_{n+1}$ уже не получается. Думается, что все равно изменение вероятного числа неотмеченных чисел на промежутке при добавлении будет больше, чем в 1 раз, что квадрат превозможет. Простая прикидка $13^2-13/11^2-11=1.418>13/12=1.083$
Отмечу еще один момент. Можно изменить процедуру вычеркивания: вводить в простые в порядке возрастания. Для каждого введенного $p_j$ считать вероятное количество неотмеченных $\pi (p_j^2,P,a_n)/x$ в промежутке $[1;p_j^2]$. С каждым введенным числом эта вероятность растет с коэффициентом большим 1, значит, как и геометрическая прогрессия ряд вероятностей стремится к бесконечности. Это тоже противоречит предположению о конечном числе простых в арифметической прогрессии.

-- Вс дек 25, 2011 13:05:49 --

Последнее добавление увидел только что. Буду разбираться.