Калькулятор чисел Хэмминга (регулярных чисел)

Что такое числа Хэмминга

Числа Хэмминга (регулярные числа, 5-гладкие числа) — это натуральные числа вида

H = 2^a · 3^b · 5^c, a, b, c ≥ 0

то есть числа, которые делятся только на 2, 3 и 5. Последовательность начинается так: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30… Числа 7, 11, 13, 14 в неё не входят — у них есть простые делители больше 5.

Название связано с Ричардом Хэммингом, который предложил задачу: вывести эти числа по возрастанию без пропусков и повторов. Эдсгер Дейкстра сделал её классическим примером элегантного алгоритма. Кодам Хэмминга и расстоянию Хэмминга эти числа родственны только по имени.

Как их найти

Каждое число Хэмминга, кроме 1, получается умножением меньшего числа Хэмминга на 2, 3 или 5. Поэтому последовательность строят тремя «указателями»: следующее число — минимум из 2·H_i, 3·H_j, 5·H_k, после чего сдвигаются указатели, давшие этот минимум. Алгоритм находит первые n чисел за n шагов.

Чтобы проверить число, его делят на 2, 3 и 5, пока делится. Если в итоге осталась единица — это число Хэмминга.

Пример

1691-е число Хэмминга — 2 125 764 000 = 2⁵ · 3¹² · 5³. Это последнее число Хэмминга, которое помещается в 31 бит — его часто используют для проверки программ. Число 2026 = 2 · 1013 — не число Хэмминга, ближайшие к нему 2025 = 3⁴ · 5² и 2048 = 2¹¹.

Где встречаются

• Быстрое преобразование Фурье. БПФ работает быстрее всего на длинах, раскладывающихся на малые множители. Библиотеки дополняют массивы до ближайшего числа Хэмминга.
• Вавилонская математика. В шестидесятеричной системе дробь 1/n записывается конечной, только если n — регулярное число. Вавилонские таблицы обратных величин состоят из таких чисел.
• Музыка. В пятипредельном строе интервалы задаются отношениями чисел Хэмминга: 3/2 — квинта, 5/4 — большая терция.
• Удобные размеры. Делимость на 2, 3 и 5 делает числа вроде 60, 360 и 3600 удобными для деления на равные части — отсюда минуты, градусы и часы.