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

[DVN]

Cash в сообщении #516121 писал(а):

Цитата:

Не перепутано, имеется ввиду известные мне оценки на данный момент. Но предположить можно, что они могут быть и одинаковыми

Вот тогда действительно странно. Вторая задача содержит в себе первую. Соответственно оценка из первой автоматом переносится и на вторую задачу, а у Вас почему-то она еще и в 2 раза увеличивается...

Да, тут уже я протупил. Просто переносил условия с одной задачи на другую, и сделал неправильно. Там еще использовалась только половина простых модулей, распределенная примерно равномерно. Давайте пока вторую оставим, сосредоточимся на первой. Если понять, как решать первую, тогда можно подумать и о второй.

-- Пт дек 16, 2011 13:47:41 --

Sonic86 в сообщении #516084 писал(а):

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

Оценка-то предельная, для n стремящихся к бесконечности, а вы ее для n=10 применяете и делаете вывод о ее неверности. Нэ хорошо.

Ааа. Так об этом надо писать, чтобы не вводить народ в заблуждение. Сама запись $\frac{n}{2 \ln (n/2)}$ говорит о том, что оценка не асимптотическая, иначе можно было бы записать проще как $\sim \frac{n}{2 \ln n}$ поскольку $\ln (n/2) \sim \ln n$.

Приношу свои извинения, я не специально, а по неопытности.

[DVN]

Sonic86 в сообщении #516084 писал(а):

Кажется, решето Эратосфена - это даже в каком-то смысле общий случай. Действительно, ясно, что в лучшем случае нам нужно использовать первые $m$ простых чисел. Пусть для числа $p_j$ мы вычитаем класс $r_j + p_j \mathbb{Z}$. Пусть $x: (\forall j) x \equiv r_j \pmod{p_j}$. Тогда по китайском теореме об остатках такой $x$ существует и значит полное распределение чисел $1,\ldots ,n$ по классам $r_j + p_j \mathbb{Z}$ соответствует вычеркиванию чисел $x,x+1,\ldots ,x+n-1$ в решете Эратосфена. Значит, если обозначить $g(m)$ - максимальный пробел между числами, остающимися после выполнения просеивания натуральных чисел решетом Эратосфена простыми числами $p_1,\ldots ,p_m$, $g^{-1}(m)$ - искомая функция.
А про $g(m)$ мы знаем только то, что $g(m) \geqslant p_{m+1}-1$ и это не верхняя граница (вроде при $m>4$). А решение этой задачи почти равносильно верхней оценке скорости роста разности между простыми числами, так что задача действительно сложная (на задачу 2 можно забить сразу). Гипотеза о верхней оценке разности между простыми - $O(\ln ^2 m)$.

Не совсем понял (или совсем не понял). Числа $r_j$ - для классического решета Эратосфена все равны 0, следовательно и x=0. А вы сами заметили, что единица, она же x+1 не вычеркивается решетом. И как тогда быть увереным в

Sonic86 в сообщении #516084 писал(а):

полное распределение чисел $1,\ldots ,n$ по классам $r_j + p_j \mathbb{Z}$ соответствует вычеркиванию чисел $x,x+1,\ldots ,x+n-1$ в решете Эратосфена.

[Sonic86]

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

Не совсем понял (или совсем не понял). Числа $r_j$ - для классического решета Эратосфена все равны 0, следовательно и x=0. А вы сами заметили, что единица, она же x+1 не вычеркивается решетом. И как тогда быть увереным в

Да, где-то криво сформулировал Но, надеюсь, смысл понятен - если мы вычеркиваем какие-то классы $r_j + p_j \mathbb{Z}$, то для этих классов мы можем найти число, которое попадает во все классы, и, приняв его за нуль, получим сдвиг множества $\{ 1;...;n\}$, которое потом просеивается решетом (фу, блин, не получается сказать).
Пример: $n=3$ - числа $1;2;3$. Тогда $m=2$, классы $1+2\mathbb{Z}$ и $2+3\mathbb{Z}$ заключают в себе все числа $1;2;3$. С другой стороны, число $-1$ попадает в оба класса. Прибавляем ко всем числам по $1$, получаем числа $2;3;4$ - они распределяются по классам $2\mathbb{Z}$ и $3 \mathbb{Z}$ - просеиваются Эратосфеном.
Тут только формулу для сдвига нужно написать и все.

[DVN]

Батороев в сообщении #516118 писал(а):

Ну, так ведь $\pi (n)$ приблизительно и равно $\dfrac{n}{\ln n}$.
Если по условию Вашей задачи мы вольны (наверное, я не до конца понял условие ) сами выбирать тот или иной вычет, то используя $1\pmod 2$, после первого шага мы получим непомеченными только четные числа. Для их дальнейшего помечания по алгоритму решета Эратосфена потребуются простые до $\dfrac {n}{2}$. А их количество приблизительно и равно $\dfrac {\frac{n}{2}}{\ln \left({\frac{n}{2}}\right)}$. Но достаточно ли будет этого количества для полного помечания, не уверен, т.к. не помеченными останутся степени двойки.

Я завтра приведу доказательство того, что требуемое количество ходов не больше, чем $\pi(n/2)+2$, просто даю шанс найти его самому.

-- Пт дек 16, 2011 15:05:13 --

Sonic86 в сообщении #516154 писал(а):

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

Не совсем понял (или совсем не понял). Числа $r_j$ - для классического решета Эратосфена все равны 0, следовательно и x=0. А вы сами заметили, что единица, она же x+1 не вычеркивается решетом. И как тогда быть увереным в

Да, где-то криво сформулировал Но, надеюсь, смысл понятен - если мы вычеркиваем какие-то классы $r_j + p_j \mathbb{Z}$, то для этих классов мы можем найти число, которое попадает во все классы, и, приняв его за нуль, получим сдвиг множества $\{ 1;...;n\}$, которое потом просеивается решетом (фу, блин, не получается сказать).
Пример: $n=3$ - числа $1;2;3$. Тогда $m=2$, классы $1+2\mathbb{Z}$ и $2+3\mathbb{Z}$ заключают в себе все числа $1;2;3$. С другой стороны, число $-1$ попадает в оба класса. Прибавляем ко всем числам по $1$, получаем числа $2;3;4$ - они распределяются по классам $2\mathbb{Z}$ и $3 \mathbb{Z}$ - просеиваются Эратосфеном.
Тут только формулу для сдвига нужно написать и все.

В первом приближении понятно, непонятно каким же должно быть m, как выразить его через n?

[Sonic86]

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

В первом приближении понятно, непонятно каким же должно быть m, как выразить его через n?

Так я же написал:

Sonic86 в сообщении #516151 писал(а):

Значит, если обозначить $g(m)$ - максимальный пробел между числами, остающимися после выполнения просеивания натуральных чисел решетом Эратосфена простыми числами $p_1,\ldots ,p_m$, $g^{-1}(m)$ - искомая функция.

Естественно мне тоже непонятно.

[DVN]

Пробую понять то, что имел ввиду Sonic86. Пусть имеются m простых модулей $p_1,…,p_m$, которыми помечают числа. Требуется определить максимальную длину отрезка, на котором помеченные числа стоят подряд. Пусть $M= p_1…p_m$. Можно искать максимум на участке длинной М, потому что таким будет период повторения узора отмеченных чисел. Логично предположить, что максимальная длинна будет тогда, когда $p_1,…,p_m$ есть первые простые. По китайской теореме об остатках в этом промежутке найдется число x, которое помечается каждым из данных простых модулей. Sonic86 предлагает начать искать сплошной помеченный отрезок, начиная с числа x. Вот тут он чуть-чуть ошибся, поскольку число x+1 не помечено. Но если начать с x+2, то дальше идут только помеченные вплоть до $x+p_{m+1}$. Если взять m простых модулей не подряд, а пропустить какой-то $p_k<p_m$ , то число $x+p_k$ (равно как и $x+p_k^l$) будет не помечено и разобьет промежуток на меньшие части.
Все вышеизложенное дает основания полагать, что найденное мной решение (которое я обещал сегодня предъявить) и есть оптимальный вариант выбора для n чисел.
Пусть есть числа от 1 до n. Введем вторую нумерацию. Среднее число обозначим нулем и от него влево отрицательные, вправо положительные. Простые положительные числа по второй нумерации и будут представителями классов. Для оставшихся непомеченными 1 и -1 выберем два еще не используемых модуля.
Только сейчас заметил, что у Sonic86 от числа x-2 в обратном направлении идет симметричный сплошной промежуток, и если поставить две заплатки на x+1 и x-1, то тоже получим максимальный промежуток. Но у меня решение поэлегантней будет, не требуется искать формулу сдвига.
Все это хорошо, только как бы покороче доказать, что некоторое m классов недостаточно, чтобы были отмеченными n чисел подряд, как это коротко выразить, какова при этом связь m и n?
Я тут подумал о второй задаче в ее начальной формулировке. Как отметил Cash, для нее потребуется не больше ходов, чем для первой. Что если применить похожую стратегию, выбрать третью нумерацию так, чтобы сплошные участки были в притык. Если и между x+1 и $x_1+1$ будет простое число, то можно сэкономить пару заплат. Что скажете на предмет оптимальности данной стратегии?
Как мы тут выяснили, функция $g$ (или $\xi$) связана с расстоянием до следующего простого. По постулату Бертрана следующее после n простое лежит в промежутке до 2n. Также известно, что простые встречаются чаще, чем квадраты. Можно ли из этого сделать вывод, что функция $g^{-1}$ не может быть $1/n^2$?

[DVN]

Еще раз спасибо всем принявшим участие в обсуждении задач. Для тех, кто не в курсе: эти задачи есть иная форма широко известных в теории чисел проблем, одна из которых решена, вторая нет. Вторая – это четвертая проблема Ландау: ряд $x^2+1$ содержит бесконечное число простых чисел. В попытках доказать это обнаружилось сходство с задачей о бесконечном числе простых в арифметической прогрессии. Дирихле доказал сей факт, но его доказательство сложное. На данный момент нет элементарного доказательства теоремы Дирихле (насколько мне известно). Так возникла первая задача. С нее и начнем.
Дана арифметическая прогрессия A $a_n=mn+l$, $n\in \mathbb{Z}$, (m,l)=1. При $n\rightarrow\infty$ можно считать $a_n=m_n$ и номер $n=a_n/m$.
Член прогрессии, который делится на p, встретится не позднее p-го номера.
Если $p\mid a_n$, то $p\mid (a_n+tp)$, числа кратные p образуют класс $A_p$.
Можно задать взаимнооднозначное отображение $\varphi A\rightarrow N$, при котором сохраняется порядок следования элементов: если $a_i>a_j$, то $\varphi(a_i)>\varphi(a_j)$. При этом отношении класс кратных $A_p$ отображается на класс $N_{rp}$ вида $r+p\inmathbb{Z}$. Элементы, не входящие в классы $A_{p_j}$ отображаются на элементы, не входящие в классы $N_{rp_j}$.
Собственно, классы $N_{rp_j}$ и есть первая задача. Если мы доказываем некий факт для нее, то этот факт переносится и на прогрессию A.
Вернемся снова к прогрессии. Члены прогрессии могут быть разложены на простые сомножители. Мы будем помечать классы чисел, двигаясь от центрального члена прогрессии (n=0) вправо в сторону положительных n. Пусть первое появление каждого сомножителя $p_j$ означает появление соответствующего класса. Пусть $p_1,…,p_q$ есть ряд таких сомножителей - подряд идущих простых, которые образуют классы $A_{p_j}$. Пусть $a_n$ есть последнее число, сомножитель которого породил класс для $p_q$. Правее $a_n$ находятся помеченные и не помеченные числа. Очевидно, что среди чисел, меньших $a_n^2$, все непомеченные должны быть простые. Доказательство бесконечности простых чисел в прогрессии строится от противного: предполагается, что число простых конечно. Если все простые входят в $p_1,…,p_q$, то числа от $a_n$ до $a_n^2$ должны быть все помеченными. Длина сплошного помеченного промежутка $a_n^2/m$ – $ a_n/m$. Следовательно, такой же самый сплошной помеченный промежуток должен быть и в задаче 1, описанной в начале темы. Промежуток достаточно большой, была надежда, что верхняя оценка для задачи 1 не будет больше, что автоматически давало бы элементарное доказательство теоремы Дирихле. А потом я понял, что немного туплю. Что все проще. Нужно ориентироваться на нижнюю оценку. При показанном порядке пометки чисел первое непомеченное число бесконечное число раз окажется в заданном промежутке (на самом деле непомеченное число бесконечное число раз будет идти первым после соответствующего $a_n$), что сразу же вызовет противоречие с предположением конечности простых чисел. Это настолько очевидно, что у меня даже проблемы с доказательством этой очевидности – как это все выразить в словах. На этом с первой задачей завершим перейдем ко второй.

-- Пт дек 23, 2011 11:02:19 --

У Серпинского в "Что мы знаем и чего не знаем о простых числах" озвучено более широкое предположение: ряд $x^2+a$, где a натуральное, содержит бесконечное число простых. Попробуем доказать еще более широкое утверждение.

Теорема : Ряд целых чисел, представимых в виде $x^2-a$, где a - некоторое целое, содержит бесконечное число простых тогда, когда а не является полным квадратом.
Ясно, почему a не должно быть квадратом - в противном случае квадратичная форма разлагается на разность квадратов, и простых чисел в таком ряду максимум два.
Пусть ...,S(-n),...,S(-1),S(0),S(1),...,S(n),...,
где $S(x)=x^2-a$, и есть исследуемый ряд. При $n\rightarrow\infty$ отношение $S(n)/n^2$ будет стремиться к 1. Каждый член ряда S сдвинут на постоянную величину от соответствующего члена ряда квадратов. Поэтому у данного ряда должны иметься ряд свойств, похожих на свойства ряда квадратов. Укажем на них.

Свойство 1. Ряд S, как и ряд квадратов, симметричен относительно S(0), S(x)=S(-x).

Свойство 2. Из m подряд идущих членов ряда квадратов одно число принадлежит нулевому классу вычетов по нечетному модулю m. Остальные классы или представлены двумя числами, или не представлены вовсе. Следовательно, и в ряду S из m подряд идущих членов один класс вычетов по модулю m представлен однократно, остальные либо двукратно, либо не представлены.

Свойство 3: Числа S(x+km), где x фиксировано, а k пробегает все целые значения, принадлежат к одному и тому же классу вычетов по модулю m. Очевидно, что для каждого m существует m различных наборов такого вида.

Свойство 4: Среди чисел S(x+km) есть минимальное число, это либо S(0), либо находится от S(0) не далее (m-1)\2.

Свойство 5: Ряд квадратов и ряд S можно образовать последовательно прибавляя нечетные числа к S(0) - нулю и a соответственно. S(x+1)-S(x)=2x+1

Будем рассматривать только те классы чисел вида S(x+kp), у которых x кратен p и p – простое (попросту говоря числа класса делятся на p). Если S(0) входит в такой класс для p, то такой класс единственный. Также единственный класс для p=2. Для остальных p, которые являются сомножителями членов ряда S, из-за симметрии таких классов по два.

Можно задать взаимнооднозначное отображение $\varphi A\rightarrow N$, при котором сохраняется порядок следования элементов: если $a_i>a_j$, то $\varphi(a_i)>\varphi(a_j)$. При этом отношении класс кратных $S_k$ отображается на класс $ N_{rp}$ вида $r_j+k_j$. Элементы, не входящие в классы $S_{k_j}$ отображаются на элементы, не входящие в классы $N_{rp_j}$. Вот вам и вторая задача из начала темы. Там она задана с более жесткими условиями, чем для последовательности S. (если бы при этих условиях решалось, то и при более слабых тоже)
Очевидно, что задача для ряда S похожа на задачу об арифметической прогрессии, только условия помягче. Промежуток, в который не должны попасть неотмеченные больше $n^4-n^2$. А классов не больше, причем одна половина симметрична ( в некотором смысле) другой. Так что тот факт, что неотмеченные числа бесконечно много раз попадут в указанный промежуток, становится еще более очевидным, так что и доказывать неинтересно.
Если подходить формально, то я не доказал соответствующую теорему, но думаю, что показал достаточно ясно, что число простых в данных рядах бесконечно. Или у кого-то остались сомнения в этом?

[Sonic86]

Написано несколько сумбурно. Не сочтите за формальную придирку, но это важно.
Вы хотите доказать теорему Дирихле о простых в прогрессии чем-то вроде решета Эратосфена? Если да, то это так просто не получается (я сам так делал у меня дома валяется 20-страничный "опус". и где-то на форуме задача, к которой все свелось). Если Вы считаете, что доказали, напишите аккуратно
(еще потом вечером перепрочту, может протелепачу чего-нибудь)

[DVN]

Цитата:

Галочкин, Нестеренко, Шидловский, «Введение в теорию чисел»
В настоящее время мало что известно о распределении простых чисел в последовательностях, растущих быстрее арифметических прогрессий. В частности, ни для одного многочлена с целыми коэффициентами степени, большей 1, не доказано, что среди его значений при натуральных значениях аргумента содержится бесконечное множество простых чисел.

Я думаю, что скоро положение изменится и соответствующая цитата будет звучать так
Для многочленов с целыми коэффициентами степени, большей 1, среди его значений при целых значениях аргумента содержится бесконечное множество простых чисел тогда, когда среди этих его значений нет нулей.

О других последовательностях (например, числах Фибоначчи) не скажу, в ту сторону не смотрел, но может что и для них изменится в сторону определенности.

-- Пт дек 23, 2011 11:10:32 --

Тут в одной из тем товарищ из Минска предлагал алгоритм генерации простых чисел. Как ему объяснили, его алгоритм работает по принципу решета Эратосфена, только дольше. Но товарищ упирал на то, что ценность его алгоритма в новизне и не успокаивался. Я тут подумал, что применить принцип решета Эратосфена к последовательности x^2+a тоже в какой-то степени новшество. А больших простых можно достигнуть за более короткое время, чем обычным решетом. И в обратку- факторизация подобным образом. Извлекаем квадратный корень из числа и приводим его в требуемый вид x^2+a. А потом прочесываем решетом соответствующую последовательность и делим на невычеркнутые простые пробные делители, а их в два раза меньше будет, чем при обычном решете. И если делитель есть, то он встретится не позже 1/3 x.

-- Пт дек 23, 2011 11:12:33 --

Sonic86 в сообщении #518827 писал(а):

Написано несколько сумбурно. Не сочтите за формальную придирку, но это важно.
Вы хотите доказать теорему Дирихле о простых в прогрессии чем-то вроде решета Эратосфена? Если да, то это так просто не получается (я сам так делал у меня дома валяется 20-страничный "опус". и где-то на форуме задача, к которой все свелось). Если Вы считаете, что доказали, напишите аккуратно
(еще потом вечером перепрочту, может протелепачу чего-нибудь)

Протелепатьте . Я на это надеюсь. Или укажите места, которые надо расписать подробнее, может, на примерах.

[Sonic86]

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

Я думаю, что скоро положение изменится и соответствующая цитата будет звучать так
Для многочленов с целыми коэффициентами степени, большей 1, среди его значений при целых значениях аргумента содержится бесконечное множество простых чисел тогда, когда среди этих его значений нет нулей.

Не так:
Гипотеза Буняковского: если целочисленный многочлен неприводим над $\mathbb{Z}$ и НОД его значений равен 1, то он принимает бесконечно много простых значений.
Эта гипотеза написана в Серпинском где-то.

[nnosipov]

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

Свойство 2. Из m подряд идущих членов ряда квадратов одно число принадлежит нулевому классу вычетов по нечетному модулю m. Остальные классы или представлены двумя числами, или не представлены вовсе. Следовательно, и в ряду S из m подряд идущих членов один класс вычетов по модулю m представлен однократно, остальные либо двукратно, либо не представлены.

Если здесь речь идёт о числе решений сравнения $x^2 \equiv b \pmod{m}$, где $m$ --- нечётное число, то решений может быть много.

[DVN]

nnosipov в сообщении #518841 писал(а):

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

Свойство 2. Из m подряд идущих членов ряда квадратов одно число принадлежит нулевому классу вычетов по нечетному модулю m. Остальные классы или представлены двумя числами, или не представлены вовсе. Следовательно, и в ряду S из m подряд идущих членов один класс вычетов по модулю m представлен однократно, остальные либо двукратно, либо не представлены.

Если здесь речь идёт о числе решений сравнения $x^2 \equiv b \pmod{m}$, где $m$ --- нечётное число, то решений может быть много.

Пять подряд идущих квадратов $4 \equiv 4 \pmod{5}$, $9 \equiv 4 \pmod{5}$, $16 \equiv 1 \pmod{5}$, $25 \equiv 0 \pmod{5}$, $36 \equiv 1 \pmod{5}$ - один 0 , по две 4 и 1, нет 3 и 2.

-- Пт дек 23, 2011 13:11:03 --

Sonic86 в сообщении #518834 писал(а):

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

Я думаю, что скоро положение изменится и соответствующая цитата будет звучать так
Для многочленов с целыми коэффициентами степени, большей 1, среди его значений при целых значениях аргумента содержится бесконечное множество простых чисел тогда, когда среди этих его значений нет нулей.

Не так:
Гипотеза Буняковского: если целочисленный многочлен неприводим над $\mathbb{Z}$ и НОД его значений равен 1, то он принимает бесконечно много простых значений.
Эта гипотеза написана в Серпинском где-то.

Если нет нулей, то неприводим. НОД его значений равен 1 - значит нельзя вынести за скобки постоянный множитель, тут согласен недоформулировал. Выходит, боян.

[nnosipov]

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

Пять подряд идущих квадратов $4 \equiv 4 \pmod{5}$, $9 \equiv 4 \pmod{5}$, $16 \equiv 1 \pmod{5}$, $25 \equiv 0 \pmod{5}$, $36 \equiv 1 \pmod{5}$ - один 0 , по две 4 и 1, нет 3 и 2.

Если модуль $m$ --- простое число, то Вы правы, а если $m$ --- всего лишь нечётное число, то Вы ошибаетесь.

[Sonic86]

Прочел.
Ну короче понятно, я почти все уже сказал. Пусть $E$ - множество значений многочлена $f(x)$. $r_j+p_j\mathbb{Z} 0 \leqlsant r_j <p$ - множество классов вычетов, являющихся решениями сравнения $f(x) \equiv 0 \pmod p$. Выбираем отрезок $I_A=[A;A^2]$ и тогда Вы хотите показать, что для любого сколь угодно большого $A$ множество $(E \cap I_A) \setminus (\bigcup\limits_{r_j,p_j<A}(r_j+p_j\mathbb{Z}) \cap I_A)$ непусто. И это проблематично

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

Это настолько очевидно, что у меня даже проблемы с доказательством этой очевидности – как это все выразить в словах.

Вот у меня тоже проблемы были
Каких-то уточнений я здесь больше не увидел. Так что вот так - никак
Т.е. если Вы хотите развить эту конструкцию, мучайте пока хотя бы теорему Дирихле. Попытайтесь выразить мысль подробно в виде цепочки определений, теорем, лемм и т.п. Здесь, по-моему, интересно сформулировать очевидность в виде какого-то инструмента доказательства. Хотя я боюсь, что конструкция доказательства известна каждому, кто хоть раз пытался доказать эти теоремы, хотя в книгах ее нет. Я могу выложить свою унылую писанину, но лучше попробуйте сами, у меня все равно ничего нетривиального нет - буду только ею глаза мозолить.

[DVN]

Я все-таки путано написал, вы правы. Много ненужного, без чего можно обойтись. Попробую донести идею на конкретном примере.
Конкретный пример: прогрессия l=3, m=5.
3 8 13 18 23 28 33 38 43 48 53 58 63 68 73 78 83 88 93 98
Процедура пометки начинается с 3. Тут простой сомножитель
p1=3, отмечаем каждое третье число. Все они делятся на 3.
Потом переходим к следующему числу 8. Тут простой сомножитель p2=2, отмечаем каждое второе число. Все они делятся на 2.
Следующее число 13, отмечаем каждое 13-е.
Следующее число 18. Его простые делители 2 и 3, которые нами уже отмечены. Это первое такое число, но очевидно, что в дальнейшем они будут встречаться все чаще и чаще.
С процедурой зачеркивания, надеюсь, понятно – обычное решето.
Пусть последнее число, для которого она выполнена 93. Были отмечены все кратные 3,2,13,23,7,11,19,43,53,29,17,73,83,31. Всего пройдено 19 чисел, значит, все простые не большие 19 уже должны быть отмечены. Посмотрим на числа, меньшие $19^2=361$:
3,...,93, 98,103,108,113,118,…,353,358. В этом промежутке все неотмеченные числа должны быть простыми: (до 93 нетмеченных просто нет,а два делителя больших 19 у остальных чисел быть не может, значит, по крайней мере один меньше 19 и поэтому все составные отмечены.
Если мы предположим, что число простых конечно и число обработанных чисел равно наибольшему простому, то в таком промежутке неотмеченных быть не должно, просто потому, что простые уже кончились. Если продолжать процедуру, то такой промежуток растет и очень быстро. Причем растет он и в том случае, когда очередное число не имеет новых сомножителей (а это происходит все чаще и чаще) и число отмеченных не меняется. Получается, что ближайшее место, где возможно первое неотмеченное число «удаляется» быстрее, чем идет зачеркивание, как-то так. Для меня очевидно, что такого не может быть, но как все это выразить математически?
Неотмеченные числа располагаются приблизительно равномерно. Чтобы узнать вероятное возможное число неотмеченных чисел на каком-то сравнительно большом промежутке, надо плотность неотмеченных чисел умножить на количество чисел в промежутке. При отработке нового сомножителя плотность уменьшается в $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 раз, что противоречит отсутствию на нем неотмеченных.

-- Сб дек 24, 2011 11:38:51 --

Sonic86 в сообщении #518961 писал(а):

Прочел.
Ну короче понятно, я почти все уже сказал. Пусть $E$ - множество значений многочлена $f(x)$. $r_j+p_j\mathbb{Z} 0 \leqlsant r_j <p$ - множество классов вычетов, являющихся решениями сравнения $f(x) \equiv 0 \pmod p$. Выбираем отрезок $I_A=[A;A^2]$ и тогда Вы хотите показать, что для любого сколь угодно большого $A$ множество $(E \cap I_A) \setminus (\bigcup\limits_{r_j,p_j<A}(r_j+p_j\mathbb{Z}) \cap I_A)$ непусто. И это проблематично [/size]

Мне еще надо медленно разобраться в этом. Не так уж быстро я соображаю, как вы.

-- Сб дек 24, 2011 11:41:25 --

nnosipov в сообщении #518906 писал(а):

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

Пять подряд идущих квадратов $4 \equiv 4 \pmod{5}$, $9 \equiv 4 \pmod{5}$, $16 \equiv 1 \pmod{5}$, $25 \equiv 0 \pmod{5}$, $36 \equiv 1 \pmod{5}$ - один 0 , по две 4 и 1, нет 3 и 2.

Если модуль $m$ --- простое число, то Вы правы, а если $m$ --- всего лишь нечётное число, то Вы ошибаетесь.

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