2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Общая формула последовательности
Сообщение13.04.2021, 22:04 


16/08/20
34
Пусть рассматриваются $n$-битные числа, где $n$ — нечётное. Зададим последовательность чисел таким образом: $x_0=00...01$ (единица), $x_{k+1}=x_{k}\oplus x'_{k}$, где $\oplus$ действует побитово, а $x'$ получается из $x$ циклическим сдвигом на единицу влево (например, $x=101$, тогда $x'=011$). Через некоторое количество итераций $T(n)$ получится число $11...10$ (это $\bar{x_0}$). Я хочу найти формулу для $T(n)$.
Например, при $n=3$:
$x_0=001$
$x_1=011$
$x_2=101$
$x_3=110$
Следовательно, $T(3)=3$.
Для $n=5$:
$x_0=00001$
$x_1=00011$
$x_2=00101$
$x_3=01111$
$x_4=10001$
...
$x_{13}=00110$
$x_{14}=01010$
$x_{15}=11110$
то есть $T(5)=15$.

 Профиль  
                  
 
 Re: Общая формула последовательности
Сообщение13.04.2021, 22:13 
Заслуженный участник


27/04/09
28128
Практический совет: найдите $T(n)$ для большого количества первых $n$ и поищите в OEIS этот префикс. Может найтись та самая последовательность, и тогда там будут ссылки на что-нибудь полезное насчёт неё, в том числе что-то насчёт формулы может быть указано.

По $T(3) = 4 - 1$ и $T(5) = 16 - 1$ создаётся впечатление, что может быть $T(n) = 2^{n - 1} - 1$, проверьте.

 Профиль  
                  
 
 Re: Общая формула последовательности
Сообщение13.04.2021, 22:43 


16/08/20
34
Да, я думал об этом, что-то не находил. Сейчас по-другому поискал — 3,_,15,_,7,_,63, и нашлось https://oeis.org/A038553

 Профиль  
                  
 
 Re: Общая формула последовательности
Сообщение14.04.2021, 09:05 


21/05/16
4292
Аделаида
Слишком мало элементов, лучше посчитать ещё примерно пять.

 Профиль  
                  
 
 Re: Общая формула последовательности
Сообщение14.04.2021, 12:51 


16/08/20
34
Всё нормально, у меня есть и следующие элементы, там всё сходится.

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

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



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

Сейчас этот форум просматривают: Alex Krylov


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

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