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

Question

for i = 0..2^k-1
  output (i ^ (i - 1))

Где ^ --- операция побитового xor-а.

Answer 1

i-ый бит следующего числа хранит сумму по модулю два всех битов предыдущего числа, номера чьих позиций меньше либо равны i bi = (\sum{j=0}^{i} a_i) % 2

Answer 2

Без первого элемента последовательность совпадает seq(k), где seq(k) = seq(k-1), 2^k - 1, seq(k-1) seq(1) = 1

Answer 3

Следующее число всегда больше предыдущего

Answer 4

Битовое представление следующего числа отличается от предыдущего только в одном бите

Вопрос из теста Алгоритмы

Программирование / junior

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