сумма ряда

[stranger12]

Помогите, пожалуйста, решить задачу.
Задача следующая: вычислить сумму ряда $\sum_{n=1}^\infty \frac{f(n)}{n(n+1)}$, где $f(n)$ -- количество единиц в двоичном представлении числа $n$.

В голову не приходит ничего путного, кроме классической задачи о вычислении суммы ряда $\sum_{n=1}^\infty \frac{1}{n(n+1)}$, то есть что $\sum_{n=1}^k \frac{1}{n(n+1)}=\sum_{n=1}^k (\frac{1}{n}-\frac{1}{n+1})=1-\frac{1}{k+1}$.

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

Числа, в двоичной записи которых не менее двух единиц, хотя бы понятно какие. Это все минус степени двойки. То есть чтобы просуммировать этот кусочек ряда, надо вычислить сумму $\sum_{n=1}^\infty \frac{1}{2^n(2^n+1)}$. И уже с ней непонятно, что делать.

Дайте, пожалуйста, какую-нибудь подсказку к решению данной задачи. Может быть, я совсем не в ту сторону мыслю...

[provincialka]

Может, суммировать поразрядно (в смысле двоичных разрядов). То есть те слагаемые, где 1 на конце двоичного представления, плюс те, где она на втором с конца месте, на третьем и т.п.

[venco]

Я бы представил $f(n)$ как сумму единиц по ненулевым битам числа, затем поменял порядок суммирования на обратный. Т.е. получилось бы сумма для нулевого бита, первого и т.д. Там дальше тоже может быть нетривиально, но уже проще, т.к. сумма будет регулярнее.

-- Ср мар 26, 2014 11:19:52 --

Довольно просто получается.

[stranger12]

Я правильно понимаю, что предлагается просуммировать сначала числа, у которых младший бит равен 1, то есть нечетные, потом добавить те, у которых на предыдущем месте единица, а они идут через два, потом через четыре и так далее?

[provincialka]

Да, оба совета состоят именно в этом. Кстати, я нашла ответ. Он через логарифм.
Только что вы имеет в виду "они идут через два"? Не совсем так. Посмотрите внимательнее, как повторяются единички по разрядам.

[stranger12]

Два через два, наверно, правильнее будет сказать. Неаккуратно написала. Спасибо! Я пока не посчитала, но, если таким образом суммировать, то понятно, как дальше действовать.

[RIP]

topic81594.html