Скажите,как решать такие задания? Научите,пожалуйста.

6 (№ 7) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы алгоритма больше 125. В ответе это число запишите в десятичной системе счисления.

Ответ 31

код на Ruby 22

for i in 1..40
    s = i.to_s(2)
    k = 0
    s.chars().each {|c| k += 1 if c == "1" }
    s += (k % 2).to_s + "0"
    p [i, s, s.to_i(2)]
end

вывод
[1, "110", 6]
[2, "1010", 10]
[3, "1100", 12]
[4, "10010", 18]
[5, "10100", 20]
[6, "11000", 24]
[7, "11110", 30]
[8, "100010", 34]
[9, "100100", 36]
[10, "101000", 40]
[11, "101110", 46]
[12, "110000", 48]
[13, "110110", 54]
[14, "111010", 58]
[15, "111100", 60]
[16, "1000010", 66]
[17, "1000100", 68]
[18, "1001000", 72]
[19, "1001110", 78]
[20, "1010000", 80]
[21, "1010110", 86]
[22, "1011010", 90]
[23, "1011100", 92]
[24, "1100000", 96]
[25, "1100110", 102]
[26, "1101010", 106]
[27, "1101100", 108]
[28, "1110010", 114]
[29, "1110100", 116]
[30, "1111000", 120]
[31, "1111110", 126]
[32, "10000010", 130]
[33, "10000100", 132]
[34, "10001000", 136]
[35, "10001110", 142]
[36, "10010000", 144]
[37, "10010110", 150]
[38, "10011010", 154]
[39, "10011100", 156]
[40, "10100000", 160]

Следующее число, большее 125₁₀, равно 126₁₀ или 1111110₂
Посмотрим, может ли оно получиться по заданному алгоритму.
На шаге 2а определяется "бит четности" путем подсчета количества единиц в двоичной записи числа. Если оно четно, к записи числа справа дописывается 0, если нечетно - единица.
На шаге 2б повторяются действия предыдущего шага.
Отбросим две правые цифры в записи 1111110₂ и посмотрим, как на получившемся числе работает предложенный алгоритм.
1111110 ⇒ 11111, число единиц нечетное, дописываем 1, получаем 111111, теперь число единиц четное, дописываем 0 и получаем 1111110, т.е. как раз то число, которое у нас было при переводе 126 в двоичную систему счисления.
А исходное число - это 11111₂ = 31₁₀
Ответ: 31