Бесконечное семейство перестановок натуральных чисел

[kthxbye]

Для начала нам нужны несколько бинарных функций.

Пусть

$$\ell(n)=\left\lfloor\log_{2}(n)\right\rfloor$$

Пусть также $\operatorname{wt}(n)$ - это A000120, число единиц в двоичной записи $n$ или же бинарный вес $n$.

Кроме того, $\operatorname{val}(n)$ - это A007814, максимальная степень двойки на которую делится $n$.

А теперь пусть $\left\lbrace a(n,m)\right\rbrace$ это последовательность чисел $k$, таких, что

$$\ell(k)-\operatorname{wt}(k)=\ell(\frac{k}{2^{\operatorname{val}(k)}}+2m)$$

.

Пусть также

$$b(n,m)=\left\lfloor\frac{a(n,m)}{2^{\operatorname{val}(a(n,m))+1}}\right\rfloor+1$$

Докажите, что для любого $m\geqslant0$ (имеется ввиду что $m$ - это некоторое целое неотрицательное число) последовательность $\left\lbrace b(n,m)\right\rbrace$ является перестановкой натуральных чисел.

[Dendr]

Немного сумбурно, потому что решал буквально в окне ответа темы, но вроде бы так...

Очевидно, что любое натуральное число можно записать в виде $k=(2p+1)2^r$, где $p, r$ - целые неотрицательные числа. Сразу можно записать $val(k)=r$.
Заметим, что логарифм округляется вниз, поэтому из нечетного аргумента можно свободно вычесть единицу и далее получить:
$\left\lfloor\log_2{(2p+1)}\right\rfloor=\left\lfloor\log_2{2p}\right\rfloor=\left\lfloor1+\log_2{p}\right\rfloor=\left\lfloor\log_2{p}\right\rfloor+1$
А тогда:
$\l(k)=\left\lfloor\log_2{(2p+1)}\right\rfloor+r=\left\lfloor\log_2{p}\right\rfloor+r+1$
В правой же части вычисляется величина $\l(2p+1+2m)=\left\lfloor\log_2{(p+m)}\right\rfloor+1$.

Наконец, $wt(a)=wt(2p+1)=wt(p)+1$: нули в конце двоичной записи можем просто отбросить, после чего выделить особо единицу в первом разряде.

Тогда равенство, определяющее подходящие $k$, выглядит следующим образом:

$$\left\lfloor\log_2{p}\right\rfloor+r - wt(p) = \left\lfloor\log_2{(p+m)}\right\rfloor+1$$

Задавшись каким-то значением $m$, мы получаем функцию

$$r(p)=\left\lfloor\log_2{(p+m)}\right\rfloor-\left\lfloor\log_2{p}\right\rfloor+wt(p)+1$$

Разность логарифмов, конечно, неотрицательна, как и $wt(p)$ - поэтому правая часть строго положительна, причем определена для любого $p\ge0$. Значение этой функции определяет количество двоичных нулей, которое надо приписать к $2p+1$, чтобы получить какое-то значение элемента последовательности $a$.

Поскольку любое натуральное число $n$ можно определить через уникальную пару $(p,r)$ и наоборот, каждой паре неотрицательных чисел соответствует какое-то натуральное число, а для любого $p$ мы можем единственным образом определить $r_p=r(p)$, то, как мы видим, можно определить все элементы последовательности $a(n,m)$. Тогда $val(n,m)=r_p+1$, и формула

$$\left\lfloor\frac{2p+1}{2}\right\rfloor+1=p+1$$

определяет элементы последовательности $b(n,m)$ в некотором порядке. Благодаря тому, что добавлена единица, $p+1$ - натуральные числа и встречаются ровно по разу. Но это и есть определение перестановки натурального ряда.
ЧТД.