2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Не только комбинаторика
Сообщение24.09.2019, 16:08 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Возьмем для начала $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

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение26.09.2019, 14:36 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Наводящая мысль: циклы не равноправны. Следует всё же выделять цикл наибольшей длины $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$, хотя это просто наблюдения. Всевозможные "видимо" и "вроде бы" пока опускаю.

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение29.09.2019, 17:57 
Заслуженный участник


12/08/10
1609
Чую ответом будет $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$) будут ответом.

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение29.09.2019, 21:47 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
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)$

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение30.09.2019, 11:53 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение01.10.2019, 10:55 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение01.10.2019, 12:29 
Заслуженный участник


12/08/10
1609
Мои $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$)

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение01.10.2019, 15:28 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение02.10.2019, 08:24 
Заслуженный участник


12/08/10
1609
$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

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение02.10.2019, 09:57 
Заслуженный участник
Аватара пользователя


21/11/12
1870
Санкт-Петербург
Ok, спасибо! Надо разобраться.

 Профиль  
                  
 
 Re: Не только комбинаторика
Сообщение02.10.2019, 13:02 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group