ProghubPH

Какие утверждения справедливы для последовательности чисел, генерируемых следующим алгоритмом?

 один вариант
for i = 0..2^k-1
  output (i ^ (i - 1))

Где ^ --- операция побитового xor-а.
i-ый бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i bi = (\sum{j=0}^{i} a_i) % 2
Без первого элемента последовательность совпадает seq(k), где seq(k) = seq(k-1), 2^k - 1, seq(k-1) seq(1) = 1
Следующее число всегда больше предыдущего
Битовое представление следующего числа отличается от предыдущего только в одном бите