Практическое число

Число такое, что оно и все меньшие числа могут быть представлены в виде суммы его различных делителей.

Демонстрация практичности числа 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. ${\displaystyle n}$ ${\displaystyle n}$

Последовательность практических чисел (последовательность 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+\sum _{i=1}^{j}d_{i}.}$$ ${\displaystyle {d_{1}<d_{2}<...<d_{j}}}$

Эта частичная характеристика была расширена и дополнена Стюартом (1954) и Серпинским (1955), которые показали, что определить, является ли число практичным, просто из его разложения на простые множители . Положительное целое число, большее единицы с разложением на простые множители (с простыми числами в отсортированном порядке ), практично тогда и только тогда, когда каждый из его простых множителей достаточно мал, чтобы иметь представление в виде суммы меньших делителей. Чтобы это было верно, первое простое число должно быть равно 2, и для каждого i от 2 до  k каждое последующее простое число должно подчиняться неравенству ${\displaystyle n=p_{1}^{\alpha _{1}}...p_{k}^{\alpha _{k}}}$ ${\displaystyle p_{1}<p_{2}<\dots <p_{k}}$ ${\displaystyle p_{i}}$ ${\displaystyle p_{i}-1}$ ${\displaystyle p_{1}}$ ${\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+\sigma (p_{1}^{\alpha _{1}})\sigma (p_{2}^{\alpha _{2}})\dots \sigma (p_{i-1}^{\alpha _{i-1}})=1+\prod _{j=1}^{i-1}{\frac {p_{j}^{\alpha _{j}+1}-1}{p_{j}-1}},}$

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

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

• Индукцией по можно показать, что . Следовательно . ${\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 (n)]}$ ${\displaystyle 1\leq q\leq \sigma (n/p_{k}^{\alpha _{k}})}$ ${\displaystyle q}$ ${\displaystyle r\in [0,\sigma (n/p_{k})]}$ ${\displaystyle m=qp_{k}^{\alpha _{k}}+r}$
• Поскольку и можно показать по индукции, что они имеют практическое значение, мы можем найти представление q в виде суммы делителей . ${\displaystyle q\leq \sigma (n/p_{k}^{\alpha _{k}})}$ ${\displaystyle n/p_{k}^{\alpha _{k}}}$ ${\displaystyle n/p_{k}^{\alpha _{k}}}$
• Так как , и так как можно показать по индукции, что это имеет практическое значение, мы можем найти представление r в виде суммы делителей . ${\displaystyle r\leq \sigma (n/p_{k})}$ ${\displaystyle n/p_{k}}$ ${\displaystyle n/p_{k}}$
• Делители, представляющие r , вместе с каждым из делителей, представляющих q , образуют представление m как сумму делителей . ${\displaystyle p_{k}^{\alpha _{k}}}$ ${\displaystyle n}$

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

• Единственное нечетное практическое число — это 1, поскольку если — нечетное число, большее 2, то 2 не может быть выражено как сумма различных делителей . Более того, Шринивасан (1948) отмечает, что, за исключением 1 и 2, каждое практическое число делится на 4 или 6 (или на оба). ${\displaystyle n}$ ${\displaystyle n}$
• Произведение двух практических чисел также является практическим числом. ^[5] Эквивалентно, множество всех практических чисел замкнуто относительно умножения. Более строго, наименьшее общее кратное любых двух практических чисел также является практическим числом.
• Из приведенной выше характеристики Стюарта и Серпинского видно, что если — практическое число и — один из его делителей, то также должно быть практическим числом. ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle n\cdot 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...

• Каждое положительное целое число имеет практическое кратное. Например, для каждого целого числа его кратное является практическим. ^[6] ${\displaystyle n}$ ${\displaystyle 2^{\lfloor \log _{2}n\rfloor }n}$

Связь с другими классами чисел

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

• Из приведенных выше свойств с практическим числом и одним из его делителей (то есть ) тогда также должно быть практическим числом, поэтому шесть раз каждая степень числа 3 должны быть практическим числом, так же как и шесть раз каждая степень числа 2. ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle d|n}$ ${\displaystyle n\cdot d}$
• Каждая степень двойки является практическим числом. ^[7] Степени двойки тривиально удовлетворяют характеристике практических чисел с точки зрения их простых множителей: единственное простое число в их множителях, p ₁ , равно двум, как и требуется.
• Каждое четное совершенное число также является практическим числом. ^[7] Это следует из результата Леонарда Эйлера о том, что четное совершенное число должно иметь вид . Нечетная часть этого разложения равна сумме делителей четной части, поэтому каждый нечетный простой множитель такого числа должен быть не более суммы делителей четной части числа. Следовательно, это число должно удовлетворять характеристике практических чисел. Подобный аргумент можно использовать, чтобы показать, что четное совершенное число при делении на 2 больше не является практическим числом. Следовательно, каждое четное совершенное число также является примитивным практическим числом. ${\displaystyle 2^{k-1}(2^{k}-1)}$
• Каждый первообразный (произведение первых простых чисел, для некоторых ) является практическим. ^[7] Для первых двух первообразных, двух и шести, это ясно. Каждый последующий первообразный образуется путем умножения простого числа на меньший первообразный, который делится как на два, так и на следующее меньшее простое число, . По постулату Бертрана , , поэтому каждый последующий простой множитель в первообразном меньше одного из делителей предыдущего первообразного. По индукции следует, что каждый первообразный удовлетворяет характеристике практических чисел. Поскольку первообразный по определению является свободным от квадратов, он также является примитивным практическим числом. ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle p_{i}}$ ${\displaystyle p_{i-1}}$ ${\displaystyle p_{i}<2p_{i-1}}$
• Обобщая первообразные , любое число, которое является произведением ненулевых степеней первых простых чисел, также должно быть практичным. Это включает в себя высокосоставные числа Рамануджана (числа с большим количеством делителей, чем любое меньшее положительное целое число), а также факториальные числа. ^[7] ${\displaystyle k}$

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

Если практично, то любое рациональное число вида с может быть представлено в виде суммы , где каждый является отдельным делителем . Каждый член в этой сумме упрощается до единичной дроби , поэтому такая сумма обеспечивает представление в виде египетской дроби . Например, ${\displaystyle n}$ ${\displaystyle m/n}$ ${\displaystyle m<n}$ ${\textstyle \sum d_{i}/n}$ ${\displaystyle d_{i}}$ ${\displaystyle n}$ ${\displaystyle m/n}$ $${\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) показал, что каждое рациональное число имеет представление в виде египетской дроби с членами. Доказательство включает в себя нахождение последовательности практических чисел со свойством, что каждое число, меньшее , может быть записано в виде суммы различных делителей . Затем выбирается так, что , и делится, давая частное и остаток . Из этих выборов следует, что . Разложение обоих числителей в правой части этой формулы в суммы делителей приводит к желаемому представлению египетской дроби. Тененбаум и Йокота (1990) используют похожую технику, включающую другую последовательность практических чисел, чтобы показать, что каждое рациональное число имеет представление в виде египетской дроби, в которой наибольший знаменатель равен . ${\displaystyle x/y}$ ${\displaystyle O({\sqrt {\log y}})}$ ${\displaystyle n_{i}}$ ${\displaystyle n_{i}}$ ${\displaystyle O({\sqrt {\log n_{i-1}}})}$ ${\displaystyle n_{i}}$ ${\displaystyle i}$ ${\displaystyle n_{i-1}<y<n_{i}}$ ${\displaystyle xn_{i}}$ ${\displaystyle y}$ ${\displaystyle q}$ ${\displaystyle r}$ ${\displaystyle {\frac {x}{y}}={\frac {q}{n_{i}}}+{\frac {r}{yn_{i}}}}$ ${\displaystyle n_{i}}$ ${\displaystyle x/y}$ ${\displaystyle O(y\log ^{2}y/\log \log y)}$

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

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

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

Давайте посчитаем, сколько практических чисел не превышают . Маргенштерн (1991) предположил, что является асимптотическим для для некоторой константы , формулы, которая напоминает теорему о простых числах , усиливая более раннее утверждение Эрдёша и Локстона (1979) о том, что практические числа имеют нулевую плотность в целых числах. Улучшая оценку Тененбаума (1986), Сайас (1997) обнаружил, что имеет порядок величины . Вайнгартнер (2015) доказал гипотезу Маргенштерна. Мы имеем ^[12] где ^[13] Таким образом, практических чисел примерно на 33,6% больше, чем простых чисел. Точное значение постоянного множителя дается выражением ^[14] где — константа Эйлера–Маскерони и пробегает простые числа. ${\displaystyle p(x)}$ ${\displaystyle x}$ ${\displaystyle p(x)}$ ${\displaystyle cx/\log x}$ ${\displaystyle c}$ ${\displaystyle p(x)}$ ${\displaystyle x/\log x}$ $${\displaystyle p(x)={\frac {cx}{\log x}}\left(1+O\!\left({\frac {\log \log x}{\log x}}\right)\right),}$$ ${\displaystyle c=1.33607...}$ ${\displaystyle c}$ $${\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}$

Как и в случае с простыми числами в арифметической прогрессии, если даны два натуральных числа и , имеем ^[15] Постоянный множитель положителен тогда и только тогда, когда существует более одного практического числа, сравнимого с . Если , то . Например, около 38,26% практических чисел имеют последнюю десятичную цифру 0, в то время как последние цифры 2, 4, 6, 8 встречаются с одинаковой относительной частотой 15,43%. ${\displaystyle a}$ ${\displaystyle q}$ $${\displaystyle |\{n\leq x:n{\text{ practical and }}n\equiv a{\bmod {q}}\}|={\frac {c_{q,a}x}{\log x}}+O_{q}\left({\frac {x}{(\log x)^{2}}}\right).}$$ ${\displaystyle c_{q,a}}$ ${\displaystyle a{\bmod {q}}}$ ${\displaystyle \gcd(q,a)=\gcd(q,b)}$ ${\displaystyle c_{q,a}=c_{q,b}}$

Примечания

1. Маргенштерн (1991) цитирует Робинсона (1979) и Хейворта (1980) для названия «панарифмические числа».
2. Sigler (2002).
3. Хаусман и Шапиро (1984); Маргенштерн (1991); Мелфи (1996); Сайас (1997).
4. Стюарт (1954); Серпинский (1955).
5. Маргенштерн (1991).
6. Эппштейн (2021).
7. Шринивасан (1948).
8. Сан, Чжи-Вэй, Гипотеза о дробях единиц, включающих простые числа (PDF) , заархивировано из оригинала (PDF) 2018-10-19 , извлечено 2016-11-22
9. Мелфи (1996).
10. Мелфи (1995)
11. Вайнгартнер (2022).
12. Вайнгартнер (2015) и замечание 1 Pomerance & Weingartner (2021)
13. Вайнгартнер (2020).
14. Вайнгартнер (2019).
15. Вайнгартнер (2021)

Ссылки

• Эппштейн, Дэвид (2021), «Египетские дроби со знаменателями из последовательностей, замкнутых относительно удвоения», Журнал целочисленных последовательностей , 24 : 21.8.8, arXiv : 2109.12217
• Эрдёш, Пол ; Локстон, Дж. Х. (1979), «Некоторые проблемы в partitio numerorum», Журнал Австралийского математического общества, Серия A , 27 (3): 319–331, doi : 10.1017/S144678870001243X.
• Хейворт, М. Р. (1980), «Еще о панарифмических числах», New Zealand Math. Mag. , 17 (1): 24–28. Как цитирует Маргенштерн (1991).
• Хаусман, Мириам; Шапиро, Гарольд Н. (1984), «О практических числах», Сообщения по чистой и прикладной математике , 37 (5): 705–713, doi :10.1002/cpa.3160370507, MR  0752596.
• Маргенштерн, Морис (1984), «Результаты и предположения о практических числах», Comptes Rendus de l'Académie des Sciences, Série I , 299 (18): 895–898. Как цитирует Маргенштерн (1991).
• Маргенштерн, Морис (1991), «Les nombres pratiques: теория, наблюдения и гипотезы», Journal of Number Theory , 37 (1): 1–36, doi : 10.1016/S0022-314X(05)80022-8 , MR  1089787.
• Мельфи, Джузеппе (1995), «Обзор практических чисел», Rend. Sem. Mat. Univ. Pol. Torino , 53 (4): 347–359.
• Мельфи, Джузеппе (1996), «О двух гипотезах о практических числах», Журнал теории чисел , 56 (1): 205–210, doi : 10.1006/jnth.1996.0012 , MR  1370203.
• Митринович, Драгослав С.; Шандор, Йожеф; Крстичи, Борислав (1996), "III.50 Практические числа", Справочник по теории чисел, Том 1 , Математика и ее приложения, т. 351, Kluwer Academic Publishers, стр. 118–119, ISBN 978-0-7923-3823-9.
• Померанс, К.; Вайнгартнер, А. (2021), «О простых числах и практических числах», Ramanujan Journal , 57 (3): 981–1000, arXiv : 2007.11062 , doi : 10.1007/s11139-020-00354-y, S2CID  220686445.
• Робинсон, ДФ (1979), «Египетские дроби через греческую теорию чисел», New Zealand Math. Mag. , 16 (2): 47–52. Цитируется Маргенштерном (1991) и Митриновичем, Шандором и Крстичи (1996).
• Сайас, Эрик (1997), «Entiers à diviseurs Denses, I», Journal of Number Theory , 62 (1): 163–191, doi : 10.1006/jnth.1997.2057 , MR  1430008.
• Сиглер, Лоуренс Э. (пер.) (2002), Liber Abaci Фибоначчи , Springer-Verlag, стр. 119–121, ISBN 0-387-95419-8.
• Серпинский, Вацлав (1955), «Sur une proprieté des nombres naturals», Annali di Matematica Pura ed Applicata , 39 (1): 69–74, doi : 10.1007/BF02410762 , S2CID  121592840.
• Шринивасан, AK (1948), «Практические числа» (PDF) , Current Science , 17 : 179–180, MR  0027799, архивировано из оригинала (PDF) 2016-03-05.
• Стюарт, Б. М. (1954), «Суммы различных делителей», American Journal of Mathematics , 76 (4), Издательство Университета Джонса Хопкинса: 779–785, doi : 10.2307/2372651, JSTOR  2372651, MR  0064800.
• Тененбаум, Г. (1986), «Sur un problème de crible et ses application», Ann. наук. Эколь Норм. Как дела. (4) , 19 (1 ): 1–30, doi : 10.24033/asens.1502 , MR  0860809.
• Тененбаум, Г.; Йокота, Х. (1990), «Длина и знаменатели египетских дробей», Журнал теории чисел , 35 (2): 150–156, doi : 10.1016/0022-314X(90)90109-5 , MR  1057319.
• Восе, М. (1985), "Египетские дроби", Бюллетень Лондонского математического общества , 17 (1): 21, doi :10.1112/blms/17.1.21, MR  0766441.
• Вайнгартнер, А. (2015), «Практические числа и распределение делителей», The Quarterly Journal of Mathematics , 66 (2): 743–758, arXiv : 1405.2585 , doi : 10.1093/qmath/hav006.
• Вайнгартнер, А. (2019), «О постоянном множителе в нескольких связанных асимптотических оценках», Математика вычислений , 88 (318): 1883–1902, arXiv : 1705.06349 , doi : 10.1090/mcom/3402, S2CID  85532616.
• Вайнгартнер, А. (2020), «Постоянный множитель в асимптотике для практических чисел», Международный журнал теории чисел , 16 (3): 629–638, arXiv : 1906.07819 , doi : 10.1142/S1793042120500311, S2CID  195069356.
• Вайнгартнер, А. (2021), «Расширение теоремы Зигеля-Вальфиса», Труды Американского математического общества , 149 (11): 4699–4708, arXiv : 2011.06627 , doi : 10.1090/proc/15607, S2CID  226956079.
• Вайнгартнер, А. (2022), «Довольно гладкие числа в коротких интервалах», Ramanujan Journal , 60 (2): 447–453, arXiv : 2105.13568 , doi : 10.1007/s11139-022-00552-w, S2CID  235247868.

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

• Таблицы практических чисел. Архивировано 26 декабря 2017 г. на Wayback Machine. Составил Джузеппе Мельфи.
• Практические числа на PlanetMath .
• Вайсштейн, Эрик В. , «Практическое число», MathWorld