Сплошные нули и единицы

[kthxbye]

Пусть

$$T(n,k)=T(\left\lfloor\frac{n}{2}\right\rfloor,k - n\bmod 2), n > 1, k > 0$$

$$T(n,0)=1 + (1 - n\bmod 2)T(\left\lfloor\frac{n}{2}\right\rfloor,0), n > 1, T(1,0)=1$$

аналогично

$$R(n,k)=R(\left\lfloor\frac{n}{2}\right\rfloor,k - (n+\left\lfloor\frac{n}{2}\right\rfloor)\bmod 2), n > 3, k > 0, R(2,1)=1$$

$$R(n,0)=1 + (1 - (n+\left\lfloor\frac{n}{2}\right\rfloor)\bmod 2)R(\left\lfloor\frac{n}{2}\right\rfloor,0), n > 0, R(0,0)=1$$

Известно, что $T(n,k)-1$ - длина сплошной последовательности нулей между $k$-той справа парой единиц в двоичной записи $n$, а $R(n,k)$ - длина $(k+1)$-ой справа сплошной последовательности идентичных битов в двоичной записи $n$.

Как это можно доказать?

[arseniiv]

kthxbye в сообщении #1510697 писал(а):

Как это можно доказать?

Можно попробовать в обратную сторону, предположительным образом открытия: вывести для этих двух величин рекуррентные соотношения и сравнить с данными. Может быть сразу совпадут, может быть после небольшой доводки, а вот если упрутся… но мы же не знаем наверняка — вдруг повезёт?

-- Ср мар 24, 2021 00:11:18 --

kthxbye в сообщении #1510697 писал(а):

$$T(n,k)=T(\left\lfloor\frac{n}{2}\right\rfloor,k - n\bmod 2), n > 1, k > 0$$

Ну вот эта часть например по мне читается на ура: Чтобы узнать $T(n, k)$, нам надо отгрызть от $n$ самый правый бит, сделав $n'$, и отнять его от $k$, сделав $k'$, и посчитать $T(n', k')$. И это вроде не сходится со словесным описанием: там $k$ считает пары единиц, а тут оно уменьшилось уже от выкидывания одной единицы.

-- Ср мар 24, 2021 00:16:27 --

А, там не пары единиц, идущих подряд, а мы как раз считаем расстояние между ними? Тогда прекрасно согласуется. А как только мы отсчитали нужное число единиц, мы утыкаемся во второе равенство, которое считает правые нули, а именно наибольшую степень двойки, на которое делится число. И это равенство опять согласуется: мы откидываем нули и прибавляем единицу к результату, пока не наткнёмся на единичный бит и перестанем зависеть от $T$ для следующего префикса.

-- Ср мар 24, 2021 00:18:02 --

В общем читается превосходно, стоит лишь нам подумать о реализации вычисления такой величины с помощью динамического программирования (допустим): придём вот ровно к тому же.