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

Эта статья находится на начальном уровне проработки, в одной из её версий выборочно используется текст из источника, распространяемого под свободной лицензией
Материал из энциклопедии Руниверсалис
Не следует путать с Регулярное простое число.
Диаграмма Хассе показывает делимость отношений между обычными числами до 400. Вертикальный масштаб является логарифмическим[1].

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

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

Теория чисел

Формально регулярное число — это целое число вида 2i·3j·5k для неотрицательных целых чисел i, j, и k. Такое число является делителем [math]\displaystyle{ \scriptstyle 60^{\max(\lceil i\,/2\rceil,j,k)}{} }[/math]. Регулярные числа также называются 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-гладкие числа[2].

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

[math]\displaystyle{ (\ln 2)i+(\ln 3)j+(\ln 5)k\le\ln N, }[/math]

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

[math]\displaystyle{ \frac{\log_2 N\,\log_3 N\,\log_5 N}{6}. }[/math]

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

[math]\displaystyle{ \frac{\left(\ln(N\sqrt{30})\right)^3}{6\ln 2 \ln 3 \ln 5}+O(\log N), }[/math]

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

Примечания

  1. ↑ Вдохновлённый аналогичными диаграммами Эркки Куренниеми в "Хорды, шкалы и решётки делителей" Архивная копия от 10 февраля 2021 на Wayback Machine.
  2. ↑ OEIS поиск последовательностей с 5-гладкостью Архивная копия от 10 апреля 2021 на Wayback Machine.
  3. ↑ Нил Слоун. The On-Line Encyclopedia of Integer Sequences. Дата обращения: 10 апреля 2021. Архивировано 6 мая 2021 года.
  4. ↑ Берндт, Брюс К. & Ренкин, Роберт Александер, eds. (1995), Рамануджан: письма и комментарии, vol. 9, История математики, Американское математическое общество, с. 23, ISBN 978-0-8218-0470-4 .
  5. ↑ 5,0 5,1 Aaboe (1965).
  6. ↑ Смотрите Conway & Guy (1996) для популярного обращения с этой интерпретацией. Плимптон 322 имеет другие интерпретации, о которых смотрите его статью, но все они включают регулярные числа.
  7. ↑ Asmussen (2001), например, заявляет, что «в любом произведении тональной музыки» все интервалы должны быть отношениями регулярных чисел, повторяя аналогичные утверждения гораздо более ранних авторов, таких как Habens (1889). В современной литературе по теории музыки это утверждение часто приписывают Longuet-Higgins (1962), который использовал графическое оформление, близкое к тональной сети, для организации 5-предельных высот звука.
  8. ↑ Halsey & Hewitt (1972) заметил, что это следует из теоремы Стёрмера[en] (Størmer 1897), и предоставил доказательства по этому делу; смотрите также Silver (1971).
  9. ↑ Dijkstra, Edsger W. (1976), 17. An exercise attributed to R. W. Hamming, Дисциплина программирования, Prentice-Hall, с. 129–134, ISBN 978-0132158718, <https://archive.org/details/disciplineofprog0000dijk/page/129> 
  10. ↑ Dijkstra, Edsger W. (1981), Упражнение Хэмминга в SASL, Отчёт EWD792. Первоначально в частном порядке распространялась как рукописная заметка., <http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF>  Архивная копия от 4 апреля 2019 на Wayback Machine
  11. ↑ Смотрите, например, Hemmendinger (1988) или Yuen (1992).
  12. ↑ Функция m235 на test_generators.py Архивная копия от 29 сентября 2007 на Wayback Machine.
  13. ↑ Barton (1908); McClain (1974).

Ссылки

Внешние ссылки

Источник — https://xn--h1ajim.xn--p1ai/index.php?title=Регулярное_число&oldid=5833616