2014 dxdy logo

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

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




 
 Найти член последовательности
Сообщение11.06.2009, 17:43 
Пусть последовательность - упорядоченное множество с аовторяющимися элементами 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] $? Хотя бы рекуррентную... :? А то интересно очень. Или доказать, что такой формулы нет (хотя этого факта не хотелось бы :wink:).

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

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

 
 
 
 Re: Найти член последовательности
Сообщение11.06.2009, 18:29 
Первая - четность количества единиц в двоичной записи числа $n-1$, вроде как.

Влад.

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

 
 
 
 Re: Найти член последовательности
Сообщение11.06.2009, 18:43 
Аватара пользователя
Это последовательность Морса-Туэ.
В явном виде $j$-й элемент равен четности количества единичных битов в двоичной записи числа $j$.

 
 
 
 Re: Найти член последовательности
Сообщение11.06.2009, 18:50 
Спасибо. А сама чётность может быть вычислена только алгоритмически?

 
 
 
 Re: Найти член последовательности
Сообщение11.06.2009, 18:59 
Аватара пользователя
arseniiv в сообщении #221432 писал(а):
Спасибо. А сама чётность может быть вычислена только алгоритмически?

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

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

 
 
 
 Re: Найти член последовательности
Сообщение11.06.2009, 19:37 
Тогда, думаю, самая быстрая реализация на 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;

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

 
 
 
 Re: Найти член последовательности
Сообщение11.06.2009, 20:04 
Аватара пользователя
Ну, думаю, реализация с циклом вместо рекурсии будет быстрее.

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

 
 
 
 Re: Найти член последовательности
Сообщение11.06.2009, 23:02 
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++, так что код может содержать ошибки.

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

 
 
 
 Re: Найти член последовательности
Сообщение29.08.2009, 01:33 
http://community.livejournal.com/ru_declarative/86764.html

 
 
 
 Re: Найти член последовательности
Сообщение29.08.2009, 10:19 
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] $? Хотя бы рекуррентную... :? А то интересно очень. Или доказать, что такой формулы нет (хотя этого факта не хотелось бы :wink:).

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

 
 
 [ Сообщений: 12 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group