LINUX.ORG.RU
решено ФорумTalks

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

 , ,


0

1

найти сумму ряда:
OneBits(n) / n*(n+1), n=1..inf
OneBits(n) - число единичных битов в двоичной записи числа n.

сразу хочется забить на законность операций (потом что хрен знает, как тут доказывать сходимость-абсолютную сходимость)
расписать OneBits(n) / n*(n+1) = (OneBits(n) / n) - (OneBits(n)/(n+1)),
перерасставить скобки и получить ряд

(OneBits(n) - OneBits(n-1)) / n, n =1..inf

дальше пройтись сначала по n = 1, 11, 101, 111, ... (для них OneBits(n) - OneBits(n-1) = 1)
потом по n = 10, 110, 1010, 1110, ... (для них OneBits(n) - OneBits(n-1) = 0)

то есть. S_m = (-m + 1) / ((2^m)*(2k+1)) k=0..inf
S_m = ((-m + 1) / (2^m)) * sum_{k=0}^{\infty} 1/(2*k+1)
m+1 - позиция первой справа единицы.
а сумма ряда S = \sum_{m=0}^\infty S_m

просуммировать и получить в ответе ноль, чего не может быть в принципе.
какие идеи?

Deleted

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

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

ziemin ★★
()
Ответ на: комментарий от Deleted

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

Deleted
()
Ответ на: комментарий от ziemin

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

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

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

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

beresk_let ★★★★★
()
Ответ на: комментарий от beresk_let

[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 даёт близкие значения суммы.

Deleted
()
Последнее исправление: VeGeek (всего исправлений: 1)
Ответ на: комментарий от Deleted

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

Deleted
()
Ответ на: комментарий от Deleted

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

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

beresk_let ★★★★★
()
Ответ на: комментарий от beresk_let

(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) + ...

Deleted
()
Ответ на: комментарий от Deleted

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

ziemin ★★
()
Ответ на: комментарий от Deleted

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

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

beresk_let ★★★★★
()
Ответ на: комментарий от beresk_let

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

Deleted
()
Ответ на: комментарий от Deleted

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

beresk_let ★★★★★
()

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

dikiy ★★☆☆☆
()
Ответ на: комментарий от Deleted

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

Rakot ★★
()

\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

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

Miguel ★★★★★
()
Ответ на: комментарий от dikiy

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

Deleted
()
Ответ на: комментарий от Miguel

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

Deleted
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.