Практический номер - Practical number

Демонстрация практичности числа 12

В теория чисел, а практический номер или же панарифмическое число^[1] положительное целое число п такие, что все меньшие положительные целые числа могут быть представлены как суммы различных делители из п. Например, 12 - это практическое число, потому что все числа от 1 до 11 могут быть выражены как суммы его делителей 1, 2, 3, 4 и 6: так же, как и сами эти делители, мы имеем 5 = 3 + 2, 7 = 6 + 1, 8 = 6 + 2, 9 = 6 + 3, 10 = 6 + 3 + 1 и 11 = 6 + 3 + 2.

Последовательность практических чисел (последовательность A005153 в OEIS ) начинается

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, 40, 42, 48, 54, 56, 60, 64, 66, 72, 78, 80, 84, 88, 90, 96, 100, 104, 108, 112, 120, 126, 128, 132, 140, 144, 150....

Практические числа использовались Фибоначчи в его Liber Abaci (1202) в связи с проблемой представления рациональных чисел в виде Египетские фракции. Фибоначчи формально не определяет практические числа, но дает таблицу разложения египетских дробей для дробей с практическими знаменателями.^[2]

Название «практический номер» связано с Шринивасан (1948). Он отметил, что «подразделение денег, веса и меры включает такие числа, как 4, 12, 16, 20 и 28, которые обычно считаются настолько неудобными, что заслуживают замены степенями 10». Он заново открыл теоретико-числовое свойство таких чисел и был первым, кто попытался классифицировать эти числа, что было завершено Стюарт (1954) и Серпинский (1955). Эта характеристика позволяет определить, применимо ли число, исследуя его разложение на простые множители. Каждый даже идеальное число и каждый сила двух тоже практическое число.

Было также показано, что практические числа аналогичны простые числа во многих своих свойствах.^[3]

Характеристика практических чисел

Оригинальная характеристика Шринивасан (1948) заявил, что практическое число не может быть недостаточное количество, то есть такое, у которого сумма всех делителей (включая 1 и себя) меньше удвоенного числа, если дефект не равен единице. Если упорядоченный набор всех делителей практического числа ${ displaystyle n}$ является ${ displaystyle {d_ {1}, d_ {2}, ..., d_ {j}}}$ с ${ displaystyle d_ {1} = 1}$ и ${ displaystyle d_ {j} = n}$, то утверждение Шринивасана можно выразить неравенством

${ Displaystyle 2n Leq 1+ сумма _ {я = 1} ^ {j} d_ {я}}$.

Другими словами, упорядоченная последовательность всех делителей ${ displaystyle {d_ {1}$ практического числа должно быть полная подпоследовательность.

Эта частичная характеристика была расширена и дополнена Стюарт (1954) и Серпинский (1955) кто показал, что определить практичность числа несложно по его простые множители.Положительное целое число больше единицы с разложением на простые множители. ${ displaystyle n = p_ {1} ^ { alpha _ {1}} ... p_ {k} ^ { alpha _ {k}}}$ (с простыми числами в отсортированном порядке ${ displaystyle p_ {1}$) практично тогда и только тогда, когда каждый из его простых множителей ${ displaystyle p_ {i}}$ достаточно мал для ${ displaystyle p_ {i} -1}$ иметь представление в виде суммы меньших делителей. Чтобы это было правдой, первое простое число ${ displaystyle p_ {1}}$ должен равняться 2 и для каждого я от 2 доk, каждое последующее простое число ${ displaystyle p_ {i}}$ должен подчиняться неравенству

${ displaystyle p_ {i} leq 1+ sigma (p_ {1} ^ { alpha _ {1}} p_ {2} ^ { alpha _ {2}} dots p_ {i-1} ^ { alpha _ {i-1}}) = 1+ prod _ {j = 1} ^ {i-1} { frac {p_ {j} ^ { alpha _ {j} +1} -1} { p_ {j} -1}},}$

куда ${ Displaystyle sigma (х)}$ обозначает сумма делителей из Икс. Например, 2 × 3² × 29 × 823 = 429606 является практичным, потому что неравенство выше выполняется для каждого из его простых множителей: 3 ≤ σ (2) + 1 = 4, 29 ≤ σ (2 × 3²) + 1 = 40 и 823 ≤ σ (2 × 3² × 29) + 1 = 1171.

Указанное выше условие является необходимым и достаточным для того, чтобы число было практичным. В одном направлении это условие необходимо для того, чтобы можно было представить ${ displaystyle p_ {i} -1}$ как сумму делителей п, потому что если бы неравенство не выполнялось, то даже сложение всех меньших делителей дало бы сумму, слишком малую для достижения ${ displaystyle p_ {i} -1}$. В противном случае, как показывает индукция, условие достаточно. Более сильно, если факторизация п удовлетворяет указанному выше условию, то любой ${ Displaystyle м Leq sigma (п)}$ можно представить в виде суммы делителей п, выполнив следующую последовательность шагов:^[4]

• Индукцией по ${ displaystyle j in [1, alpha _ {k}]}$, можно показать, что ${ displaystyle p_ {k} ^ {j} leq 1+ sigma (n / p_ {k} ^ { alpha _ {k} - (j-1)})}$. Следовательно ${ displaystyle p_ {k} ^ { alpha _ {k}} leq 1+ sigma (n / p_ {k})}$.
• Поскольку внутренности ${ displaystyle [qp_ {k} ^ { alpha _ {k}}, qp_ {k} ^ { alpha _ {k}} + sigma (n / p_ {k})]}$ крышка ${ Displaystyle [1, sigma (п)]}$ за ${ displaystyle 1 leq q leq sigma (п / p_ {k} ^ { alpha _ {k}})}$, есть такая ${ displaystyle q}$ и немного ${ Displaystyle г в [0, sigma (п / р_ {к})]}$ такой, что ${ displaystyle m = qp_ {k} ^ { alpha _ {k}} + r}$.
• С ${ Displaystyle д Leq сигма (п / р_ {к} ^ { альфа _ {к}})}$ и ${ displaystyle n / p_ {k} ^ { alpha _ {k}}}$ можно показать по индукции как практичный, мы можем найти представление q в виде суммы делителей ${ displaystyle n / p_ {k} ^ { alpha _ {k}}}$.
• С ${ Displaystyle г Leq сигма (п / р_ {к})}$, и с тех пор ${ displaystyle n / p_ {k}}$ можно показать по индукции как практичный, мы можем найти представление р как сумму делителей ${ displaystyle n / p_ {k}}$.
• Дивизоры, представляющие р, вместе с ${ displaystyle p_ {k} ^ { alpha _ {k}}}$ умножить на каждый из делителей, представляющих qвместе образуют представление м в виде суммы делителей п.

Характеристики

• Единственное нечетное практическое число - 1, потому что если п > 2 - нечетное число, тогда 2 нельзя выразить как сумму различных делителейп. Сильнее, Шринивасан (1948) отмечает, что кроме 1 и 2, каждое практическое число делится на 4 или 6 (или на оба).
• Произведение двух практических чисел также является практическим числом.^[5] Сильнее наименьший общий множитель любых двух практических чисел также является практическим числом. Эквивалентно, набор всех практических чисел замкнут при умножении.
• Из приведенной выше характеристики Стюарта и Серпинского видно, что если п это практическое число и d является одним из его делителей, то н * д также должно быть практическое число.
• В наборе всех практических чисел есть примитивный набор практических чисел. Примитивный практический номер либо практичен, либо свободный от квадратов или практично и при делении на любой из основных факторов, чьи факторизация показатель степени больше 1 больше не применяется. Последовательность примитивных практических чисел (последовательность A267124 в OEIS ) начинается

1, 2, 6, 20, 28, 30, 42, 66, 78, 88, 104, 140, 204, 210, 220, 228, 260, 272, 276, 304, 306, 308, 330, 340, 342, 348, 364, 368, 380, 390, 414, 460 ...

Отношение к другим классам номеров

Несколько других примечательных наборов целых чисел состоят только из практических чисел:

• Из вышеуказанных свойств с п практический номер и d один из его делителей (то есть d | п) тогда н * д также должно быть практическим числом, поэтому шесть раз в каждой степени 3 должно быть практическим числом, а также шесть раз в каждой степени двойки.
• Каждый сила двух это практическое число.^[6] Степени двойки тривиально удовлетворяют характеристике практических чисел в терминах их простых факторизаций: единственное простое число в их факторизациях, п₁, равно двум, если требуется.
• Каждый даже идеальное число тоже практическое число.^[6] Это следует из Леонард Эйлер В результате четное совершенное число должно иметь вид 2^п − 1(2^п - 1). Нечетная часть этой факторизации равна сумме делителей четной части, поэтому каждый нечетный простой делитель такого числа должен быть не более чем суммой делителей четной части числа. Следовательно, это число должно соответствовать характеристике практических чисел.
• Каждый первобытный (продукт первого я простые числа, для некоторых я) практично.^[6] Для первых двух примориалов, второго и шестого, это ясно. Каждый последующий примориал формируется путем умножения простого числа. п_я на меньшее число, которое делится как на два, так и на следующее меньшее простое число, п_я − 1. К Постулат Бертрана, п_я < 2п_я − 1, поэтому каждый последующий простой множитель в примориале меньше одного из делителей предыдущего первичного. По индукции отсюда следует, что каждый примориал удовлетворяет характеристике практических чисел. Поскольку примитив по определению не содержит квадратов, он также является примитивным практическим числом.
• Обобщая примитивы, любое число, являющееся произведением ненулевых степеней первого k простые числа также должны быть практичными. Это включает в себя Рамануджан с очень сложные числа (числа с большим количеством делителей, чем любое меньшее положительное целое число), а также факториал числа.^[6]

Практические числа и египетские дроби

Если п практично, то любой Рациональное число формы м/п с м < п можно представить в виде суммы ∑d_я/п где каждый d_я является отличным делителем п. Каждый член в этой сумме упрощается до единичная дробь, поэтому такая сумма дает представление м/п как Египетская фракция. Например,

${ displaystyle { frac {13} {20}} = { frac {10} {20}} + { frac {2} {20}} + { frac {1} {20}} = { frac {1} {2}} + { frac {1} {10}} + { frac {1} {20}}.}$

Фибоначчи в своей книге 1202 г. Liber Abaci^[2] перечисляет несколько методов для нахождения египетских представлений дробей рационального числа. Из них первый - проверить, является ли само число уже единичной дробью, а второй - найти представление числителя в виде суммы делителей знаменателя, как описано выше. Этот метод гарантированно работает только для практичных знаменателей. Фибоначчи предоставляет таблицы этих представлений для дробей, имеющих в качестве знаменателя практические числа 6, 8, 12, 20, 24, 60 и 100.

Восе (1985) показал, что каждое число Икс/у имеет представление египетской фракции с ${ Displaystyle scriptstyle O ({ sqrt { log y}})}$ термины. Доказательство включает в себя поиск последовательности практических чисел. п_я со свойством, что каждое число меньше чем п_я можно записать как сумму ${ displaystyle scriptstyle O ({ sqrt { log n_ {i-1}}})}$ различные делители п_я. Потом, я выбирается так, чтобы п_я − 1 < у ≤ п_я, и xn_я делится на у дает частное q и остальное р. Из этих выборов следует, что ${ displaystyle scriptstyle { frac {x} {y}} = { frac {q} {n_ {i}}} + { frac {r} {yn_ {i}}}}$. Раскладывая оба числителя в правой части этой формулы в суммы делителей п_я приводит к желаемому представлению египетской дроби. Тененбаум и Йокота (1990) используйте аналогичную технику с использованием другой последовательности практических чисел, чтобы показать, что каждое число Икс/у имеет египетское представление дроби, в котором наибольший знаменатель ${ Displaystyle scriptstyle O ({ гидроразрыва {y log ^ {2} y} { log log y}})}$.

Согласно гипотезе сентября 2015 г. Чжи-Вэй Сунь,^[7] каждое положительное рациональное число имеет представление египетской дроби, в котором каждый знаменатель является практическим числом. Есть доказательство гипотезы о Дэвид Эппштейн блог.^[8]

Аналогии с простыми числами

Одна из причин интереса к практическим числам состоит в том, что многие из их свойств аналогичны свойствам простые числа. Действительно, теоремы, аналогичные Гипотеза Гольдбаха и гипотеза о простых близнецах известны практическими числами: каждое положительное четное целое число является суммой двух практических чисел, и существует бесконечно много троек практических чисел Икс − 2, Икс, Икс + 2.^[9] Мелфи также показал, что существует бесконечно много практических Числа Фибоначчи (последовательность A124105 в OEIS ); аналогичный вопрос о существовании бесконечно многих Простые числа Фибоначчи открыт. Хаусман и Шапиро (1984) показал, что в интервале [Икс²,(Икс + 1)²] для любого положительного реального Икс, результат аналогичен Гипотеза Лежандра для простых чисел. Этот результат о практических числах на коротких интервалах впоследствии улучшил Мелфи, который доказал, что ^[10] что если ${ displaystyle s_ {n}}$ - последовательность практических чисел, то для достаточно больших п и для подходящего А,

${ displaystyle s_ {n + 1} -s_ {n}$

Позволять п(Икс) посчитайте, сколько практических чисел не большеИкс.Маргенштерн (1991) предположил, что п(Икс) асимптотична сх/бревноИкс для некоторой постоянной c, формула, напоминающая теорема о простых числах, усиливая ранее утвержденные Эрдеш и Локстон (1979) что практические числа имеют нулевую плотность в целых числах. Тененбаум (1986), Сайас (1997) обнаружили, что п(Икс) имеет порядок величины Икс/бревноИкс.Вайнгартнер (2015) доказал гипотезу Маргенштерна, показав, что

${ displaystyle p (x) = { frac {cx} { log x}} left (1 + O ! left ({ frac { log log x} { log x}} right) верно),}$

куда ${ displaystyle c = 1,33607 ...}$^[11] Таким образом, практических чисел примерно на 33,6% больше, чем простых. Точное значение постоянного множителя ${ displaystyle c}$ дан кем-то^[12]

${ displaystyle c = { frac {1} {1-e ^ {- gamma}}} sum _ {n { text {Practical}}} { frac {1} {n}} { Biggl (} sum _ {p leq sigma (n) +1} { frac { log p} {p-1}} - log n { Biggr)} prod _ {p leq sigma ( n) +1} left (1 - { frac {1} {p}} right),}$

куда ${ displaystyle gamma}$ это Константа Эйлера – Маскерони и ${ displaystyle p}$ пробегает простые числа.

Примечания

Рекомендации

• Эрдеш, Пол; Локстон, Дж. Х. (1979), "Некоторые проблемы in partitio numerorum", Журнал Австралийского математического общества, серия A, 27 (3): 319–331, Дои:10.1017 / S144678870001243X.
• Хейворт, М. Р. (1980), "Подробнее о панарифмических числах", New Zealand Math. Mag., 17 (1): 24–28. Как цитирует Маргенштерн (1991).
• Хаусман, Мириам; Шапиро, Гарольд Н. (1984), «О практических числах», Сообщения по чистой и прикладной математике, 37 (5): 705–713, Дои:10.1002 / cpa.3160370507, МИСТЕР  0752596.
• Мардженштерн, Морис (1984), «Результаты и предположения о практических занятиях», Comptes Rendus de l'Académie des Sciences, Série I, 299 (18): 895–898. Как цитирует Маргенштерн (1991).
• Мардженштерн, Морис (1991), «Les nombres pratiques: теория, наблюдения и предположения», Журнал теории чисел, 37 (1): 1–36, Дои:10.1016 / S0022-314X (05) 80022-8, МИСТЕР  1089787.
• Мельфи, Джузеппе (1995), "Обзор практических чисел", Ренд. Сем. Мат. Univ. Pol. Турин, 53 (4): 347–359.
• Мелфи, Джузеппе (1996), "О двух предположениях о практических числах", Журнал теории чисел, 56 (1): 205–210, Дои:10.1006 / jnth.1996.0012, МИСТЕР  1370203.
• Митринович, Драгослав С .; Шандор, Йожеф; Crstici, Борислав (1996), "III.50 Практические числа", Справочник по теории чисел, Том 1, Математика и ее приложения, 351, Kluwer Academic Publishers, стр. 118–119, ISBN  978-0-7923-3823-9.
• Робинсон, Д. Ф. (1979), «Египетские дроби с помощью греческой теории чисел», New Zealand Math. Mag., 16 (2): 47–52. Как цитирует Маргенштерн (1991) и Митринович, Шандор и Крстичи (1996).
• Сайас, Эрик (1997), "Entiers à diviseurs denses, I", Журнал теории чисел, 62 (1): 163–191, Дои:10.1006 / jnth.1997.2057, МИСТЕР  1430008.
• Сиглер, Лоуренс Э. (пер.) (2002), Liber Abaci Фибоначчи, Springer-Verlag, стр. 119–121, ISBN  0-387-95419-8.
• Серпинский, Вацлав (1955), "Sur une propriété des nombres naturels", Annali di Matematica Pura ed Applicata, 39 (1): 69–74, Дои:10.1007 / BF02410762.
• Сринивасан, А. К. (1948), «Практические цифры» (PDF), Текущая наука, 17: 179–180, МИСТЕР  0027799.
• Стюарт, Б.М. (1954), «Суммы различных делителей», Американский журнал математики, Издательство Университета Джона Хопкинса, 76 (4): 779–785, Дои:10.2307/2372651, JSTOR  2372651, МИСТЕР  0064800.
• Тененбаум, Г. (1986), "Sur un problème de crible et ses applications", Анна. Sci. École Norm. Как дела. (4), 19 (1): 1–30, МИСТЕР  0860809.
• Тененбаум, Г.; Йокота, Х. (1990), "Длина и знаменатели египетских дробей", Журнал теории чисел, 35 (2): 150–156, Дои:10.1016 / 0022-314X (90) 90109-5, МИСТЕР  1057319.
• Восе, М. (1985), «Египетские фракции», Бюллетень Лондонского математического общества, 17 (1): 21, Дои:10.1112 / blms / 17.1.21, МИСТЕР  0766441.
• Weingartner, A. (2015), "Практические числа и распределение делителей", Ежеквартальный журнал математики, 66 (2): 743–758, arXiv:1405.2585, Дои:10.1093 / qmath / hav006.
• Weingartner, A. (2019), "О постоянном множителе в нескольких связанных асимптотических оценках", Математика вычислений, 88 (318): 1883–1902, arXiv:1705.06349, Дои:10.1090 / mcom / 3402.
• Вайнгартнер, А. (2020), «Постоянный множитель в асимптотике для практических чисел», Международный журнал теории чисел, 16 (3): 629–638, arXiv:1906.07819, Дои:10.1142 / S1793042120500311.

внешняя ссылка

• Таблицы практических чисел составлено Джузеппе Мельфи.
• Практический номер в PlanetMath.
• Вайсштейн, Эрик В. «Практический номер». MathWorld.