Покрытие арифметическими прогрессиями

[Dmitry_]

Помогите, пожалуйста, с задачей.

Даны $n$ арифметических прогрессий вида:

$(2i+1)k + x_{i},~~~~ i = 1..n, k > 0$

Начала прогрессий $x_{i} > 0$ мы можем произвольно варьировать.
Задача состоит в том, чтобы покрыть этими $n$ прогрессиями $m(n)$ — максимально возможное число подряд идущих целых чисел начиная с $1$ (число покрыто, если оно принадлежит хотя бы в одной из этих прогрессий).

Например, что сразу приходит в голову:
$m(n) \approx LCM_{i=1..n}(\{2i+1\})$

Но это очень много, существуют ли лучшие решения этой задачи ?

Численные расчеты вроде показывают, что:
$m(n) \approx Cn$

[ИСН]

Линейный-то сделать легко. Кладём каждую следующую последовательность так, чтобы она накрывала первую дырку среди предыдущих.

[Dmitry_]

ИСН, спасибо за ответ, но мне не понятно является ли это лучшим случаем ?
Или в лучшем случае (в котором $m(n)$ максимально возможно для данного $n$) мы получим что-то вроде $nlogn$ из-за зависимости от распределения простых чисел?

Т. е., если я правильно Вас понял, то следующий алгоритм дает линейный порядок роста для $m(n)$:
1)Произвольно берем любую из еще не использованных последовательностей и для нее $x_{i}$ делаем равным первому еще не покрытому числу.
2)Отмечаем текущую последовательность как используемую, повторяем Шаг 1.

Если это так, то не понятно почему $m(n) \approx Cn$ ?

[ИСН]

Dmitry_ в сообщении #1140624 писал(а):

ИСН, спасибо за ответ, но мне не понятно является ли это лучшим случаем ?

Да вот чёрт его знает.

Dmitry_ в сообщении #1140624 писал(а):

Если это так, то не понятно почему $m(n) \approx Cn$ ?

Это-то просто. Каждая последовательность нам добавила как минимум одно число? Добавила.

[Dmitry_]

Неожиданный ответ Я думал, что это простая задача и существуют какие-то известные результаты.

Тогда можно спросить будет ли:

$$a = LCM_{i=1..n}(\{(2i+1)k + x_i\}) + 1$$

для фиксированного $k > n$ являться верхней оценкой для $m(n)$ ?

[ИСН]

Они, может, и есть, просто мне не известны. Вы погодите, вдруг кто знающий зайдёт.
LCM - оценка явно дико завышенная.

[svv]

Знаю, как обеспечить $m(n)=2n-2$:
...,15,13,11,9,7,5,3,A,B,3,5,7,9,11,13,15,...
Число показывает, из какой оно прогрессии. A и B — из двух самых старших прогрессий, используемых для затыкания дырки в середине.

LCM здесь важно, но значит совсем не то. Это период, после которого вся картина покрытости/непокрытости повторяется.

Условия «$k>0$», «$x_i>0$», «начиная с $1$» лишние совершенно. Мыслите бесконечные в обе стороны прогрессии, сдвигая которые как угодно, надо получить где угодно максимум покрытых мест подряд. Сдвинуть потом всё как целое, как Вам надо, можно всегда.

[Dmitry_]

svv, большое спасибо!
Т. е. Вы последовательно используете прогрессии от периода $(2(n-2)+1)$ к самому меньшему $3$, а потом затыкаете два оставшихся пробела оставшимися двумя прогрессиями ?
Меня очень сильно интересует случай, когда $m(n)$ наоборот - максимально.

На stackoverflow мне подсказали следующий способ:

Начинаем каждую из $\frac{n}{\log n}$ последовательностей в простых числах меньших n.
Тогда останутся непокрытыми:

1) Степени двойки (их примерно $\log n$)
2) Простые большие чем $n$

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

$LCM$ гарантирует, что $LCM+1$ будет точно непокрыто.

[svv]

Dmitry_ в сообщении #1140638 писал(а):

Т. е. Вы последовательно используете прогрессии от периода $(2(n-2)+1)$ к самому меньшему $3$, а потом затыкаете два оставшихся пробела оставшимися двумя прогрессиями ?

Ну, не обязательно, строить же можно и от центра к краям. Ещё раз призываю Вас не обращать внимание на Ваши ограничения, они совершенно не принципиальны. Можно строить всё хоть в отрицательной области, хоть вообще не привязываясь к ряду целых чисел (закрашивая каждую третью клеточку, потом каждую пятую и т.д.). Потом всегда можно показать на самую левую клеточку в ряду идущих подряд закрашенных и сказать: это 1.

Dmitry_ в сообщении #1140638 писал(а):

Меня очень сильно интересует случай, когда $m(n)$ наоборот - максимально.

Так и я к этому стремлюсь.

[Dmitry_]

svv, ограничения не принципиальны, просто так было легче моделировать на компьютере.
Получается, что максимально возможное $m(n)$ для выбранного $n$ это $m(n) = 2n-2$ ?

Не получается осмыслить почему это так... и как в этом случает быть с вышеприведенным примером ? (с stackoverflow)

[svv]

Dmitry_ в сообщении #1140642 писал(а):

Получается, что максимально возможное $m(n)$ для выбранного $n$ это $m(n) = 2n-2$ ?

Что Вы, это всего лишь наилучшее найденное на текущий момент. Сейчас ещё какой-нибудь участник этот рекорд побъёт.

[Dmitry_]

Извиняюсь, но хочу спросить, чтобы мне не запутаться в дальнейшем.
Под "побъёт рекорд" Вы понимаете то, что, возможно, существует $m'(n) < 2n-2$ ?

[svv]

Dmitry_ в сообщении #1140638 писал(а):

На stackoverflow мне подсказали следующий способ:

Начинаем каждую из $\frac{n}{\log n}$ последовательностей в простых числах меньших n.
Тогда останутся непокрытыми:

1) Степени двойки (их примерно $\log n$)
2) Простые большие чем $n$

Это непонятно, впечатление, будто они решают другую задачу.
Скажите, Вы согласны, что через $LCM(...)$ вся картина будет повторяться? Например, как ни располагать прогрессии с разностями $3,5,7$, через каждые $105$ будет полный повтор картины. (Если, конечно, либо прогрессии бесконечны в обе стороны, либо мы рассматриваем их там, где все прогрессии уже «вступили в игру»). А если согласны, я совершенно не понимаю, как понять замечания спецов со stackoverflow.

Dmitry_ в сообщении #1140646 писал(а):

Извиняюсь, но хочу спросить, чтобы мне не запутаться в дальнейшем.
Под "побъёт рекорд" Вы понимаете то, что, возможно, существует $m'(n) < 2n-2$ ?

Ничего не понимаю, почему «меньше»? Вам же надо покрыть как можно большее количество подряд идущих, разве не его мы называем $m(n)$?

[Dmitry_]

Да, я тоже считаю, что $LCM(...)$ это период повторений.

Возможно, из-за уровня моего английского они решали другую задачу
Не знаю можно ли тут выкладывать ссылки на другие сайты, но вот: http://mathoverflow.net/questions/24524 ... ogressions.

Мне нужно знать такое $m(n)$, что для данного $n$ не существует другого $m'(n) > m(n)$.

Первое, что мне пришло в голову - это как раз $LCM(...)$, т. к. $LCM(...)$+1 гарантировано непокрыто.


Т. е.

Сначала используем последовательности вида $p_{i}k$, где $p_i$ это простые меньшие $2n+1$ Всего мы задействуем порядка $\frac{n}{\log n}$прогрессий.
При этом у нас остаются непокрытыми степени двойки, их примерно $\log n $ штук. Соответственно из оставшихся $n-\frac{n}{\log n}$ прогрессий мы используем $\log n$.

Таким образом у нас остается примерно $n-\frac{n}{\log n} - \log n$ прогрессий и уже полностью покрыто примерно $n\log n$ последовательных чисел, т. е. $m(n) \geq n\log n$.

[svv]

Ну, в таком случае «побьют рекорд» — значит, что предложат решение, в котором $m'(n)$ больше моего. Вы тоже — человек, который потенциально может это сделать.

-- Чт июл 28, 2016 17:47:22 --

Dmitry_ в сообщении #1140652 писал(а):

Мне нужно знать такое $m(n)$, что для данного $n$ не существует другого $m'(n) > m(n)$.

Да, я понимаю.
Можно попробовать посчитать $m(n)$ истинные (с помощью компьютера) до хотя бы $n=10$ или $15$, а потом эту последовательность результатов поискать в энциклопедии целочисленных последовательностей (OEIS). Может, это какая-то известная последовательность, тогда про неё там можно найти разнообразную интересную информацию.