интересная задача

Какбэ в исходной формуле содержится ответ. Чего ты привязался к OneBits? Это же ln2(n), округлённый вверх. Получается уравнение, которое можно решить численными методами.

Правда, чувствуется, что есть более изящный метод...

Это же ln2(n), округлённый вверх. - ?
127 = 0b01111111 -> 7
128 = 0b10000000 -> 1

ну, в общем, хочется идти сначала по n=2k+1
потом по n=2*(2k+1)
потом по n=2*2*(2k+1)
и т.д.

[ln2(n)]+1, если быть совсем точным.

VeGeek, поясни переход от

(OneBits(n) / n) - (OneBits(n)/(n+1))

(OneBits(n) - OneBits(n-1)) / n

Сдаётся мне, у тебя там двойная ошибка.

[ln2(n)]+1, если быть совсем точным. - не понимаю.

(OneBits(1) / 1 - OneBits(1) / 2) + (OneBits(2) / 2 - OneBits(2) / 3) + (OneBits(3) / 3 - OneBits(3) / 4) + ... = (OneBits(1) / 1 - OneBits(0) / 1) + (OneBits(2) / 2 - OneBits(1) / 2) + (OneBits(3) / 3 - OneBits(2) / 3) + (OneBits(4) / 4 - OneBits(3) / 4) + ...

по идее, незаконный, но скрипт на руби для обоих вариантов при близких n даёт близкие значения суммы.

я переставил скобочки и поменял слагаемые местами

пардон, число единичных битов в двоичной записи

Первое предложение было не тебе.

Вот про скобочки и слагаемые поподробнее, пожалуйста. Ты же отдаёшь себе отчёт в том, что там между ними ещё деление, да?

А, так это уже другое дело.

(c(1) / 1 - c(1) / 2) + (c(2) / 2 - c(2) / 3) + (c(3) / 3 - c(3) / 4) + ... = (- c(0) / 1 + c(1) / 1) + (- c(1) / 2 + c(2) / 2) + (- c(2) / 3 + c(3) / 3) + (- c(3) / 4 + c(4) / 4) + ...

Да, действительно. Можно попробовать переупорядочить слагаемые. Например в коде Грея разница в один бит.

Ума не приложу, как у тебя -с(n)/(n+1) превращается в -с(n-1)/n.

Нельзя просто так взять и вычесть из числителя и знаменателя одно и то же число, оставив дробь неизменной. А у тебя даже не просто из числителя, а из аргумента функции c(n) (кстати, что это?), значение которой является числителем.

я добавляю c(0) / 1, и переставляю скобки
никого при этом не меняю

оно никак не превращается, я глуп, но не настолько

Теперь понял, спасибо. Однако в таком случае у тебя при перестановке скобок «теряется» последнее слагаемое, -c(n)/(n+1), разве не так?

ну и хрен с ним или нет?

Ты же сумму считаешь, как это хрен с ним?

ряд бесконечный и сходится вроде

при перестановке скобок самый первый член остается «в одиночестве».В твоем случае это 1.

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

\sum_{n=1}^{\infinity} OneBits(n) / (n * (n+1)) = //Bit(n,k) - k-й бит в двоичной записи n

\sum_{n=1}^{\infinity}\sum_{k=0}^{\infinity} Bit(n,k)/(n * (n+1)) =

\sum_{k=0}^{\infinity}\sum_{n=1}^{\infinity} Bit(n,k)/(n * (n+1)) = \\если Bit(n,k)=1, то n = a*2^{k+1}+2^k+b, где b \in [0..2^{k-1}]

\sum_{k=0}^{\infinity}\sum_{a=0}^{\infinity}\sum_{b=0}^{2^{k-1}} [1/(a*2^{k+1}+2^k+b) - 1/(a*2^{k+1}+2^k+b+1)] =

\sum_{k=0}^{\infinity}\sum_{a=0}^{\infinity} [1/(a*2^{k+1}+2^k) - 1/(a*2^{k+1}+2*2^k)] =

\sum_{k=0}^{\infinity} 1/(2^k) * \sum_{a=0}^{\infinity} [1/(2a+1) - 1/(2a+2)] =

\sum_{k=0}^{\infinity} 1/(2^k) * (1 - 1/2 + 1/3 - 1/4 + ...) = // то, что в скобках — классический знакочередующийся ряд, сходящийся к ln 2

ln 2 * \sum_{k=0}^{\infinity} 1/(2^k) =

2 * ln 2

Вроде как-то так.

да, кажется, действительно так

чем обрешиваться, чтобы быть к таким задачам готовым?

я его доукомплектовываю c(0) / 1 и дальше всё хорошо

Ничем. Тут поможет только мозг.

Блин, описка. Там не 2^{k-1}, а 2^k-1. В двух местах.

ответ правильный вроде, идею уловил, без разницы
прикольно было бы, если бы тут был раздел Math/Science с TeX'ом, круче Talks было бы.

спасибо