Обычный номер - Regular number

Не путать с обычный прайм.

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

Обычные номера числа, которые равномерно делят степени 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, для неотрицательных целых чисел я, j, и k. Такое число является делителем ${displaystyle scriptstyle 60^{max(lceil i,/2ceil ,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, они довольно редки среди больших целых чисел. Обычный номер п = 2^я·3^j·5^k меньше или равно N тогда и только тогда, когда точка (я,j,k) принадлежит тетраэдр ограниченный координатными плоскостями и плоскостью

${displaystyle (ln 2)i+(ln 3)j+(ln 5)kleq ln N,}$

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

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

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

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

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

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

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

Например, предположим, что мы хотим разделить на обычное число 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 и сдвигом трех шестидесятеричных знаков.

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

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

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

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

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

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

Алгоритмы

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

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

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

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

Связанная проблема, обсуждаемая Кнут (1972), это перечислить все k-значные шестидесятеричные числа в порядке возрастания, как это было сделано (для k = 6) Инакибит-Ану, Селевкид -эра писец планшета АО6456. С алгоритмической точки зрения это эквивалентно генерации (по порядку) подпоследовательности бесконечной последовательности регулярных чисел в диапазоне от 60^k до 60^k + 1.Увидеть Джинджерич (1965) для раннего описания компьютерного кода, который генерирует эти числа не по порядку, а затем сортирует их; Кнут описывает специальный алгоритм, который он приписывает Брюинз (1970), для более быстрого генерирования шестизначных чисел, но это не дает прямого обобщения на большие значения k. Эппштейн (2007) описывает алгоритм вычисления таблиц этого типа за линейное время для произвольных значений k.

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

Хенингер, Рейнс и Слоан (2006) показать это, когда п является правильным числом и делится на 8, производящая функция п-мерная экстремальная четная унимодулярная решетка является п-я степень полинома.

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

Книга VIII из Платон с Республика включает в себя аллегорию брака, основанную на очень регулярном числе 60⁴ = 12 960 000 и его делители. Позднее ученые использовали как вавилонскую математику, так и теорию музыки, пытаясь объяснить этот отрывок.^[11] (Увидеть Число Платона.)

Заметки

1. Вдохновленный аналогичными диаграммами Эркки Куренниеми в «Хорды, шкалы и решетки делителей».
2. OEIS поиск последовательностей с 5-гладкостью.
3. Слоан, Н. Дж. А. (ред.). «Последовательность A051037». В Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
4. Берндт, Брюс С .; Ранкин, Роберт Александр, ред. (1995), Рамануджан: письма и комментарии, История математики, 9, Американское математическое общество, стр. 23, ISBN  978-0-8218-0470-4.
5. Aaboe (1965).
6. Увидеть Конвей и Гай (1996) для популярного обращения с этой интерпретацией. Плимптон 322 имеет другие интерпретации, о которых см. его статью, но все они включают обычные числа.
7. Асмуссен (2001), например, заявляет, что «в любом произведении тональной музыки» все интервалы должны быть отношениями регулярных чисел, повторяя аналогичные утверждения гораздо более ранних авторов, таких как Хабенс (1889). В современной литературе по теории музыки это утверждение часто приписывают Лонге-Хиггинс (1962), который использовал графическое оформление, тесно связанное с Tonnetz организовать 5-лимитные веревки.
8. Холзи и Хьюитт (1972) заметим, что это следует из Теорема Стёрмера (Стёрмер 1897 ), и предоставить доказательства этого случая; смотрите также Серебро (1971).
9. См., Например, Хеммендингер (1988) или Юэнь (1992).
10. Функция m235 in test_generators.py.
11. Бартон (1908); Макклейн (1974).

использованная литература

• Aaboe, Asger (1965), «Некоторые математические таблицы Селевкидов (расширенные обратные и квадраты регулярных чисел)», Журнал клинописных исследований, Американские школы восточных исследований, 19 (3): 79–86, Дои:10.2307/1359089, JSTOR  1359089, Г-Н  0191779.
• Асмуссен, Роберт (2001), Периодичность синусоидальных частот как основа для анализа барокко и классической гармонии: компьютерное исследование (PDF), Кандидат наук. Тезис, Университет Лидса.
• Бартон, Джордж А. (1908), «О вавилонском происхождении брачного числа Платона», Журнал Американского восточного общества, Американское восточное общество, 29: 210–219, Дои:10.2307/592627, JSTOR  592627.
• Брюинз, Э. М. (1970), "La construction de la grande table le valeurs réciproques AO 6456", Finet, André (ed.), Actes de la XVII^е Rencontre Assyriologique Internationale, Comité belge de recherches en Mésopotamie, стр. 99–115..
• Конвей, Джон Х.; Гай, Ричард К. (1996), Книга чисел, Коперник, стр.172–176, ISBN  0-387-97993-X.
• Дейкстра, Эдсгер В. (1976), «17. Упражнение, приписываемое Р. В. Хэммингу», Дисциплина программирования, Прентис-Холл, стр.129–134, ISBN  978-0132158718
• Дейкстра, Эдсгер В. (1981), Упражнение Хэмминга в SASL (PDF), Отчет EWD792. Первоначально распространенная в частном порядке рукописная записка.
• Эппштейн, Дэвид (2007), Проблема Хэмминга с ограничением по дальности.
• Gingerich, Оуэн (1965), "Одиннадцатизначные регулярные шестидесятичные числа и их обратные", Труды Американского философского общества, Американское философское общество, 55 (8): 3–38, Дои:10.2307/1006080, JSTOR  1006080.
• Habens, Rev. W. J. (1889), «По музыкальной шкале» (PDF), Труды Музыкального общества, Королевская музыкальная ассоциация, 16: 16-я сессия, с. 1, JSTOR  765355.
• Halsey, G.D .; Хьюитт, Эдвин (1972), «Подробнее о сверхчастичных соотношениях в музыке», Американский математический ежемесячный журнал, Математическая ассоциация Америки, 79 (10): 1096–1100, Дои:10.2307/2317424, JSTOR  2317424, Г-Н  0313189.
• Хеммендингер, Дэвид (1988), "Проблема Хэмминга" в Прологе ", Уведомления ACM SIGPLAN, 23 (4): 81–86, Дои:10.1145/44326.44335.
• Хенингер, Надя; Rains, E.M .; Слоан, Н. Дж. А. (2006), «О целостности пкорни производящих функций », Журнал комбинаторной теории, Серия А, 113 (8): 1732–1745, arXiv:math.NT / 0509316, Дои:10.1016 / j.jcta.2006.03.018, Г-Н  2269551}.
• Хонинг, Алин; Бод, Ренс (2005), «Выпуклость и правильная форма музыкальных объектов», Журнал новых музыкальных исследований, 34 (3): 293–303, Дои:10.1080/09298210500280612.
• Кнут, Д. Э. (1972), «Древние вавилонские алгоритмы», Коммуникации ACM, 15 (7): 671–677, Дои:10.1145/361454.361514. Опечатки в CACM 19(2), 1976. Печатается с кратким дополнением в Избранные статьи по информатике, CSLI Lecture Notes 59, Cambridge Univ. Press, 1996, с. 185–203.
• Лонге-Хиггинс, Х. (1962), «Письмо музыкальному другу», Музыкальный обзор (Август): 244–248.
• Макклейн, Эрнест Г. (1974), "Мюзикл" Браки "в платоновской" Республике """, Журнал теории музыки, Издательство Duke University Press, 18 (2): 242–272, Дои:10.2307/843638, JSTOR  843638.
• Сакс, А. Дж. (1947), "Вавилонские математические тексты. I. Взаимные числа правильных шестидесятеричных чисел", Журнал клинописных исследований, Американские школы восточных исследований, 1 (3): 219–240, Дои:10.2307/1359434, JSTOR  1359434, Г-Н  0022180.
• Сильвер, А. Л. Ли (1971), «Музыка или скрипка монахини», Американский математический ежемесячный журнал, Математическая ассоциация Америки, 78 (4): 351–357, Дои:10.2307/2316896, JSTOR  2316896.
• Стёрмер, Карл (1897), "Теоретические поиски Пелля" Икс² − Dy² = ±1 и другие приложения ", Скрифтер Виденскабс-сельскабет (Христиания), Мат.-Натурв. Kl., я (2).
• Темпертон, Клайв (1992), "Обобщенный алгоритм быстрого преобразования Фурье для любых N = 2^п3^q5^р", Журнал SIAM по научным и статистическим вычислениям, 13 (3): 676–686, Дои:10.1137/0913039.
• Юэн, К. К. (1992), "Числа Хэмминга, ленивое вычисление и активное удаление", Уведомления ACM SIGPLAN, 27 (8): 71–75, Дои:10.1145/142137.142151.

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

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