Округление log_2(n) (ищу доказательство)

[kthxbye]

Для определённых преобразований потребовалось получше узнать характер $[\log_2(n)]$ (т.е. округление до ближайшего целого). Если округляем вниз, там все прекрасно, а тут начинаются страшные вещи. Прежде всего, находим A004257, где ничего вменяемого, увы, нет. После некоторых экспериментов замечаем, что

$$a(n)=[\log_2(n)]=[n>1]\cdot(a\left(\lfloor{n\over2}\rfloor\right)+1+[n=a_2(k)+1]\cdot[1-a_1(k+1)]\cdot[k\geqslant0])$$

где $a_1$ это A004539, $a_2$ это A084188, а $[P]$ равно $1$ если условие истинно (ну и $0$ если ложно).

Если существует элементарное доказательство, то оно само по себе сможет пролить свет на много других интересных вещей, так что если поделитесь, буду очень признателен.

[B@R5uk]

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

...потребовалось получше узнать характер...

А что именно вы понимаете под этими словами?

-- 02.08.2019, 19:42 --

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

Если округляем вниз, там все прекрасно...

Приведите, пожалуйста, пример того, что у вас хорошо получилось, чтобы провести аналогию с тем, что именно вам нужно.

[kthxbye]

B@R5uk в сообщении #1408367 писал(а):

А что именно вы понимаете под этими словами?

Ну, собственно, найти как минимум одно удобное рекуррентное соотношение.

B@R5uk в сообщении #1408367 писал(а):

Приведите, пожалуйста, пример того, что у вас хорошо получилось, чтобы провести аналогию с тем, что именно вам нужно.

Хорошо получилось не у меня, а вообще:

$$a(n)=\lfloor\log_2(n)\rfloor=[n>1]\cdot(a\left(\lfloor{n\over2}\rfloor\right)+1)$$

Работать с такой штукой - одно удовольствие.

[Евгений Машеров]

Округление до ближайшего целого получается из округления вниз, если к аргументу прибавить 0.5

(Оффтоп)

не литра

[kthxbye]

Евгений Машеров в сообщении #1408371 писал(а):

Округление до ближайшего целого получается из округления вниз, если к аргументу прибавить 0.5

Благодарю за участие и упоминание об этом замечательном факте (пусть и в несколько курьезной манере)! Возможно я плохо вижу, но мне кажется

$$[\log_2(n)]=\lfloor\log_2(n)+\frac{1}{2}\rfloor=\lfloor\log_2(n)+\log_2(\sqrt{2})\rfloor=\lfloor\log_2(\sqrt{2}n)\rfloor$$

это единственное, чем нам это может быть полезно (и о чем не забыли в A004257).

[wrest]

kthxbye
Ну так корень из двух это иррациональное число, такшта записывается оно последовательностью цифр похожей на случайную не только в десятичной но и в двоичной системах счисления.
То что вы хотите это "двоичный порядок".
Посмотрим на аналогию.
$\sqrt{10}=3,16227766016837933...$
Округленный до ближайщего целого десятичный логарифм будет перескакивать на следующую единицу
Между $3$ и $4$
Между $31$ и $32$
Между $316$ и $317$
Между $3162$ и $3163$
Между $31622$ и $31623$
Между $316227$ и $316228$
И так далее.
Так же, но только по корню из двух будет перескакивать двоичный логарифм:
$\sqrt{10}_2=1,011010100000100_2...$
Между $1_2$ и $10_2$
Между $10_2$ и $11_2$
Между $101_2$ и $110_2$
Между $1011_2$ и $1100_2$
И так далее.

Какую закономерность вы тут хотите найти?

P.S. А, ну вы об этом и писали вроде. Так это (то что вы хотите доказать), кажись, самоочевидно, разве нет?
Вот у вас есть запись корня из двух в двоичном виде. Ясно что если вы сколько-то (например $k$) первых цифр, умножаете на $2^k$ то поскольку у вас там оставался какой-то ненулевой остаток, то двоичный логарифм этого произведения округлится в меньшую сторону, т.е. округлится к $k$, а следующее значение уже к $k+1$.
А почему корень именно квадратный? А потому, что округляете "дрлижайшего целого" вы вниз если до $1/2$ и вверх после $1/2$. Если бы округляли, скажем, до $1/3$ вниз, а после $1/3$ вверх, то корень нужен был бы кубический

[B@R5uk]

Обозначим для удобности:

$$a(n)=\lfloor\log_2(n)\rfloor$$

$$b(n)=[\log_2(n)]$$

Можно заметить, что $b(n)$ иногда на единицу больше, чем $a(n)$. Это происходит в тех случаях, когда:

$$\log_2(n)-a(n)>\frac{1}{2}$$

$$n>\sqrt{2}\cdot2^{a(n)}$$

$$n^2>2^{2a(n)+1}$$

$$a(n^2)=2a(n)+1$$

В чём проблема работать рекуррентно с $a(n)$, а проверяя неравенство (равенство) и, если надо, прибавляя единицу, получать $b(n)$?

[kthxbye]

wrest в сообщении #1408379 писал(а):

Так же, но только по корню из двух будет перескакивать двоичный логарифм:
$\sqrt{10}_2=1,011010100000100_2...$
Между $1_2$ и $10_2$
Между $10_2$ и $11_2$
Между $101_2$ и $110_2$
Между $1011_2$ и $1100_2$
И так далее.

Вижу! Вот что значит наглядный пример. Ещё раз пробежался по A084188, там (оказывается!) как раз об этом.

B@R5uk в сообщении #1408415 писал(а):

В чём проблема работать рекуррентно с $a(n)$, а проверяя неравенство (равенство) и, если надо, прибавляя единицу, получать $b(n)$?

Прелестно! Можно пойти ещё дальше и заметить, что

$$b(n)=a(n^2)-a(n)$$

Если честно, $n^2$ в роли индекса казалось чем-то запретным.

Выражаю огромную благодарность wrest и B@R5uk за участие и оказанную помощь!