Регулярное число (Jyirlxjuky cnvlk)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Regular_divisibility_lattice.svg/360px-Regular_divisibility_lattice.svg.png)
Регулярные числа — это числа, которые равномерно делят степени 60 (или, что эквивалентно, степени 30). Например, 602 = 3600 = 48 × 75, поэтому и 48, и 75 являются делителями степени 60. Таким образом, они являются обычными числами. Эквивалентно, это числа, единственные простые делители которых равны 2, 3 и 5.
Числа, которые равномерно делят степень 60, возникают в нескольких областях математики и её приложений и имеют разные названия, взятые из этих разных областей исследования.
- В теории чисел эти числа называются 5-гладкими, потому что они могут быть охарактеризованы как имеющие только 2, 3 или 5 как простой множитель. Это частный случай более общего k-гладкое число, то есть набора чисел, у которых нет простого множителя больше k.
- При изучении вавилонской математики делители степеней 60 называются обычными числами или обычными шестидесятеричными числами и имеют большое значение из-за шестидесятеричной системы счисления, используемой вавилонянами.
- В теории музыки регулярные числа встречаются в соотношениях тонов в пятиступенчатом натуральном строе.
- В информатике регулярные числа часто называют числами Хэмминга в честь Ричарда Хэмминга, который предложил задачу поиска компьютерных алгоритмов для генерации этих чисел в порядке возрастания.
Теория чисел
[править | править код]Формально регулярное число — это целое число вида 2i·3j·5k для неотрицательных целых чисел i, 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-гладкие числа[2].
Хотя регулярные числа кажутся плотными в диапазоне от 1 до 60, они довольно редки среди больших целых чисел. Регулярное число n = 2i·3j·5k меньше или равно N тогда и только тогда, когда точка (i,j,k) принадлежит тетраэдру, ограниченному координатными плоскостями и плоскостью
как можно увидеть, логарифмируя обе части неравенства 2i·3j·5k ≤ N. Следовательно, количество регулярных чисел, не превышающих N, можно оценить как объём этого тетраэдра, который равен
Ещё точнее, используя нотацию «O» большое, количество регулярных чисел до N равно
и было высказано предположение, что погрешность этого приближения на самом деле [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 была интерпретирована Отто Э. Нейгебауэром как перечисление пифагоровых троек , сгенерированных обоими регулярными числами p, q, которые меньше 60[6].
Теория музыки
[править | править код]В теории музыки натуральный строй диатонической гаммы включает обычные числа: высоты звука в одной октаве этой гаммы имеют частоты, пропорциональные числам в последовательности 24, 27, 30, 32, 36, 40, 45, 48 почти последовательных регулярных чисел. Таким образом, для инструмента с такой настройкой все высоты тона являются регулярными гармониками одной основной частоты[англ.]. Эта шкала называется настройкой 5-предельной[англ.] настройкой, что означает, что интервал между любыми двумя тонами можно описать как произведение 2i3j5k степеней простых чисел до 5, или, что то же самое, как отношение регулярных чисел.
5-предельные музыкальные шкалы, отличные от привычной диатонической шкалы западной музыки, также использовались как в традиционной музыке других культур, так и в современной экспериментальной музыке: Honingh & Bod (2005) перечисляет 31 различные 5-предельные шкалы, взятые из большой базы данных музыкальных шкал. Каждая из этих 31 шкал разделяет с диатонической интонацией то свойство, что все интервалы являются отношениями регулярных чисел. Тональная сеть Эйлера обеспечивает удобное графическое представление высоты звука в любой 5-предельной настройке путём выделения октавных соотношений (степени двойки) так, что оставшиеся значения образуют планарную сетку[англ.]. Некоторые теоретики музыки в более общем плане заявили, что регулярные числа имеют фундаментальное значение для самой тональной музыки, и что отношения высоты тона, основанные на простых числах больше 5, не могут быть созвучными[7]. Однако равномерно темперированный строй современных фортепиано не является 5-предельной настройкой, и некоторые современные композиторы экспериментировали с настройками, основанными на простых числах больше 5.
В связи с применением обычных чисел к теории музыки представляет интерес найти пары регулярных чисел, которые отличаются на единицу. Таких пар ровно десять (x, x + 1)[8] и каждая такая пара определяет сверхчастичное соотношение (x + 1)/x, которое имеет смысл как музыкальный интервал. Это 2/1 (октава), 3/2 (чистая квинта), 4/3 (чистая кварта), 5/4 (мажорная терция[англ.]), 6/5 (минорная терция[англ.]), 9/8 (большая секунда), 10/9 (малая секунда), 16/15 (диатонический полутон), 25/24 (хроматический полутон) и 81/80 (синтоническая запятая[англ.]).
Алгоритмы
[править | править код]Алгоритмы вычисления регулярных чисел в порядке возрастания были популяризированы Эдсгером Дейкстрой. Дейкстра [9] [10] приписывает Хэммингу задачу построения бесконечной возрастающей последовательности всех 5-гладких чисел; эта проблема теперь известна как проблема Хэмминга, и полученные таким образом числа также называются числами Хэмминга. Идеи Дейкстры для вычисления этих чисел заключаются в следующем:
- Последовательность чисел Хэмминга начинается с цифры 1.
- Остальные значения в последовательности имеют вид 2h, 3h и 5h, где h — любое число Хэмминга.
- Следовательно, последовательность H может быть сгенерирована путём вывода значения 1, а затем происходит слияние[англ.] последовательностей 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]. (Смотрите Число Платона[англ.].)
Примечания
[править | править код]- ↑ Вдохновлённый аналогичными диаграммами Эркки Куренниеми в «Хорды, шкалы и решётки делителей» Архивная копия от 10 февраля 2021 на Wayback Machine.
- ↑ OEIS поиск последовательностей с 5-гладкостью Архивная копия от 10 апреля 2021 на Wayback Machine.
- ↑ Нил Слоун. The On-Line Encyclopedia of Integer Sequences . Дата обращения: 10 апреля 2021. Архивировано 6 мая 2021 года.
- ↑ Берндт, Брюс К.; Ренкин, Роберт Александер, eds. (1995), Рамануджан: письма и комментарии, История математики, vol. 9, Американское математическое общество, p. 23, ISBN 978-0-8218-0470-4.
- ↑ 1 2 Aaboe (1965).
- ↑ Смотрите Conway & Guy (1996) для популярного обращения с этой интерпретацией. Плимптон 322 имеет другие интерпретации, о которых смотрите его статью, но все они включают регулярные числа.
- ↑ Asmussen (2001), например, заявляет, что «в любом произведении тональной музыки» все интервалы должны быть отношениями регулярных чисел, повторяя аналогичные утверждения гораздо более ранних авторов, таких как Habens (1889). В современной литературе по теории музыки это утверждение часто приписывают Longuet-Higgins (1962), который использовал графическое оформление, близкое к тональной сети, для организации 5-предельных высот звука.
- ↑ Halsey & Hewitt (1972) заметил, что это следует из теоремы Стёрмера[англ.] (Størmer 1897), и предоставил доказательства по этому делу; смотрите также Silver (1971).
- ↑ Dijkstra, Edsger W. (1976), "17. An exercise attributed to R. W. Hamming", Дисциплина программирования, Prentice-Hall, pp. 129–134, ISBN 978-0132158718
- ↑ Dijkstra, Edsger W. (1981), Hamming's exercise im SASL (PDF), Отчёт EWD792 «Упражнение Хэмминга в SASL». Первоначально в частном порядке распространялась как рукописная заметка., Архивировано из оригинала (PDF) 4 апреля 2019, Дата обращения: 10 апреля 2021
- ↑ Смотрите, например, Hemmendinger (1988) или Yuen (1992).
- ↑ Функция m235 на test_generators.py Архивная копия от 29 сентября 2007 на Wayback Machine.
- ↑ Barton (1908); McClain (1974).
Литература
[править | править код]- Aaboe, Asger (1965), "Некоторые математические таблицы Селевкидов (расширенные обратные и квадраты регулярных чисел)", Journal of Cuneiform Studies, 19 (3), Американские школы восточных исследований: 79—86, doi:10.2307/1359089, JSTOR 1359089, MR 0191779.
- Asmussen, Robert (2001), Периодичность синусоидальных частот как основа для анализа барокко и классической гармонии: компьютерное исследование (PDF), Ph.D. thesis, University of Leeds Архивная копия от 24 апреля 2016 на Wayback Machine.
- Barton, George A. (1908), "О вавилонском происхождении брачного числа Платона", Journal of the American Oriental Society, 29, Американское восточное общество: 210—219, doi:10.2307/592627, JSTOR 592627.
- Bruins, E. M. (1970), "Построение большой таблицы обратных величин АО 6456", in Finet, André (ed.), Материалы XVII Международного ассириологического совещания, Бельгийский комитет по исследованиям в Месопотамии, pp. 99—115.
- Conway, John H.; Guy, Richard K. (1996), Книга чисел, Copernicus, pp. 172–176, ISBN 0-387-97993-X.
- Dijkstra, Edsger W. (1976), "17. Упражнение, приписываемое Р. В. Хэммингу.", Дисциплина программирования, Prentice-Hall, pp. 129–134, ISBN 978-0132158718
- Dijkstra, Edsger W. (1981), Упражнение Хэмминга в SASL (PDF), Отчет EWD792. Первоначально распространённая в частном порядке рукописная записка.
- Eppstein, David (2007), Проблема Хэмминга с ограничением по дальности.
- Gingerich, Owen (1965), "Одиннадцатизначные обычные шестидесятичные числа и их обратные", Transactions of the American Philosophical Society, 55 (8), Американское философское общество: 3—38, doi:10.2307/1006080, JSTOR 1006080.
- Habens, Rev. W. J. (1889), "О музыкальной шкале" (PDF), Труды Музыкального общества, 16, Королевская музыкальная ассоциация: 16-я сессия, стр. 1, JSTOR 765355.
- Halsey, G. D.; Hewitt, Edwin (1972), "Подробнее о сверхчастичных соотношениях в музыке", American Mathematical Monthly, 79 (10), Математическая ассоциация Америки: 1096—1100, doi:10.2307/2317424, JSTOR 2317424, MR 0313189.
- Hemmendinger, David (1988), ""Проблема Хэмминга" в Прологе", ACM SIGPLAN Notices, 23 (4): 81—86, doi:10.1145/44326.44335.
- Heninger, Nadia; Rains, E. M.; Sloane, N. J. A. (2006), "О целочисленности корней n-й степени производящих функций", Journal of Combinatorial Theory, Series A, 113 (8): 1732—1745, arXiv:math.NT/0509316, doi:10.1016/j.jcta.2006.03.018, MR 2269551}.
- Honingh, Aline; Bod, Rens (2005), "Выпуклость и правильная форма музыкальных объектов", Journal of New Music Research, 34 (3): 293—303, doi:10.1080/09298210500280612.
- Knuth, D. E. (1972), "Древние вавилонские алгоритмы", Communications of the ACM, 15 (7): 671—677, doi:10.1145/361454.361514. Errata in CACM 19(2), 1976. Печатается с кратким дополнением к Избранным статьям по информатике, Лекционные заметки CSLI 59, Издательство Кембриджского университета, 1996, стр. 185—203.
- Longuet-Higgins, H. C. (1962), "Письмо музыкальному другу", Музыкальный обозрение (August): 244—248.
- McClain, Ernest G. (1974), "Музыкальные «Браки» в «Республике» Платона.", Journal of Music Theory, 18 (2), Издательство Дьюкского университета: 242—272, doi:10.2307/843638, JSTOR 843638.
- Sachs, A. J. (1947), "Вавилонские математические тексты. I. Обратные от регулярных шестидесятеричных чисел.", Journal of Cuneiform Studies, 1 (3), Американские школы восточных исследований: 219—240, doi:10.2307/1359434, JSTOR 1359434, MR 0022180.
- Silver, A. L. Leigh (1971), "Музыка или скрипка монахини", Американский математический ежемесячник, 78 (4), Математическая ассоциация Америки: 351—357, doi:10.2307/2316896, JSTOR 2316896.
- Størmer, Carl (1897), "Quelques théorèmes sur l'équation de Pell x2 − Dy2 = ±1 et leurs applications", Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl, I (2) Некоторые теоремы об уравнении Пелля x2 − Dy2 = ±1 и их приложения.
- Temperton, Clive (1992), "A generalized prime factor FFT algorithm for any N = 2p3q5r", SIAM Journal on Scientific and Statistical Computing, 13 (3), Society for Industrial and Applied Mathematics: 676—686, doi:10.1137/0913039 Обобщенный алгоритм БПФ с простыми множителями для любых N = 2p3q5r.
- Yuen, C. K. (1992), "Числа Хэмминга, ленивое вычисление и нетерпеливое избавление", Уведомления ACM SIGPLAN, 27 (8): 71—75, doi:10.1145/142137.142151.
Ссылки
[править | править код]- Таблица обратных чисел для регулярных до 3600 с веб-сайта профессора Дэвида Э. Джойса, Университет Кларка.
- RosettaCode Генерация чисел Хэмминга на ~ 50 языках программирования.