Арбузный блог

Не так давно попалась мне на глаза великолепная юмористическая статья про файловую систему, хранящую данные в числе Пи. Бурное обсуждение, развернувшееся в комментариях (кажется, не все его участники поняли шутку), натолкнуло меня на мысль, что тему нормальных чисел неплохо бы обсудить более серьёзно, тем более что тема эта благодатна, полна красивых результатов, нерешённых проблем и прочих кошерных вещей. Если желаете с этими вещами ознакомиться — пожалуйте под кат.

Вавилонская библиотека

Числа, подходящие для того, чтобы «хранить» в них детскую порнографию и нелицензионный контент произвольные данные посредством метода, напоминающего книжный шифр, называются дизъюнктивными. Более строго, число называется дизъюнктивным по основанию b, если его b-ичная запись содержит любую конечную последовательность b-ичных цифр. Такие числа несложно построить искусственно. К примеру, выпишем все натуральные числа подряд в качестве дробной части десятичного дизъюнктивного числа:

0,12345678910111213…

Чуть менее «искусственное» дизъюнктивное число можно получить как сумму ряда: , что будет выглядеть как:

0,1002000030000004…

Или, используя результат, полученный мной здесь, а также уменьшив количество лишних нулей, можно в качестве нашей «вавилонской библиотеки» взять сумму , которая выглядит следующим образом:

1.204008001600032…

Аналогичные конструкции можно использовать для построения дизъюнктивных чисел по произвольному основанию.

Лексикон

Лексиконом, или абсолютно дизъюнктивным числом называется число, дизъюнктивное по любому основанию. Если обычное дизъюнктивное число — это вавилонская библиотека, то лексикон можно назвать «вавилонской википедией», содержащей вавилонскую библиотеку в каждом языковом разделе (системе счисления).

Такую штуку сконструировать уже сложнее. Однако, как говаривал вещий Олег, «мой конь не боится опасных трудов». Идея следующая: каждое b-значное число можно немного увеличить на некое Δ так, чтобы его первые k цифр остались неизменными (b и k любые). Более того, для нескольких систем счисления можно выбрать некое Δ_min так, чтобы при увеличении на него не пострадали первые k цифр ни в одной из этих систем счисления. Поэтому для построения лексикона L можно использовать следующий алгоритм:

1. Вначале возьмём L = 0.
2. Для каждого n от 2 до ∞ выполним пункт 3.
3. Для каждого b от 2 до n выполним пункт 4.
4. Увеличим число L на такое минимальное Δ, чтобы в b-ичной системе счисления его запись стала содержать b-ичную запись числа (n — b + 1), но при этом не «стёрлась» ни одна запись, внесённая предыдущими итерациями этого пункта.
5. Совершаем предельный переход
6. Профит!

Можно попытаться проследить несколько первых шагов этого алгоритма.

Тряхнём нормальностью

Нормальное число по основанию b — это такое дизъюнктивное число (по тому же основанию), что для всякого k все последовательности b-ичных цифр длины k входит в b-ичную запись этого числа с одной и той же асимптотической плотностью b^-k. Под асимптотической плотностью последовательности w подразумевается , где count(w,n) — это сколько раз последовательность w встретилась среди первых n цифр.

Говоря по рабоче-крестьянски, число является нормальным, если в последовательности его цифр все подпоследовательности равной длины встречаются одинаково часто. В контексте нашей гипотетической файловой системы это означает, что у одинаковых объёмов данных будут смещения примерно одного порядка. Если отбросить шутки в сторону, в среднем запись смещения будет иметь примерно ту же длину, что и кодируемая этим смещением информация. Так что никакого сжатия 100%, увы.

Аналогично понятию абсолютно дизъюнктивного числа, существует также понятие абсолютно нормального числа. Как нетрудно догадаться, это число, нормальное по любому основанию.

Ненормальная нормальность

Удивительно, но все числа, с которыми мы имеем дело в повседневной жизни, не являются нормальными. «Ненормальность» целых чисел очевидна — их дробная состоит из одних нулей. Также ненормальны и рациональные числа, поскольку их дробная часть в некоторый момент становится периодической, и мы можем подобрать последовательность цифр, которая с этой периодичностью жёстко дисгармонирует.

Что касается привычных нашему глазу иррациональностей (пи, е, корень из двух etc.) — с ними тоже всё далеко не гладко. Британские учёные полагают, эти числа нормальны; однако на сегодняшний день, насколько мне известно, не существует даже доказательства того, что они дизъюнктивны.

Выходит, что мы не знаем ни одного «адекватного», естественным образом полученного нормального числа. Что же тогда в них нормального? Ответ прост: нормальных чисел большинство. Доказано, что множество «ненормальных» чисел имеет лебегову меру 0. Это означает, что если ткнуть пальцем в единичный отрезок, то с вероятностью 100% попадёшь в нормальное число.

Нормальность vs Дизъюнктивность

Между нормальными и дизъюнктивными числами есть две существенных разницы. Первая — дополнительное условие, накладываемое на асимптотическую плотность последовательностей цифр в записи нормального числа. Вторая — само существование нормальных чисел куда менее очевидно.

Вернёмся к примерам дизъюнктивных чисел из раздела «Вавилонская библиотека». Нетрудно понять, что второй и третий пример ненормальны: в них асимптотическая плотность нуля будет существенно выше, чем у других цифр. Скажу по секрету:

А вот первый пример, как ни странно, является нормальным числом. Кстати, это число называется константой Чамперноуна. Также нормальна константа Коуплэнда-Эрдёша:

0,235711131719…

— состоящая из десятичных записей простых чисел. Доказано, что аналогичные константы являются нормальными в других системах счисления. Также доказана нормальность таких чисел, как:

0,1491625364964…

0,182764125216…

0,1361015212836…

— и многих других. Однако доказательства их нормальности не являются тривиальными. В следующей статье, если данная тема заинтересует хабрасообщество, я покажу, как построить число, нормальность которого очевидна. Это потребует отдельной статьи, поскольку весьма неочевиден (и интересен!) способ его построения. Похоже, существует некий аналог гейзенберговского принципа неопределённости, касающийся сложности построения нормального числа и сложности доказательства его нормальности :)

Что касается абсолютно нормальных чисел — для них, в отличие от лексиконов, нет даже алгоритма построения. Однако доказано, что алгоритм существует. Такие дела.

Резюме

Существует вероятность, что число Пи не обеспечит должную сохранность ваших файлов. Рекомендую использовать вместо него любое искусственно выведенное нормальное число, например — константу Чамперноуна. Кстати, довольно интересная алгоритмическая задача — по заданной последовательности цифр определить индекс её первого вхождения в десятичную запись этой константы.

На этом всё. До свидания, девочки и мальчики, до новых встреч, и пусть всё у вас будет нормально.

Источник.