Найти член последовательности

[arseniiv]

Пусть последовательность - упорядоченное множество с аовторяющимися элементами 0 и 1, и для двух последовательностей определена конкатенация $ + $. А также имеются следующие определения:
$ a_0 = (0) $
$ \bar a_0 = (1) $
$ a_{n + 1} = a_n + \bar a_n $
$ \bar a_{n + 1} = \bar a_n + a_n $
Очевидно, что длина последовательности $ \operatorname{Length} a_n = 2^n $.
Можно ли найти формулу для j-го члена последовательности $ a_n [\kern-0.15em[ j ]\kern-0.15em] $? Хотя бы рекуррентную... А то интересно очень. Или доказать, что такой формулы нет (хотя этого факта не хотелось бы ).

-- Чт июн 11, 2009 20:48:47 --

Можно оставить только два определения, а $ \bar a_n $ ввести как обращение (заменить 0 на 1 и обратно) $ a_n $, сути это не сменит, но, может, упростит всё это

[vlad239]

Первая - четность количества единиц в двоичной записи числа $n-1$, вроде как.

Влад.

[Xaositect]

Ну, $a_n$ - это вектор значений функции $x_1\oplus x_2\oplus\dots\oplus x_n$
Так что $a_n[j]$ - это четность количества единиц в двоичной записи $j$ (если $j$ считать от 0 до $2^n-1$)

[maxal]

Это последовательность Морса-Туэ.
В явном виде $j$-й элемент равен четности количества единичных битов в двоичной записи числа $j$.

[arseniiv]

Спасибо. А сама чётность может быть вычислена только алгоритмически?

[Xaositect]

arseniiv в сообщении #221432 писал(а):

Спасибо. А сама чётность может быть вычислена только алгоритмически?

А как еще можно вычислять?

Функция примитивно-рекурсивная, если это чем-то поможет.

[arseniiv]

Тогда, думаю, самая быстрая реализация на Pascal будет:

function ThueMorse(X: Longword): Boolean;
begin
  if X=0 then
    Result := False
  else if Odd(X) then
    Result := not ThueMorse(X shr 1)
  else
    Result := ThueMorse(X shr 1);
end;

Интересная последовательность всё-таки. Странная

[Xaositect]

Ну, думаю, реализация с циклом вместо рекурсии будет быстрее.

А последовательность интересная, да. Фрактальная.

[venco]

arseniiv в сообщении #221442 писал(а):

Тогда, думаю, самая быстрая реализация на Pascal будет:

Делением пополам надо вычислять такие вещи:

function ThueMorse(X: Longword): Boolean;
begin
  X = X xor (X shr 32);
  X = X xor (X shr 16);
  X = X xor (X shr 8);
  X = X xor (X shr 4);
  X = X xor (X shr 2);
  X = X xor (X shr 1);
  if (X and 1) = 0 then
    Result := False
  else
    Result := True
  end
end;

Я обычно пишу на C/C++, так что код может содержать ошибки.

[arseniiv]

Ну, Odd(x) ≡ (x and 1)=1
Алгоритм какой-то не очень хороший. Лучше бы ему не зависеть от длины числа, да и эти 6 операторов были бы хороши в цикле

[hlg]

http://community.livejournal.com/ru_declarative/86764.html

[VAL]

arseniiv в сообщении #221427 писал(а):

Пусть последовательность - упорядоченное множество с аовторяющимися элементами 0 и 1, и для двух последовательностей определена конкатенация $ + $. А также имеются следующие определения:
$ a_0 = (0) $
$ \bar a_0 = (1) $
$ a_{n + 1} = a_n + \bar a_n $
$ \bar a_{n + 1} = \bar a_n + a_n $
Очевидно, что длина последовательности $ \operatorname{Length} a_n = 2^n $.
Можно ли найти формулу для j-го члена последовательности $ a_n [\kern-0.15em[ j ]\kern-0.15em] $? Хотя бы рекуррентную... А то интересно очень. Или доказать, что такой формулы нет (хотя этого факта не хотелось бы ).

А если бы вы участвовали (или хотя бы следили) в Математическом марафоне, у Вас не возник бы этот вопрос
См. ММ108