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

[Dmitry_]

svv, спасибо за помощь!
К сожалению, в OEIS такой последовательности нет.

[Dmitry_]

На mathoverflow сказали, что "очевидное" предположение о том что:
Если
$a = \operatorname*{LCM}\limits_{i=1,\,\ldots\,,\,n}(\{(2i+1)k + x_i\}) + 1$
То $a$ не принадлежит ни одной из $n$ прогрессий ошибочно.

Контрпример:
$n=2$, $k=6$, $x_1=1$, $x_2=3$, $u = LCM(3 \cdot 6+1, 5 \cdot 6+3)+1 = 628 =3 \cdot 209+1$

Анализируя контрпример, возникает следующий вопрос, что на счет:
$a = \operatorname*{LCM}\limits_{i=1,\,\ldots\,,\,n}(\{(2i+1)k\}) + x^{*},~~~x^{*} \notin \{x_i\}_{i=1,..,n},~~~x^{*} < k \text{?}$

[Sonic86]

Я думаю, что существует такое $n_0$, начиная с которого возможно покрытие всго $\mathbb{Z}$ конечным числом прогрессий, после доказательства этого задача сведется к конечному перебору.
Например,

$$ (\forall x\in\mathbb{Z})\left\[ \begin{cases} x\equiv 0\pmod{2} \\ x\equiv 3\pmod{4} \\ x\equiv 1\pmod{3} \\ x\equiv 5\pmod{6} \\ x\equiv 9\pmod{12} \end{cases} $$

Только у нас запрещены четные множители, но, мне кажется, что они ничем принципиально от остальных множителей здесь не отличаются. Просто $\sum\limits_{p\leqslant x}\frac{1}{p-1}\sim\ln\ln x$ растет медленно, потому придется потрудиться с поиском (расчет показывает, что достаточно множителей $3,5,7,11$).

[Батороев]

(Оффтоп)

Во-первых, первые числа $m(n)$ при заданных условиях "покрыть" нечем.
А во-вторых, если наплевать на первые числа, то чем не устраивают две прогрессии: $(k,x)=(1,1);(1,2)$?
Оффтоп из-за того, что может быть неправильно понял условие задачи.

[Sonic86]

(Оффтоп)

что-то никто ничего не пишет , а задачка-то интересная!

Чуть менее тривиальный пример - $n=30$ - тоже четное, но степень $2$ здесь уже 1.
Пример с начетным модулем мне пока построить не удалось, но я еще не подходил к компу (а так призываю всех попробовать!), сейчас напишу, почему это не просто.

Пусть $M$ - натуральное, $d|M,d>1$. Чтобы покрыть все $\mathbb{Z}$, достаточно покрыть $\mathbb{Z}_M$.
Прогрессия $x+dt, t\in\mathbb{Z}$ покрывает $\frac{M}{d}$ чисел.
Прогрессии $x+at, y+bt, t\in\mathbb{Z}$ пересекаются только если $\gcd(a,b)|x-y$, причем в этом случае они пересекаются по прогрессии с коэффициентом $\mathrm{lcm}(a,b)$.
Будем считать, что мы можем у всех прогрессий $x_d+dt$ можем выбрать $x_d$ так, что если у любых двух различных прогрессий коэффициенты $d$ не взаимно просты, то прогрессии не пересекаются. Это вряд ли возможно в общем случае, но, похоже, в нашем случае, это оказывается близко к истине.
Обозначим $C_d=\{a:(\exists t) a\equiv x_d+dt \pmod M\}$. Надо, чтобы $U=\bigcup\limits_{d>1}=\mathbb{Z}_M$.
В предположении выше, мы можем по формуле включений исключений оценить число элементов в $U$:
$|U|=\sum\limits_{d}C_d-\sum\limits_{d_1<d_2}|C_{d_1}\cap C_{d_2}|+...+(-1)^{k-1}\sum\limits_{d_1<...<d_k}|C_{d_1}\cap ...\cap C_{d_k}|+...$
По предположению $C_{d_1}\cap C_{d_2}$ непусто только если $d_1\perp d_2$, и тогда $C_{d_1}\cap C_{d_2}=С_{d_1d_2}$ (не тот $C_{d_1d_2}$, обозначенный выше, а просто некий класс вычетов по модулю $d_1d_2$, надеюсь, это не вызовет проблем )
Тогда
$|U|=\sum\limits_{P_1(d)}|C_d|-\sum\limits_{P_2(d)}|C_d|+...+(-1)^{k-1}\sum\limits_{P_k(d)}|C_d|+...$,
где $P_k(d)$ означает "$d$ содержит как минимум $k$ простых различных делителей".
Положим $M=\prod\limits_{k=1}^sp_k^{a_k}$. Далее ограничимся случаем $s=4$ и будем считать, что в формуле включений-исключений разность 3-го и 4-го слагаемого неотрицательна
Тогда $|U|\geqslant \sum\limits_{d:d=p^k,k>0}\frac{M}{d}\geqslant M\Leftarrow$
$L_s=\sum\limits_{k=1}^s\sum\limits_{j=1}^{a_k}\frac{1}{p_k^j}=\sum\limits_{k=1}^s\frac{1-p_k^{-a_k}}{p_k-1}\geqslant 1$
Если устремить $a_k\to\infty$, то $L_4=\sum\limits_{k=1}^s\frac{1}{p_k-1}=\frac{1}{2}+\frac{1}{4}+\frac{1}{6}+\frac{1}{10}=1+\frac{1}{60}>1$. $L_3<1$, именно поэтому взято $s=4$
$L_4>1\Leftrightarrow \sum\limits_{k=1}^4\frac{p_k^{-a_k}}{p_k-1}<\frac{1}{60}$.
Подбором на компе у меня получились оптимальные $a_k=5;3;2;1$, т.е. $M=3^5\cdot 5^3\cdot 7^2\cdot 11^1\approx 1,6\cdot 10^9$.
Число $M$ довольно большое, потому явно покрытие всего $\mathbb{Z}_M$ подобрать трудно. Но зато получается, что искомое ТС $m(M)=\infty$, значит и для всех $x\geqslant M$ $m(x)=\infty$, после чего остается хоть перебором на компе найти $m(x)$ для конечного числа $x<M$, после чего задача становится теоретически неинтересной
Также получается, что $M$ - скорее всего минимальный аргумент, при котором $m(x)$ бесконечна. Но тоже строго обоснования еще нет. Вот наше дело найти явное покрытие $\mathbb{Z}_M$ или обосновать его существование строго.

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

чем не устраивают две прогрессии: $(k,x)=(1,1);(1,2)$?

Требуются прогрессии только с нечетными неединичными коэффициентами.

[Sonic86]

Задачу пока не решил, а программу написать не получается по техническим причинам.
Пока придумал только следующее:
Можно для простоты искать только $M$ вида $p_2...p_k,$ (по формуле выше получается $p_k=29$, а $M\approx 10^9$ - увеличивается).
Для упрощения расчетов можно представлять элементы $\mathbb{Z}_M$ через вычеты по модулям $p_j$ - так удобнее вычислять мощности пересечения прогрессий.
Можно также превратить задачу в геометрическую: каждой точке $x=(a_j \bmod p_j), j=1,...,s$ можно поставить в соответствие точку $(a_j)$ многомерного кирпича $K$ размерами $p_2\times ... \times p_k$. Прогрессиям будут соответствовать гиперплоскости $\alpha_J:\{ x_j = a_j, j\in J$. Задача тогда формулируется следующим образом: надо покрыть прогрессиями $\alpha_J$ весь кирпич $K$, причем все $J$ должны быть различны, $J\neq \varnothing$, $J\subseteq\{2,...,k\}$ - множество номеров координат. Этот подход удобен тем, что позволяет отказаться от простоты размеров $p_j$ и их различия. В результате можно строить разные покрытия кирпичей небольших мощностей и "щупать их руками". Например, у меня получилось покрыть все $\mathbb{Z}_3^n$ при $n\geqslant 4$.
Введем параметр для кирпичей $a=\max \{p_2,...,p_k\}$. Возьмем систему гиперплоскостей вида $\alpha_J : \{ x_j=\min(|J|,p_j)$ для $|J|\leqslant a$. Она покрывает $K$ достаточно неэффективно (если $|J_1|=|J_2|$, то $\alpha_{J_1}\cap\alpha_{J_2}\neq\varnothing$), но $\left|K\setminus\bigcup_{|J|\leqslant a} \alpha_j\right|\leqslant P(a)$ - многочлена от $a$, и тогда чаще всего достаточно брать взять все $\alpha_J$ при $|J|\leqslant a+1$ для покрытия всего $K$. Но вообще $|J|\leqslant k$ и тогда такое покрытие существует только при $k\leqslant \max \{p_2,...,p_k\}$, т.е. если размерность $K$ достаточно велика, а сами размеры достаточно малы. Таким способом мы не сможем покрыть кирпич размерами $3\times 5\times ... \times 29$. В этом смысле приведенное покрытие тривиально, а задача в геометрическом виде оказывается, видимо, нетривиальной.

Интересно, где ТС откопал эту задачу.

[Dmitry_]

Sonic86, Большое спасибо за Ваш труд! Задача возникла, как попытка оценить расстояния между простыми числами. К сожалению, я предполагал, что покрыть все множество натуральных чисел не получится, и, например, $m(n) = Cn$, что скорее всего выполняется в задаче, которую я рассматриваю, но из-за особого распределения $x_i$.