одинокие единицы

[photon]

Входные данные - двоичное число (без ведущих нулей), возможно, очень большое (до 1000000 знаков), при этом есть ограничения на время выполнения программы.

Если в двоичном числе самая левая или самая правая единица отделена от остальной части нулями (хотя бы одним), то она называется одинокой
например, в числах $10100$, $1011001$, $101$, $10101$ - по две одинокие единицы, в $1101$, $10110$, $101011$ - по одной, а в $1100$, $110110$, $11$ их нет вообще.

Необходимо посчитать общее количество одиноких единиц во всех числах от $1$ до заданного и вывести ответ в двоичном виде.

Пример:
на входе: $101$
на выходе $101$ (5 одиноких единиц из $1$, $10$, $100$, $101$ )

-- Wed Nov 27, 2013 11:13:17 --

[worm2]

Задачу пока не пытался решать, но подозреваю, что она решается с помощью универсального приёма под названием OEIS

[worm2]

А что, никому больше не интересна задача? Хорошая же.
Увы, в OEIS прямой формулы не нашёл

1) Подсчитаем $f(2^n-1)$ — число одиноких единиц в диапазоне $[0, 2^n-1]$. Если первая цифра 0, то набираем $f(2^{n-1}-1)$. Если 1, а потом 0, то ещё $f(2^{n-2}-1)$, плюс бонус за первую одинокую единицу в размере $2^{n-2}$. Если $k>1$ первых разрядов единичные, а потом 0, то $f(2^{n-k-1}-1)$, но при этом бонусов нету. Итого:

$$f(2^n-1)=2^{n-2}+\sum\limits_{k=1}^{n-1}f(2^k-1).$$

2) Несложной индукцией доказываем, что $f(2^n-1)=2^{n-3}(n+2)$ при $n>1$.
3) Дальше муторно. Пусть число из $n$ разрядов, причем первые $m$ единичные. Применяя рассуждения из пункта 1) к новым реалиям, кажется, получаем формулу

$$f(1...10X...X)=2^{n-2}+\sum\limits_{k=n-m}^{n-1}f(2^k-1) + f(XX...X).$$

Этим уже можно пользоваться, но нужно тщательно проверить пограничные случаи, что лень.
А ещё лень реализовывать сложение многоразрядных чисел.

P.S. Поправка к п. 3): если $m = 1$, то вместо $2^{n-2}$ нужно ставить $XX...X+1$ (считаем только первую изолированную единицу во всех числах в интервале $[10...0, 10XX...X]$).

[photon]

Я рассуждал примерно так же: посчитать число единиц для круглого числа, меньше заданного, а потом для остального завернуть рекурсию, но как-то недокрутил, да и рекурсия ведет к слишком долгому выполнению алгоритма. А ограничение было, кажется, 2с на обработку 10 чисел, каждое из которых от 3 до 1000000 знаков.

[worm2]

Только сейчас дошло, что моё решение не удовлетворительно. Из-за последней поправки (добавки $XX...X+1$) вычисление $f(1010.....0101)$ будет выполняться за время $O(n^2\log n)$.

[worm2]

Вроде, можно решить эту проблему. Я сначала проиллюстрирую её:
Искомое число является суммой некоторого количества слагаемых вида (1): $2^x$ и $y\cdot 2^x$, где $y$ может быть около миллиона (с этими слагаемыми никаких проблем не возникает, они складываются быстро) и слагаемых вида (2):

+1010110111010101
+  10110111010101
+    110111010101
+           10101
+             101
+               1

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

Поскольку слагаемые совпадают друг с другом (а также с исходным числом) во всех разрядах, за исключением старших, их можно складывать поразрядно: нужно завести массив long-ов, в котором для каждого разряда исходного числа нужно завести количество его попаданий в сумму слагаемых вида (2). Это количество на единицу больше числа изолированных единиц не правее данного разряда (тут я могу немного ошибаться), и оно легко вычисляется (а тут уже не могу). Массив, кстати, очень удобно использовать и для хранения слагаемых типа (1). Сложение чисел этого массива имеет сложность $O(n\log n)$.

(Оффтоп)

Меня не покидает ощущение, что мало кто знает о существовании этого с таким трудом созданного раздела.

[sup]

А у меня другой ответ: $F(n) = f(2^n - 1) = 2^{n} - n$. Рекуррентное соотношение имеет вид
$F(2) = 2$
$F(n) = F(n-1) + 2^{n-1} -1$
Все как и у Вас. Рассматриваем n-битные числа. Если старший бит 0, то для таких чисел сумма единиц равна $F(n-1)$. Далее имеем две группы чисел.
1. Числа начинаются на 11. Для них старшая единица не является одинокой, поэтому вклад дает только младшая. А это все числа вида 11xxxxxxx01,11xxxxxxx010, 11xxxxxxx0100 ... . Таких, очевидно, $2^{n-4} + 2^{n-5} + \dots 1 = 2^{n-3} - 1$
2. Числа начинаются на 10. Для них старшая единица всегда одинокая. Ее вклад равен $2^{n-2}$. Какой вклад дает младшая единица?. Это все числа вида 10xxxxxxx01,10xxxxxxx010, 10xxxxxxx0100 ... Таких, как мы видели, $2^{n-3} - 1$. Плюс еще одно число 10100...0. Итого, таких $2^{n-3}$. А сумма единиц равна $2^{n-2} + 2^{n-3}$
Суммируем и получаем рекуррентное соотношение.
С исходной задачей аналогично. Нам понадобится вспомогательная задача.
Задано число Z. Найти количество всех чисел не превосходящих Z, у которых есть одинокая правая единица. Пусть эта задача решена. Соответствующую функцию назовем G(Z).
Переходим к исходной задаче. Задано n-битное число Z. Два варианта.
1. Число Z начинается на 10. Тогда все не превосходящие его числа либо начинаются на 0 (и для них сумма единиц известна и равна $F(n-1)$) либо начинаются на 10. Для таких чисел левая единица одинокая и ее вклад в общую сумму равен просто количеству таких чисел $Z - 2^{n-1} + 1$. А сумма правых одиноких единиц совпадает с $G(Z_1)$, где $Z_1$ - это число образованное младшими $n-2$ разрядами числа Z. Отдельно надо еще разобраться с числом 10100...0.
2. Число Z начинается на 11. Как и раньше легко получаем $F(n-1)$ (начинаются на 0) плюс $2^{n-2} + 2^{n-3}$ (начинаются на 10) плюс $G(Z_1)$.
Таким образом, надо просто уметь решать вспомогательную задачу нахождения $G(Z)$.
Эта вспомогательная задача решается за линейное время относительно количества бит n.
Ну действительно. Всякое нужное нам число X имеет вид $\overline{xxxxx0100000}$ и оно должно быть не больше числа $Z = \overline{zzzzzz_1z_2yyyyy}$ ($z_1z_2$ - соответствуют 01 в числе X)
Отсюда видим, что если $z_1z_2$ - это 01, 10, 11, то необходимо и достаточно, чтобы $\overline{xxxxx} \leqslant \overline{zzzzz}$, а для $z_1z_2$ равного 00, необходимо и достаточно, чтобы $\overline{xxxxx} < \overline{zzzzz}$
Итак, количество таких чисел либо $\overline{zzzzz}+1$ либо $\overline{zzzzz} $. Количество этих экстра-единиц легко подсчитывается.
Далее, что же это за числа $\overline{zzzzz}$. Да это же сдвиги вправо исходного числа Z. Записав сумму этих чисел в столбик, видим, что сумма битов в каждом разряде (столбике) отличается от предыдущей суммы одним лишь битом числа Z. Ну например, пусть $Z = 1011101$. Тогда искомая сумма выглядит так
1 0 1 1 1 0 1
0 1 0 1 1 1 0
0 0 1 0 1 1 1
0 0 0 1 0 1 1
0 0 0 0 1 0 1
0 0 0 0 0 1 0
0 0 0 0 0 0 1
Легко видеть, что каждый столбик отличается от столбика слева тем, что он сдвинут на одну строчку вниз и добавлен еще один битик. Поэтому сумма считается легко. Для того, чтобы не использовать доп. память, сначала первым проходом считаем сумму единиц в самом правом столбике. А потом начинаем "честное сложение столбиком". Сдвигаемся влево. Вычисляем сумму элементов этого столбика простым вычитанием одного бита из предыдущей суммы. Подсчитываем сколько "на ум пошло". Ну и тд.

Возможно, там еще надо рассмотреть пару "граничных" случаев, но это уже не принципиально. В целом же, вроде бы не слишком трудная задача.