ProghubPH

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

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