_Небольшая предыстория. Этот пост я написал для двух целей. Во-первых, обкатать [конвертор разметки][1] Markdown + ![inline_formula][2] в хабрачитаемый вид. Во-вторых, рассказать об интересной задаче из data streaming. К концу написания, я обнаружил [пост про LogLog][3] четырехлетней давности. На мою удачу автор предыдущего поста делал упор на реализацию. Я же, полагаясь на ![inline_formula][4], расскажу больше о математике._ Давайте представим, что у нас есть роутер. Через роутер проходит много пакетов по разным адресам. Нам интересно получить статистику, как много адресов задействовано в коммуникации. Есть пара проблем.

* Пакетов так много, что запомнить их все нельзя. Сказать ушедшему пакету «Вернись! Я все прощу,» — тоже.
* Всех возможных адресов ![inline_formula][5]. Столько памяти на роутере нет.

![some title][6] **Задача**. _Есть последовательность целых чисел ![inline_formula][7], все числа принимают значения от ![inline_formula][8] до ![inline_formula][9]. Требуется в один проход посчитать количество различных чисел, используя ![inline_formula][10] памяти_. [Читать дальше →][11]

[1]: http://habrahabr.ru/post/263213/
[2]: http://tex.s2cms.ru/svg/%5Cinline%20%5CLaTeX
[3]: http://habrahabr.ru/post/119852/
[4]: http://tex.s2cms.ru/svg/%5Cinline%20%5CLaTeX
[5]: http://tex.s2cms.ru/svg/%5Cinline%202%5E%7B32%7D
[6]: https://habrastorage.org/files/9e5/6e3/758/9e56e3758e6543cf8a7c1b2490bb7c8f
[7]: http://tex.s2cms.ru/svg/%5Cinline%20%5Csigma%20%3D%20a_1%2C%20a_2%2C%20%5Ccdots%2C%20a_m
[8]: http://tex.s2cms.ru/svg/%5Cinline%200
[9]: http://tex.s2cms.ru/svg/%5Cinline%20n%20-%201
[10]: http://tex.s2cms.ru/svg/%5Cinline%20%5Coverline%7Bo%7D%28n%20%2B%20m%29
[11]: http://habrahabr.ru/post/263211/#habracut