Обычный номер

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

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

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

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

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

Теория чисел

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

Первые несколько обычных чисел

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-гладкие числа.

Хотя обычные числа кажутся плотными в диапазоне от 1 до 60, они довольно редки среди больших целых чисел. Обычный номер $n=2^{i}\cdot 3^{j}\cdot 5^{k}$ меньше или равно некоторому порогу $N$ тогда и только тогда, когда точка $(i,j,k)$ принадлежит тетраэдру, ограниченному координатными плоскостями и плоскостью $$i\ln 2+j\ln 3+k\ln 5\leq \ln N,$$в чем можно убедиться, логарифмируя обе части неравенства $2^{i}\cdot 3^{j}\cdot 5^{k}\leq N$.Следовательно, количество правильных чисел, не превосходящих $N$ можно оценить как объем этого тетраэдра, который $${\frac {\log _{2}N\,\log _{3}N\,\log _{5}N}{6}}.$$Еще точнее, используя обозначение big 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$ приводится Шринивасой Рамануджаном в его первом письме Г.Х. Харди .

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

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

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

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

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

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

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

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

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

Ссылки

• Аабо, Асгер (1965), «Некоторые математические таблицы Селевкидов (расширенные обратные числа и квадраты обычных чисел)», Журнал клинописных исследований , 19 (3), Американские школы восточных исследований: 79–86, doi : 10.2307/1359089 , JSTOR   1359089 , MR   0191779 , S2CID   164195082 .
• Асмуссен, Роберт (2001), Периодичность синусоидальных частот как основа анализа барочной и классической гармонии: компьютерное исследование (PDF) , доктор философии. диссертация, Университет Лидса .
• Бартон, Джордж А. (1908), «О вавилонском происхождении брачного числа Платона», Журнал Американского восточного общества , 29 , Американское восточное общество: 210–219, doi : 10.2307/592627 , JSTOR   592627 .
• Берндт, Брюс К.; Рэнкин, Роберт Александр, ред. (1995), Рамануджан: письма и комментарии , История математики, вып. 9, Американское математическое общество, с. 23, Бибкод : 1995rlc..книга.....B , ISBN  978-0-8218-0470-4 .
• Брюинз, Э.М. (1970), «Построение большой таблицы обратных значений AO 6456», в Фине, Андре (ред.), Actes de la XVII. ^и Международная ассириологическая встреча , Бельгийский комитет по исследованию Месопотамии, стр. 99–115 .
• Кларк, А.Р. (январь 1877 г.), «Просто интонация», Nature , 15 (377): 253, Бибкод : 1877Natur..15..253C , doi : 10.1038/015253b0 .
• Конвей, Джон Х .; Гай, Ричард К. (1996), Книга чисел , Коперник, стр. 172–176 , ISBN  0-387-97993-Х .
• Дейкстра, Эдсгер В. (1976), «17. Упражнение, приписываемое Р.В. Хэммингу», Дисциплина программирования , Прентис-Холл, стр. 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), «Одиннадцатизначные правильные шестидесятеричные числа и их обратные величины», Transactions of the American Philosophical Society , 55 (8), American Philosophical Society: 3–38, doi : 10.2307/1006080 , JSTOR   1006080 .
• Хабенс, преподобный WJ (1889), «О музыкальной шкале» , Труды Музыкальной ассоциации , 16 , Королевская музыкальная ассоциация: 16-я сессия, с. 1, JSTOR   765355 .
• Хэлси, Джорджия; Хьюитт, Эдвин (1972), «Подробнее о сверхчастичных отношениях в музыке», American Mathematical Monthly , 79 (10), Mathematical Association of America: 1096–1100, doi : 10.2307/2317424 , JSTOR   2317424 , MR   0313189 .
• Хеммендингер, Дэвид (1988), «Проблема Хэмминга» в Прологе, Уведомления ACM SIGPLAN , 23 (4): 81–86, doi : 10.1145/44326.44335 , S2CID   28906392 .
• Хенингер, Надя ; Дожди, Э.М.; Слоан, NJA (2006), «О целостности корней n-й степени производящих функций», Журнал комбинаторной теории , серия A, 113 (8): 1732–1745, arXiv : math.NT/0509316 , doi : 10.1016/j .jcta.2006.03.018 , MR   2269551 , S2CID   15913795 }.
• Хонинг, Алин; Бод, Ренс (2005), «Выпуклость и правильность музыкальных объектов», Journal of New Music Research , 34 (3): 293–303, doi : 10.1080/09298210500280612 , S2CID   16321292 .
• Ховард, Дебора ; Палладио Лонгэр, Малькольм (май 1982 г.), «Гармонические пропорции и Quattro Libri », Журнал Общества историков архитектуры , 41 (2): 116–143, doi : 10.2307/989675 , JSTOR   989675
• Кнут, DE (1972), «Древние вавилонские алгоритмы» (PDF) , Communications of the 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), «Музыкальные «браки» в «Республике» Платона », Journal of Music Theory , 18 (2), Duke University Press: 242–272, JSTOR   843638 .
• Померанс, Карл (1995), «Роль гладких чисел в теоретико-числовых алгоритмах», Труды Международного конгресса математиков, Vol. 1, 2 (Цюрих, 1994) , Базель: Birkhäuser, стр. 411–422, MR   1403941 .
• Сакс, AJ (1947), «Вавилонские математические тексты. I. Обратные величины правильных шестидесятеричных чисел», Журнал клинописных исследований , 1 (3), Американские школы восточных исследований: 219–240, doi : 10.2307/1359434 , JSTOR   1359434 , МР   0022180 , S2CID   163783242 .
• Сильвер, А.Л. Ли (1971), «Музыматика или скрипка монахини», American Mathematical Monthly , 78 (4), Mathematical Association of America: 351–357, doi : 10.2307/2316896 , JSTOR   2316896 .
• Слоан, Нью-Джерси (редактор), «Последовательность A051037 (5-гладкие числа)» , Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS
• Стёрмер, Карл (1897), «Некоторые теоремы об уравнении Пелля x ² - Те ² = ±1 и другие приложения», Skrifter Videnskabs-selskabet (Christiania), Mat.-Naturv. Kl. , I (2) .
• Темпертон, Клайв (1992), «Обобщенный алгоритм БПФ с простыми коэффициентами для любого N = 2 ^п 3 ^д 5 ^р ", SIAM Journal on Scientific and Statistical Computing , 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 , ПМИД   25963600
• Вольф, Дэниел Джеймс (март 2003 г.), «Альтернативные настройки, альтернативные тональности», Contemporary Music Review , 22 (1–2): 3–14, doi : 10.1080/0749446032000134715 , S2CID   191457676
• Юэн, К.К. (1992), «Числа Хэмминга, ленивая оценка и быстрое удаление», Уведомления ACM SIGPLAN , 27 (8): 71–75, doi : 10.1145/142137.142151 , S2CID   18283005 .

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

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