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

[DVN]

1. Дано n чисел. За один ход помечаются все числа, принадлежащие одному классу вычетов по простому модулю. Каждое простой модуль может быть использован не более одного раза. За сколько ходов все n чисел окажутся помеченными?

2. Аналогично, только простые модули больше 2 используются не более двух раз.

Я ответа не знаю, наверное, и никто не знает. Задачи трудные.
Для первой задачи число ходов не более $(n/2)/\ln (n/2)$, для второй - $n/\ln n$ .
Интересуют доказательные нижние оценки, сколько ходов точно недостаточно. Можно ли улучшить предположительную нижнюю оценку $sqr(n)/\ln sqr(n)$.

[Sonic86]

1. Я правильно понял, что для каждого простого модуля можно использовать лишь один класс вычетов? Если да, то даже если предположить, что каждый новый класс вычетов всегда вычеркивает только невычеркнутые числа, то необходимо сделать порядка $\frac{n}{p_1} + \frac{n}{p_2} + \ldots \sim n \sum\limits_{p \leqslant O(n^{1-\epsilon})} \frac{1}{p} \sim n \ln \ln n$ - столько ходов необходимо.

(формулы)

корень: $\sqrt{a}$

[DVN]

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

1. Я правильно понял, что для каждого простого модуля можно использовать лишь один класс вычетов? Если да, то даже если предположить, что каждый новый класс вычетов всегда вычеркивает только невычеркнутые числа, то необходимо сделать порядка $\frac{n}{p_1} + \frac{n}{p_2} + \ldots \sim n \sum\limits_{p \leqslant O(n^{1-\epsilon})} \frac{1}{p} \sim n \ln \ln n$ - столько ходов необходимо.

Да, поняли вы правильно. А предположили нет. По вашей оценке $n \ln \ln n$ для больших n выходит, что ходов требуется больше, чем n. Или это я не понял?

[Sonic86]

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

Да, поняли вы правильно. А предположили нет. По вашей оценке $n \ln \ln n$ для больших n выходит, что ходов требуется больше, чем n. Или это я не понял?

Действительно фигня какая-то надо еще подумать...

[Батороев]

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

1. Дано n чисел. За один ход помечаются все числа, принадлежащие одному классу вычетов по простому модулю. Каждое простой модуль может быть использован не более одного раза. За сколько ходов все n чисел окажутся помеченными?

Так ведь от чисел зависит.
Если все $n$ чисел принадлежат (чисто случайно) одному классу вычетов по модулю первого простого, то имеем всего один шаг.
Если допустим, числа - натуральные до $n$, то все числа пометим лишь, дойдя до последнего простого, не превосходящего $n$ (т.к. получаем некое подобие решета Эратосфена).

-- 15 дек 2011 18:17 --

Да и то, можем все и не пометить.

[Sonic86]

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

Так ведь от чисел зависит.

Имеются ввиду первые $n$ натуральных чисел.

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

Если допустим, числа - натуральные до $n$, то все числа пометим лишь, дойдя до последнего простого, не превосходящего $n$ (т.к. получаем некое подобие решета Эратосфена).

Вроде бы необязательно. Например, я могу делать так: на каждом шаге находим 1-е невычеркнутое число $r$ и вычеркиваем класс $r \pmod p$ (такой жадный алгоритм) - вдруг быстрее получится? (хотя сильно быстрее Эратосфена не получится). Хотя пример подобрать не могу - надо далеко уходить вперед...
Кстати, решето Эратосфена не вычеркивает число 1

[Sonic86]

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

Например, я могу делать так: на каждом шаге находим 1-е невычеркнутое число $r$ и вычеркиваем класс $r \pmod p$ (такой жадный алгоритм) - вдруг быстрее получится?

Впрочем, если числа $p$ перебирать по порядку, то получится как раз решето Эратосфена, просто смещенное на 1 влево. А если $p$ перебирать не по порядку, то это уже даже не жадный алгоритм будет

[DVN]

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

Если допустим, числа - натуральные до $n$, то все числа пометим лишь, дойдя до последнего простого, не превосходящего $n$ (т.к. получаем некое подобие решета Эратосфена).

Да, числа подряд до n. Что нужно доходить до последнего простого - это не так. В первом сообщении я указал, что

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

Для первой задачи число ходов не более $(n/2)/\ln (n/2)$

Можно предложить это в виде олимпиадной задачи, доказательство просто, но нужна догадка.

Как я указал, меня интересуют нижние границы, необходимое число и оно должно быть меньше достаточного (или по крайней мере равно, и равенство доказано).

[Sonic86]

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

Для первой задачи число ходов не более $(n/2)/\ln (n/2)$

Это значит для $n=10$ число ходов не более чем $3,1067$. Можете проиллюстрировать ходы?

[Батороев]

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

Да, числа подряд до n. Что нужно доходить до последнего простого - это не так. В первом сообщении я указал, что

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

Для первой задачи число ходов не более $(n/2)/\ln (n/2)$

Можно предложить это в виде олимпиадной задачи, доказательство просто, но нужна догадка.

Под условие Вашей задачи подпадает и решето Эратосфена.
В этом случае пометить все числа (а не найти простые, для чего предназачено решето Эратосфена) можно лишь, дойдя до последнего простого числа, не превосходящего $n$, а это примерно $\dfrac{n}{\ln n}$ шагов. При этом, как справедливо отметил Sonic86, число 1 не будет помечено (т.е. "миссия невыполнима"). Если Ваше доказательство не проходит для одного случая, в данном случае для решета Эратосфена, то оно уже не может быть верным.

[Cash]

Цитата:

Это значит для $n=10$ число ходов не более чем $3,1067$. Можете проиллюстрировать ходы?

Невыполнимая задача. Вычеркнуть по модулям 3 и 5 можно максимум $4+2$ чисел, из которых половина будут уже "заняты" двойкой. Итого за 3 хода не то что 10 чисел, но и 9 не получится просеять. Соответственно, даже 4 ходов недостаточно для вычеркивания всех 10.

-- Пт дек 16, 2011 09:36:38 --

Цитата:

Для первой задачи число ходов не более $(n/2)/\ln (n/2)$, для второй - $n/\ln n$

Странно, а почему верхняя оценка во второй задаче выше? Ничего не перепутано?

[DVN]

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

Цитата:

Это значит для $n=10$ число ходов не более чем $3,1067$. Можете проиллюстрировать ходы?

Невыполнимая задача. Вычеркнуть по модулям 3 и 5 можно максимум $4+2$ чисел, из которых половина будут уже "заняты" двойкой. Итого за 3 хода не то что 10 чисел, но и 9 не получится просеять. Соответственно, даже 4 ходов недостаточно для вычеркивания всех 10.

-- Пт дек 16, 2011 09:36:38 --

Цитата:

Для первой задачи число ходов не более $(n/2)/\ln (n/2)$, для второй - $n/\ln n$

Странно, а почему верхняя оценка во второй задаче выше? Ничего не перепутано?

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

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

-- Пт дек 16, 2011 11:15:24 --

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

Под условие Вашей задачи подпадает и решето Эратосфена.
В этом случае пометить все числа (а не найти простые, для чего предназачено решето Эратосфена) можно лишь, дойдя до последнего простого числа, не превосходящего $n$, а это примерно $\dfrac{n}{\ln n}$ шагов. При этом, как справедливо отметил Sonic86, число 1 не будет помечено (т.е. "миссия невыполнима"). Если Ваше доказательство не проходит для одного случая, в данном случае для решета Эратосфена, то оно уже не может быть верным.

Попробую внести ясность. Я предупреждал, что задача трудная, но насколько трудная, не уточнил. Вы верно подметили, что решето Эратосфена - это частный случай, когда из всех классов вычетов используются только нулевые. Предел для этого случая, как вы правильно заметили - $\dfrac{n}{\ln n}$. Если же говорить о конечных случаях, то нужно использовать числовую функцию $\pi(n)$ - количество простых, не превышающих n. Число ходов для конкретного n будет $\pi(n) +1$ (+1 - это упомянутая Sonic86 незачеркнутая единица). Естественно предположить, то для общего случая число ходов есть некая функция от функции $\xi(\pi(n))$ и число ходов для общего случая должно быть меньше, чем для частного. Легко показать, что это число не более $\pi(n/2) +2$ ,что при переходе к пределу даст озвученую мной оценку.

-- Пт дек 16, 2011 11:34:31 --

я в курсе скольких усилий стоило исследование поведения функции $\pi$ и понимаю, что просить точной формулы для $\xi(\pi)$ это изуверство. Но мне это и не нужно. Для меня достаточно, чтобы $\xi(\pi)$ было бы в рамках $1/n^2+kn$ для какого нибудь конечного k. Интуитивно я понимаю, что так должно быть и число решений не будет больше $\sqrt{n} / \ln \sqrt{n}$, но доказать это не могу.

[Sonic86]

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

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

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

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

Число ходов для конкретного n будет $\pi(n) +1$ (+1 - это упомянутая Sonic86 незачеркнутая единица).

Нет, число ходов решетом Эратосфена будет $\pi (n)$ - надо просто решето применить не к $1,\ldots ,n$, а к $2,\ldots, n+1$, а потом от всех классов вычетов $0 + p \mathbb{Z}$ отнять единицу.

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

Вы верно подметили, что решето Эратосфена - это частный случай, когда из всех классов вычетов используются только нулевые.

Кажется, решето Эратосфена - это даже в каком-то смысле общий случай. Действительно, ясно, что в лучшем случае нам нужно использовать первые $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)$.

[Батороев]

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

[Cash]

Цитата:

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

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