Не только комбинаторика

[Andrey A]

Возьмем для начала $k$ произвольных двоичных знаков, из которых хотя бы один $\neq 0$, и будем строить последовательность единиц и нулей по правилу $a_{n+k}=a_n-a_{n+1} \mod 2$, пока начальные знаки не повторятся. Пример: $110...\ \ (k=3)$. Получаем цикл $110(0101110)$. Всего возможны $2^3$ троек, но тройку $000$ таким способом не получить. Поэтому троек всего $2^3-1=7$, и все входят в циклическую последовательность из семи знаков. То же для $k=2,4$ и не только. Но уже в случае $k=5$ чтобы получить все $2^5-1=31$ пятерок потребуется три цикла длиной $3+7+21=31$ знаков:

$$11011(011);\ 10100(1110100);\ 11111(000010001100101011111).$$

Задача выросла из темы "Фибоначчи k-го уровня" (последний пост, случай $p=2$), только последовательности строятся в обратном направлении и требование "$k$ начальных единиц" снимается как частный случай. А вопрос следующий: сколько нужно циклов и какой длины чтобы "закрыть" все $(2^k-1)$ ненулевых комбинаций двоичных знаков длиной $k$? При желании можно продолжить на простые $p>2$.

Исправлено 27.09.2019

[Andrey A]

Наводящая мысль: циклы не равноправны. Следует всё же выделять цикл наибольшей длины $L$, поскольку для всех прочих циклов длиной $l_i$, если они имеются, выполняется $l_i \mid L$. Для $k=14$, к примеру, имеем $2^{14}-1=11811+3937+381+127+93+31+3$ и $3937 \cdot 3=381 \cdot 31=127\cdot 93=11811.$ То есть $2^{14}=\sigma (11811)$, но может быть и так: $2^9-1=73+73+73+73+73+73+73.$ Оно выполняется и для простых $p>2$, хотя это просто наблюдения. Всевозможные "видимо" и "вроде бы" пока опускаю.

[Null]

Чую ответом будет $2^l-1$, где $l$ - количество неприводимых сомножителей в разложении $P(x)=x^n+x+1$ над $Z_2$.
Причем если $P(x)=Q_1(x)Q_2(x)\dots Q_l(x)$ и $L_k(i)=\sum_{j=1}^{\deg(Q_k)} x^i_{kj}$,где $x_k_j$ - корни $Q_k$(у $P(x)$ кратных корней нет) в поле разложения $P$, то последовательности $L_k$ и все их нетривиальные суммы(всего $2^l-1$) будут ответом.

[Andrey A]

Null в сообщении #1418177 писал(а):

Чую ответом будет $2^l-1$, где...

Имеется в виду, что количество циклов – число вида $2^l-1$ для любого $k$? Ага, тогда для $p>2$ нужно предположить $\dfrac{p^l-1}{p-1}$, поскольку единица бывает всегда (почему-то кажется). Это бы сильно упрощало дело, но вот для $k=8$ имеем

$$2^8-1=63+63+63+63+3.$$

$5$ циклов, специально перепроверил. На всякий случай начальные знаки непересекающихся циклов:

$10000000(...)$
$10100000(...)$
$10010000(...)$
$10110000(...)$
$10110110(110)$

[Null]

Да,у меня ошибка, это все из за того что $\text{НОД}(2^2-1,2^6-1)=3$. Но базисных последовательностей будет $l$, а ответом будут различные всевозможные суммы их сдвигов.
Например при $k=8$ - базисные последовательности $(101)$(ваша 5тая) и $(100000111000010010001101100101101011101111001100010101001111110)$ (ваша 2рая). Остальные это 3 их суммы с учетом 3 возможных сдвигов.

[Andrey A]

Null
Можно брать за отправную точку цикл, включающий $k$ последовательных единиц. Он наибольший ( $\geqslant $ исключений пока не было) и содержит по предположению информацию о возможных $l_i$.
Идея с суммами хороша. Понравилось. В такой форме это было бы действительно решение, но как найти базисные последовательности только Вам ведомо. На всякий случай многочлен $x^n+x+1$ приводим по любому модулю для $n=3t+2\ (t=1,2,3,...)$

[Null]

Мои $l$ последовательностей задаются линейными реккурентами(рекуррентными последовательностями) соответствующими(эти многочлены характеристические для них) многочленам $Q_i$.
Если многочлен $Q$ степени $s$ неприводим в $Z_p$, то любая нетривиальная последовательность соответствующая $Q$ имеет цикл минимальной длиннны $p^s-1$ и генерирует все подпоследовательности длинны $s$ кроме нулевой.
Я предлагаю разложить многочлен $Q=x^n+x-1$(Ранее был он же но только в $Z_2$) на неприводимые множители $Q_1,\dots,Q_l$(пусть их степени $l_i$). Каждый многочлен соответствует последовательности $L_i$ с циклом длинны $p^{l_i}-1$. Если $T$ -оператор сдвига, то я утверждаю что $\{T^jL_i|i=1..l;j=0..l_i-1\}$ базис, а все {различные с учетом сдвигов} их суммы будут ответом. Тут полезно заметить что $\forall q,w \exists u: T^q L_i+T^w L_i=T^u L_i$(или $=0$)

[Andrey A]

Нельзя ли привести пример? Наиболее показательный на Ваш взгляд. И еще. Есть ли уверенность, что для простого $p>2$ общее решение выражается выражается в подобной форме?

[Null]

$n=9;p=3$
$x^9+x-1=(1 + x) (1 + x^2 + x^3 + x^4) (2 + 2 x + 2 x^2 + x^3 + x^4)\pmod 3$
Получаем 4 базовые последовательности(1 развалилась на 2 части - не ожидал):
$L_1=(12)$
$L_{21}=(1000210221001111011020001201120022220220)$
$L_{22}=(1112212110020121010122211212200102120202)$
$L_3=(10001221110022010010102210212110111121012000211222001102002020112012122022221202)$
Соответственно ответ ($T$ - сдвиг в лево)
Только $L_1$,$L_{21}$,$L_{22}$ или $L_3$ - 4 последовательности
$L_1$ и $L_{21}$ - 2 возможные различные суммы($L_{21}+L_1$ и $L_{21}+TL_1$).
$L_1$ и $L_{22}$ - 2 возможные различные суммы($L_{22}+L_1$ и $L_{22}+TL_1$).
$L_1$ и $L_3$ - 2 возможные различные суммы($L_3+L_1$ и $L_3+TL_1$).
$L_{21}$ и $L_3$ - 40 возможных различных сумм($L_3+T^iL_{21}, i=0..39$ ).
$L_{22}$ и $L_3$ - 40 возможных различных сумм($L_3+T^iL_{22}, i=0..39$ ).
$L_1$,$L_{21}$ и $L_3$ -80 сумм ($L_3+T^iL_{21}+T^kL_1, i=0..39, k=0..1$)
$L_1$,$L_{22}$ и $L_3$ -80 сумм ($L_3+T^iL_{22}+T^kL_1, i=0..39, k=0..1$)
Итого 250

[Andrey A]

Ok, спасибо! Надо разобраться.

[Null]

Весело начинается когда у многочлена есть кратные сомножители, для $p=2$ у этого многочлена их нет а вот $n=5;p=3$ надо изучить.