Регулярный номер

Числа, которые делят степени числа 60 нацело

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

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

Эти числа встречаются в различных областях математики и ее приложений и имеют разные названия, происходящие от различных областей их изучения.

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

Теория чисел

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

Первые несколько обычных чисел — ^[2]

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 )

Несколько других последовательностей в Онлайновой энциклопедии целочисленных последовательностей имеют определения, включающие 5-гладкие числа. ^[4]

Хотя регулярные числа кажутся плотными в диапазоне от 1 до 60, они довольно редки среди больших целых чисел. Регулярное число меньше или равно некоторому порогу тогда и только тогда, когда точка принадлежит тетраэдру , ограниченному координатными плоскостями и плоскостью , как можно увидеть, взяв логарифмы обеих сторон неравенства . Таким образом, количество регулярных чисел, которые не превышают , можно оценить как объем этого тетраэдра, который составляет Еще точнее, используя обозначение большого O , количество регулярных чисел до равно и было высказано предположение, что погрешность этого приближения на самом деле равна . ^[2] Подобная формула для количества 3-гладких чисел до приведена Шринивасой Рамануджаном в его первом письме к GH Hardy . ^[5] ${\displaystyle n=2^{i}\cdot 3^{j}\cdot 5^{k}}$ ${\displaystyle N}$ ${\displaystyle (i,j,k)}$ $${\displaystyle i\ln 2+j\ln 3+k\ln 5\leq \ln N,}$$ ${\displaystyle 2^{i}\cdot 3^{j}\cdot 5^{k}\leq N}$ ${\displaystyle N}$ $${\displaystyle {\frac {\log _{2}N\,\log _{3}N\,\log _{5}N}{6}}.}$$ ${\displaystyle N}$ $${\displaystyle {\frac {\left(\ln(N{\sqrt {30}})\right)^{3}}{6\ln 2\ln 3\ln 5}}+O(\log N),}$$ ${\displaystyle O(\log \log N)}$ ${\displaystyle N}$

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

AO 6456, таблица обратных величин обычных чисел из селевкидского Урука , скопированная из неизвестного более раннего источника

В вавилонской шестидесятеричной системе счисления обратная величина обычного числа имеет конечное представление. Если делит , то шестидесятеричное представление — это то же самое, что и для , сдвинутое на некоторое количество позиций. Это позволяет легко делить на эти числа: делить на , умножать на , затем сдвигать. ^[6] ${\displaystyle n}$ ${\displaystyle 60^{k}}$ ${\displaystyle 1/n}$ ${\displaystyle 60^{k}/n}$ ${\displaystyle n}$ ${\displaystyle 1/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 и сдвинув три шестидесятеричных знака.

Вавилоняне использовали таблицы обратных чисел обычных чисел, некоторые из которых сохранились до сих пор. ^[7] Эти таблицы существовали относительно неизменными на протяжении вавилонских времен. ^[6] Одна табличка времен Селевкидов , написанная неким Инакибитом-Ану, содержит обратные числа 136 из 231 шестизначных обычных чисел, первое место которых — 1 или 2, перечисленные по порядку. Она также включает обратные числа некоторых чисел, состоящих из более чем шести знаков, таких как 3 ²³ (2 1 4 8 3 0 7 в шестидесятеричной системе), обратная величина которых имеет 17 шестидесятеричных цифр. Отмечая сложность как вычисления этих чисел, так и их сортировки, Дональд Кнут в 1972 году приветствовал Инакибита-Ану как «первого человека в истории, решившего вычислительную задачу, которая занимает больше одной секунды времени на современном электронном компьютере!» (Известны также две таблицы, дающие приближенные значения обратных величин нерегулярных чисел, одна из которых дает обратные величины для всех чисел от 56 до 80.) ^{[8] [9]}

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

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

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

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

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

В теории всеобщей гармонии эпохи Возрождения музыкальные соотношения использовались в других приложениях, включая архитектуру зданий. В связи с анализом этих общих музыкальных и архитектурных соотношений, например, в архитектуре Палладио , регулярные числа также назывались гармоническими целыми числами . ^[17]

Алгоритмы

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

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

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

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

Связанная с этим проблема, обсуждаемая Кнутом (1972), заключается в перечислении всех -значных шестидесятеричных чисел в порядке возрастания (см. #Вавилонская математика выше). В алгоритмических терминах это эквивалентно генерации (по порядку) подпоследовательности бесконечной последовательности обычных чисел, начиная от до . ^[8] См. Джинджерич (1965) для раннего описания компьютерного кода, который генерирует эти числа не по порядку, а затем сортирует их; ^[20] Кнут описывает специальный алгоритм, который он приписывает Брюинзу (1970), для более быстрой генерации шестизначных чисел, но который не обобщается прямым образом на большие значения . ^[8] Эппштейн (2007) описывает алгоритм для вычисления таблиц этого типа за линейное время для произвольных значений . ^[21] ${\displaystyle k}$ ${\displaystyle 60^{k}}$ ${\displaystyle 60^{k+1}}$ ${\displaystyle k}$ ${\displaystyle k}$

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

Хенингер, Рейнс и Слоан (2006) показывают, что когда — регулярное число, делящееся на 8, то производящая функция -мерной экстремальной четной унимодулярной решетки является -ой степенью многочлена. ^[22] ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

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

Восьмая книга « Государства » Платона включает аллегорию брака, сосредоточенную на очень регулярном числе 60 ⁴ = 12 960 000 и его делителях (см. число Платона ). Более поздние ученые прибегали как к вавилонской математике, так и к теории музыки в попытке объяснить этот отрывок. ^[24]

Некоторые виды бамбука выпускают большое количество семян синхронно (процесс, называемый мастингом ) с интервалами, которые были оценены как регулярные числа лет, с различными интервалами для разных видов, включая примеры с интервалами 10, 15, 16, 30, 32, 48, 60 и 120 лет. ^[25] Была выдвинута гипотеза, что биологический механизм для определения времени и синхронизации этого процесса поддается гладким числам и, в частности, в этом случае 5-гладким числам. Хотя предполагаемые интервалы мастинга для некоторых других видов бамбука не являются регулярными числами лет, это может быть объяснено ошибкой измерения. ^[25]

Примечания

1. Вдохновлено аналогичными диаграммами Эркки Куренниеми в «Аккорды, гаммы и решетки делителей».
2. Слоан "A051037".
3. Померанс (1995).
4. Поиск OEIS последовательностей, включающих 5-гладкость.
5. Берндт и Ранкин (1995).
6. Aaboe (1965).
7. Сакс (1947).
8. Кнут (1972).
9. Фаулер и Робсон (1998).
10. См. Conway & Guy (1996) для популярного толкования этой интерпретации. Plimpton 322 имеет другие интерпретации, о которых см. его статью, но все они включают обычные числа.
11. Кларк (1877).
12. Хонинг и Бод (2005).
13. Asmussen (2001), например, утверждает, что «в пределах любого произведения тональной музыки» все интервалы должны быть отношениями регулярных чисел, что перекликается с аналогичными утверждениями гораздо более ранних авторов, таких как Habens (1889). В современной литературе по теории музыки это утверждение часто приписывается Longuet-Higgins (1962), который использовал графическую аранжировку, тесно связанную с tonnetz, для организации 5-предельных высот.
14. Копиез (2003).
15. Вольф (2003).
16. Хэлси и Хьюитт (1972) отмечают, что это следует из теоремы Штёрмера (Størmer 1897), и приводят доказательство для этого случая; см. также Сильвер (1971).
17. Ховард и Лонгэр (1982).
18. См., например, Хеммендингер (1988) или Юэнь (1992).
19. Функция m235 в test_generators.py.
20. Джинджерич (1965).
21. Эппштейн (2007).
22. Хенингер, Рэйнс и Слоан (2006).
23. Темпертон (1992).
24. Бартон (1908); Макклейн (1974).
25. Веллер, Новак и Дэвис (2015).

Ссылки

• Aaboe, Asger (1965), «Некоторые математические таблицы Селевкидов (расширенные обратные величины и квадраты обычных чисел)», Журнал клинописных исследований , 19 (3), Американские школы восточных исследований: 79–86, doi : 10.2307/1359089, JSTOR  1359089, MR  0191779, S2CID  164195082.
• Асмуссен, Роберт (2001), Периодичность синусоидальных частот как основа для анализа гармонии барокко и классицизма: компьютерное исследование (PDF) , докторская диссертация, Университет Лидса , архивировано из оригинала (PDF) 24-04-2016 , извлечено 15-03-2007.
• Бартон, Джордж А. (1908), «О вавилонском происхождении брачного числа Платона», Журнал Американского восточного общества , 29 , Американское восточное общество: 210–219, doi :10.2307/592627, JSTOR  592627.
• Берндт, Брюс С.; Рэнкин, Роберт Александр, ред. (1995), Рамануджан: письма и комментарии , История математики, т. 9, Американское математическое общество, стр. 23, Bibcode : 1995rlc..book.....B, ISBN 978-0-8218-0470-4.
• Брюинз, Э.М. (1970), «Строительство большого стола le valeurs reciproques AO 6456», в Фине, Андре (редактор), Actes de la XVII ^e Rencontre Assyriologique Internationale , Comité belge de recherches en Mésopotamie, стр. 99– 115.
• Кларк, AR (январь 1877), "Просто интонация", Nature , 15 (377): 253, Bibcode : 1877Natur..15..253C, doi : 10.1038/015253b0.
• Конвей, Джон Х.; Гай , Ричард К. (1996), Книга чисел, Коперник, стр. 172–176, ISBN 0-387-97993-X.
• Дейкстра, Эдсгер В. (1976), «17. Упражнение, приписываемое Р. В. Хэммингу», Дисциплина программирования, Prentice-Hall, стр. 129–134, ISBN 978-0132158718
• Дейкстра, Эдсгер В. (1981), Упражнение Хэмминга в SASL (PDF) , Отчет EWD792. Первоначально частная рукописная записка.
• Эппштейн, Дэвид (2007), Задача Хэмминга с ограниченным диапазоном.
• Фаулер, Дэвид; Робсон, Элеанор (1998), «Приближения квадратного корня в старой вавилонской математике: YBC 7289 в контексте» (PDF) , Historia Mathematica , 25 (4): 366–378, doi : 10.1006/hmat.1998.2209, стр. 375.
• Джинджерич, Оуэн (1965), «Одиннадцатизначные правильные шестидесятеричные числа и их обратные», Труды Американского философского общества , 55 (8), Американское философское общество: 3–38, doi : 10.2307/1006080, JSTOR  1006080.
• Хабенс, преподобный У. Дж. (1889), «О музыкальной шкале», Труды Музыкальной Ассоциации , 16 , Королевская Музыкальная Ассоциация: 16-я сессия, стр. 1, JSTOR  765355.
• Хэлси, Г. Д.; Хьюитт, Эдвин (1972), «Больше о суперчастных отношениях в музыке», American Mathematical Monthly , 79 (10), Математическая ассоциация Америки: 1096–1100, doi : 10.2307/2317424, JSTOR  2317424, MR  0313189.
• Хеммендингер, Дэвид (1988), «Проблема Хэмминга в Прологе», ACM SIGPLAN Notices , 23 (4): 81–86, doi :10.1145/44326.44335, S2CID  28906392.
• Хенингер, Надя ; Рейнс, Э.М.; Слоан, Н.Дж.А. (2006), «О целочисленности n- ных корней производящих функций», Журнал комбинаторной теории , Серия A, 113 (8): 1732–1745, arXiv : math.NT/0509316 , doi : 10.1016/j.jcta.2006.03.018, MR  2269551, S2CID  15913795}.
• Хонинг, Алин; Бод, Ренс (2005), «Выпуклость и правильность форм музыкальных объектов», Журнал новых музыкальных исследований , 34 (3): 293–303, doi : 10.1080/09298210500280612, S2CID  16321292.
• Говард, Дебора ; Лонгэр, Малкольм (май 1982 г.), «Гармоническая пропорция и Quattro Libri Палладио », Журнал Общества историков архитектуры , 41 (2): 116–143, doi :10.2307/989675, JSTOR  989675
• Кнут, Д.Э. (1972), «Древние вавилонские алгоритмы» (PDF) , Сообщения ACM , 15 (7): 671–677, doi :10.1145/361454.361514, S2CID  7829945. Исправление появляется в CACM 19(2), 1976, в котором говорится, что табличка не содержит все 231 интересующих нас чисел. Статья (исправленная) с кратким дополнением появляется в Selected Papers on Computer Science, CSLI Lecture Notes 59, Cambridge Univ. Press, 1996, стр. 185–203, но без Приложения, которое было включено в исходную статью.
• Копьез, Рейнхард (2003), «Интонирование гармонических интервалов: способность опытных музыкантов адаптироваться к равномерной темперации и простому интонированию», Music Perception , 20 (4): 383–410, doi :10.1525/mp.2003.20.4.383
• Лонге-Хиггинс, ХК (1962), «Письмо другу-музыканту», Music Review (август): 244–248.
• Макклейн, Эрнест Г. (1974), «Музыкальные «браки» в «Государстве» Платона»", Журнал теории музыки , 18 (2), Издательство Университета Дьюка: 242–272, JSTOR  843638.
• Померанс, Карл (1995), «Роль гладких чисел в теоретико-числовых алгоритмах», Труды Международного конгресса математиков, т. 1, 2 (Цюрих, 1994) , Базель: Birkhäuser, стр. 411–422, MR  1403941.
• Сакс, А. Дж. (1947), «Вавилонские математические тексты. I. Обратные числа обычных шестидесятеричных чисел», Журнал клинописных исследований , 1 (3), Американские школы восточных исследований: 219–240, doi : 10.2307/1359434, JSTOR  1359434, MR  0022180, S2CID  163783242.
• Сильвер, А. Л. Ли (1971), «Музыкальная наука или скрипка монахини», American Mathematical Monthly , 78 (4), Математическая ассоциация Америки: 351–357, doi : 10.2307/2316896, JSTOR  2316896.
• Слоан, Н. Дж. А. (ред.), «Последовательность A051037 (5-гладкие числа)», Онлайновая энциклопедия целочисленных последовательностей , Фонд OEIS
• Стормер, Карл (1897), «Quelques theorèmes sur l'équation de Pell x ² − Dy ² = ±1 и другие приложения», Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. кл. , я (2).
• Темпертон, Клайв (1992), «Обобщенный алгоритм быстрого преобразования Фурье на простых множителях для любого N = 2 ^p 3 ^q 5 ^r », Журнал SIAM по научным и статистическим вычислениям , 13 (3): 676–686, doi : 10.1137/0913039, S2CID  14764894.
• Веллер, Карл; Новак, Мартин А.; Дэвис, Чарльз К. (май 2015 г.), «Увеличение интервалов цветения бамбуков в результате дискретного размножения», Ecology Letters , 18 (7): 653–659, Bibcode : 2015EcolL..18..653V, doi : 10.1111/ele.12442, PMID  25963600
• Вольф, Дэниел Джеймс (март 2003 г.), «Альтернативные настройки, альтернативные тональности», Contemporary Music Review , 22 (1–2): 3–14, doi :10.1080/0749446032000134715, S2CID  191457676
• Юэн, CK (1992), «Числа Хэмминга, ленивая оценка и активное избавление», ACM SIGPLAN Notices , 27 (8): 71–75, doi :10.1145/142137.142151, S2CID  18283005.

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

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