Регулярное число

Не следует путать с Регулярное простое число.

Диаграмма Хассе показывает делимость отношений между обычными числами до 400. Вертикальный масштаб является логарифмическим.

Регулярные числа — это числа, которые равномерно делят степени 60 (или, что эквивалентно, степени 30). Например, 60² = 3600 = 48 × 75, поэтому и 48, и 75 являются делителями степени 60. Таким образом, они являются обычными числами. Эквивалентно, это числа, единственные простые делители которых равны 2, 3 и 5.

Числа, которые равномерно делят степень 60, возникают в нескольких областях математики и её приложений и имеют разные названия, взятые из этих разных областей исследования.

• В теории чисел эти числа называются 5-гладкими, потому что они могут быть охарактеризованы как имеющие только 2, 3 или 5 как простой множитель. Это частный случай более общего k-гладкое число, то есть набора чисел, у которых нет простого множителя больше k.
• При изучении вавилонской математики делители степеней 60 называются обычными числами или обычными шестидесятеричными числами и имеют большое значение из-за шестидесятеричной системы счисления, используемой вавилонянами.
• В теории музыки регулярные числа встречаются в соотношениях тонов в пятиступенчатом натуральном строе.
• В информатике регулярные числа часто называют числами Хэмминга в честь Ричарда Хэмминга, который предложил задачу поиска компьютерных алгоритмов для генерации этих чисел в порядке возрастания.

Теория чисел

Формально регулярное число — это целое число вида 2ⁱ·3^j·5^k для неотрицательных целых чисел i, j, и k. Такое число является делителем $\scriptstyle 60^{\max(\lceil i\,/2\rceil ,j,k)}{}$. Регулярные числа также называются 5-гладкое, указывая, что их наибольший простой множитель не превосходит 5.

Первые несколько регулярных чисел

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, … (последовательность A051037 в OEIS).

Некоторые другие последовательности в OEIS имеют определения, включающие 5-гладкие числа.

Хотя регулярные числа кажутся плотными в диапазоне от 1 до 60, они довольно редки среди больших целых чисел. Регулярное число n = 2ⁱ·3^j·5^k меньше или равно N тогда и только тогда, когда точка (i,j,k) принадлежит тетраэдру, ограниченному координатными плоскостями и плоскостью

$(\ln 2)i+(\ln 3)j+(\ln 5)k\leq \ln N,$

как можно увидеть, логарифмируя обе части неравенства 2ⁱ·3^j·5^k ≤ N. Следовательно, количество регулярных чисел, не превышающих N, можно оценить как объём этого тетраэдра, который равен

${\frac {\log _{2}N\,\log _{3}N\,\log _{5}N}{6}}.$

Ещё точнее, используя нотацию «O» большое, количество регулярных чисел до N равно

${\frac {\left(\ln(N{\sqrt {30}})\right)^{3}}{6\ln 2\ln 3\ln 5}}+O(\log N),$

и было высказано предположение, что погрешность этого приближения на самом деле $O(\log \log N)$. Похожая формула для количества 3-гладких чисел до N дана Сринивасой Рамануджаном в его первом письме Годфри Харолду Харди.

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

В вавилонской шестидесятеричной записи обратное число от регулярного числа имеет конечное представление, поэтому оно легко делится. В частности, если n делит 60^k, тогда шестидесятеричное представление 1/n равно 60^k/n , сдвинутое на некоторое количество мест.

Например, предположим, что мы хотим разделить на обычное число 54 = 2¹3³. 54 — делитель 60³, а 60³/54 = 4000, поэтому деление на 54 в шестидесятеричной дроби можно выполнить, умножив на 4000 и сдвинув три разряда. В шестидесятеричном формате 4000 = 1×3600 + 6×60 + 40×1, или (как указано Джойсом) 1:6:40. Таким образом, 1/54 в шестидесятеричном формате составляет 1/60 + 6/60² + 40/60³, что также обозначается 1:6:40, как это делали вавилонские условные обозначения. не указывая степень начальной цифры. И наоборот, 1/4000 = 54/60³, поэтому деление на 1:6:40 = 4000 может быть выполнено умножением на 54 и сдвигом трёх шестидесятеричных знаков.

Вавилоняне использовали таблицы обратных регулярных чисел, некоторые из которых сохранились до сих пор (Закс, 1947). Эти таблицы существовали относительно неизменными на протяжении вавилонских времён.

Хотя основная причина предпочтения обычных чисел другим заключается в конечности их обратных чисел, некоторые вавилонские вычисления, кроме обратных, также включали регулярные числа. Например, найдены таблицы регулярных квадратов, а сломанная клинопись таблички Плимптон 322 была интерпретирована Отто Э. Нейгебауэром как перечисление пифагоровых троек $(p^{2}-q^{2},\,2pq,\,p^{2}+q^{2})$, сгенерированных обоими регулярными числами p, q, которые меньше 60.

Теория музыки

В теории музыки натуральный строй диатонической гаммы включает обычные числа: высоты звука в одной октаве этой гаммы имеют частоты, пропорциональные числам в последовательности 24, 27, 30, 32, 36, 40, 45, 48 почти последовательных регулярных чисел. Таким образом, для инструмента с такой настройкой все высоты тона являются регулярными гармониками одной основной частоты. Эта шкала называется настройкой 5-предельной настройкой, что означает, что интервал между любыми двумя тонами можно описать как произведение 2ⁱ3^j5^k степеней простых чисел до 5, или, что то же самое, как отношение регулярных чисел.

5-предельные музыкальные шкалы, отличные от привычной диатонической шкалы западной музыки, также использовались как в традиционной музыке других культур, так и в современной экспериментальной музыке: Honingh & Bod (2005) перечисляет 31 различные 5-предельные шкалы, взятые из большой базы данных музыкальных шкал. Каждая из этих 31 шкал разделяет с диатонической интонацией то свойство, что все интервалы являются отношениями регулярных чисел. Тональная сеть Эйлера обеспечивает удобное графическое представление высоты звука в любой 5-предельной настройке путём выделения октавных соотношений (степени двойки) так, что оставшиеся значения образуют планарную сетку. Некоторые теоретики музыки в более общем плане заявили, что регулярные числа имеют фундаментальное значение для самой тональной музыки, и что отношения высоты тона, основанные на простых числах больше 5, не могут быть созвучными. Однако равномерно темперированный строй современных фортепиано не является 5-предельной настройкой, и некоторые современные композиторы экспериментировали с настройками, основанными на простых числах больше 5.

В связи с применением обычных чисел к теории музыки представляет интерес найти пары регулярных чисел, которые отличаются на единицу. Таких пар ровно десять (x, x + 1) и каждая такая пара определяет сверхчастичное соотношение (x + 1)/x, которое имеет смысл как музыкальный интервал. Это 2/1 (октава), 3/2 (чистая квинта), 4/3 (чистая кварта), 5/4 (мажорная терция), 6/5 (минорная терция), 9/8 (большая секунда), 10/9 (малая секунда), 16/15 (диатонический полутон), 25/24 (хроматический полутон) и 81/80 (синтоническая запятая).

Алгоритмы

Алгоритмы вычисления регулярных чисел в порядке возрастания были популяризированы Эдсгером Дейкстрой. Дейкстра приписывает Хэммингу задачу построения бесконечной возрастающей последовательности всех 5-гладких чисел; эта проблема теперь известна как проблема Хэмминга, и полученные таким образом числа также называются числами Хэмминга. Идеи Дейкстры для вычисления этих чисел заключаются в следующем:

• Последовательность чисел Хэмминга начинается с цифры 1.
• Остальные значения в последовательности имеют вид 2h, 3h и 5h, где h — любое число Хэмминга.
• Следовательно, последовательность H может быть сгенерирована путём вывода значения 1, а затем происходит слияние последовательностей 2H, 3H и 5H.

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

В языке программирования Python ленивый функциональный код для генерации регулярных чисел используется в качестве одного из встроенных тестов для правильности реализации языка.

Связанная проблема, обсуждаемая в Knuth (1972), состоит в том, чтобы перечислить все k-цифровые шестнадцатиричные числа в порядке возрастания, как было сделано (для k = 6) писцом эры Селевкидов Инакибит-Ану в табличке AO6456. В алгоритмических терминах это эквивалентно генерированию (в порядке) подпоследовательности бесконечной последовательности обычных чисел в диапазоне от 60^k до 60^{k + 1}. Смотрите Gingerich (1965) для раннего описания компьютерного кода, который генерирует эти числа не по порядку, а затем сортирует их; Кнут описывает специальный алгоритм, который он приписывает Bruins (1970), для более быстрого генерирования шестизначных чисел, но он не обобщается прямым способом на большие значения k. Eppstein (2007) описывает алгоритм вычисления таблиц этого типа за линейное время для произвольных значений k.

Другие приложения

Heninger, Rains & Sloane (2006) показывают, что, когда n является регулярным числом и делится на 8, производящая функция n-мерной экстремальной чётной унимодулярной решётки является n-й степенью многочлена.

Как и в случае с другими классами гладких чисел, регулярные числа важны как размеры проблем в компьютерных программах для выполнения быстрого преобразования Фурье, метода анализа доминирующих частот сигналов в изменяющихся во времени данных. Например, метод Temperton (1992) требует, чтобы длина преобразования была обычным числом.

В книге 8 «Государства» Платона есть аллегория брака, основанная на очень регулярном числе 60⁴ = 12 960 000 и его делители. Позднее учёные использовали как вавилонскую математику, так и теорию музыки, пытаясь объяснить этот отрывок. (Смотрите Число Платона.)

Ссылки

• Таблица обратных чисел для регулярных до 3600 с веб-сайта профессора Дэвида Э. Джойса, Университет Кларка.
• RosettaCode Генерация чисел Хэмминга на ~ 50 языках программирования.