Практичное число
![](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/thumb/c/c1/Practical_number_Cuisenaire_rods_12.png/220px-Practical_number_Cuisenaire_rods_12.png)
Практичное число или панаритмичное число[1] — это положительное целое число n, такое что все меньшие положительные целые числа могут быть представлены в виде суммы различных делителей числа n. Например, 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].
Название «практичное число» дал Шринивасан[3]. Он заметил, что «разбиение денег, веса и других мер, использующие числа, такие как 4, 12, 16, 20 и 28, которые обычно так неудобны, что заслуживают замены на степени 10.» Он переоткрыл ряд теоретических свойств таких чисел и первым попытался классифицировать эти числа, а Стюарт[4] и Серпинский[5] завершили классификацию. Определение практичных чисел делает возможным определить, является ли число практичным путём просмотра разложения числа на простые множители. Лю��ое чётное совершенное число и любая степень двойки является практичным числом.
Можно показать, что практичные числа аналогичны простым числам во многих отношениях[6].
Описание практичных чисел
[править | править код]Исходное описание Шринивасана[3] утверждает, что практичное число (кроме степени двойки) не может быть недостаточным числом. Если для практичного числа выписать упорядоченное множество делителей , где и , то утверждение Шринивасана можно выразить неравенством
- .
Другими словами, упорядоченная последовательность всех делителей практичного числа должна быть полной подпоследовательностью.
Это определение расширили и завершили Стюарт[4] и Серпинский[5], которые показали, что определение, является ли число практичным, определяется его разложением на простые делители. Положительное целое число, большее единицы с разложением (с сортировкой простых делителей по возрастанию ), является практичным тогда и только тогда, когда каждый его простой делитель достаточно мал, чтобы имело представление в виде суммы меньших делителей. Чтобы это было верно, первое простое число должно быть равно 2, а для любого i от 2 до k, для каждого следующего простого числа должно выполняться неравенство
где означает сумму делителей числа x. Например, является практичным, поскольку неравенство выполняется для каждого простого делителя: и .
Условие, приведённое выше, является необходимым и достаточным. В одном направлении, это условие является необходимым, чтобы можно было представить в виде суммы делителей числа n, поскольку в случае нарушения неравенства сложение всех меньших делителей дало бы сумму, слишком маленькую, чтобы получить . В другом направлении, условие является достаточным, что можно получит�� по индукции. Более строго, если разложение числа n удовлетворяет вышеприведённому условию, то любое число может быть представлено в виде суммы делителей числа n после следующих шагов[4][5]:
- Пусть , и пусть .
- Учитывая, что можно показать по индукции, что и являются практичными, мы можем найти представление q в виде суммы делителей .
- Учитывая, что можно показать по индукции, что и являются практичными, мы можем найти представление r в виде суммы делителей .
- Представление в виде делителей r, вместе с коэффициентом для каждого делителя представления в виде делителей q, вместе образуют представление m в виде суммы делителей n.
Свойства
[править | править код]- Единственное нечётное практичное число — 1, поскольку если n > 2 является нечётным числом, то 2 нельзя представить в виде суммы различных делителей числа n. Шринивасан[3] заметил, что отличные от 1 и 2 практичные числа делятся на 4 и/или 6.
- Произведение двух практичных чисел является также практичным числом[7]. Более сильное утверждение, наименьшее общее кратное любых двух практичных чисел, является также практичным числом. Эквивалентно, множество всех практичных чисел замкнуто по умножению.
- Из описания чисел Стюартом и Серпинским можно видеть, что в случае, когда n является практичным числом, а d является одним из его делителей, число n*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 ...
Связь с другими классами чисел
[править | править код]Несколько других достойных внимания множеств целых чисел состоят исключительно из практичных чисел:
- Из свойств, приведённых выше, для практичного числа n и одного из его делителей d (то есть, d|n) число n*d должно также быть практичным, так что помноженная на 6 любая степень числа 3 должна быть практичным числом, как и помноженная на 6 любая степень числа 2.
- Любая степень двойки является практичным числом [3]. Степень двойки тривиально удовлетворяет описанию практичных чисел в терминах разложения целых чисел — все простые числа в разложении числа, p1, равны двум, что и требуется.
- Любое чётное совершенное число является также практичным числом[3]. Это следует из результата Эйлера, что чётное совершенное число должно иметь вид . Нечётная часть этого разложения равна сумме делителей чётной части, так что любое нечётный простой делитель такого числа должен быть не больше суммы делителей чётной части числа. Таким образом, это число должно удовлетворять описанию практичных чисел.
- Любой праймориал (произведение первых i простых для некоторого числа i) является практичным числом[3]. Для первых двух праймориалов, двойки и шестёрки это ясно. Каждый последующий праймориал образуется умножением простого числа pi на меньший праймориал, который делится как на двойку, так и на предыдущее простое число . Согласно постулату Бертрана , так что каждый предшествующий простой делитель праймориала меньше, чем один из делителей предыдущего праймориала. По индукции, из этого следует, что любой праймориал удовлетворяет описанию практичных чисел. Поскольку праймориал по определению свободен от квадратов, он также является простым практичным числом.
- Обобщая праймориалы, любое число, являющееся произведением ненулевых степеней первых k простых чисел, должно быть практичным. В это множество попадают сверхсоставные числа Рамануджана (числа с количеством делителей, большим любого меньшего положительного числа), а также факториалы[3].
Практические числа и египетские дроби
[править | править код]Если n является практичным, то любое рациональное число вида m/n с m < n может быть представлен в виде суммы , где все di являются различными делителями числа n. Каждый член в этой сумме приводится к доле единицы, так что такая сумма даёт представление числа m/n в виде египетской дроби. Например,
Фибоначчи в своей книге 1202 года Liber Abaci[2] приводит некоторые методы поиска представления рационального числа в виде египетской дроби. Из них первый метод заключается в проверке, не является ли число уже долей единицы, а второй метод заключается в представлении числителя в виде суммы делителей знаменателя, как описано выше. Это метод гарантирует успех только в случае, когда знаменатель является практичным числом. Фибоначчи привёл таблицы таких представлений для дробей, имеющих в качестве знаменателей практичные числа 6, 8, 12, 20, 24, 60 и 100.
Воуз[8] показал, что любое число x/y имеет представление в виде египетской дроби с членами. Доказательство использует поиск последовательности практичных чисел ni со свойством, что любое число, меньшее ni, может быть записано в виде суммы различных делителей числа ni. Тогда i выбирается так, что и делится на y, давая частное q и остаток r. Из этого выбора следует, что . Разложив числители в правой части формулы на сумму делителей числа ni получим представление числа в виде египетской дроби. Тененбаум и Йокота[9] использовали подобную технику, использующую другую последовательность практичных чисел, чтобы показать, что любое число x/y имеет представление в виде египетской дроби, в которой наибольший знаменатель равен .
Согласно сентябрьской 2015 года гипотезе Чжи-Вэй Сунь[10] любое положительное рациональное число имеет представление в виде египетской дроби, в котором любой знаменатель является практичным числом. Существует доказательство гипотезы в блоге Дэвида Эппштейна[11].
Аналогия простым числам
[править | править код]Одна из причин интереса к практичным числам заключается в том, что многие из их свойств подобны свойствам простых чисел. Более того, теоремы, аналогичные гипотезе Гольдбаха и гипотезе о числах-близнецах, известны для практичных чисел — любое положительное чётное число является суммой двух практичных чисел и существует бесконечно много троек практичных чисел [12]. Джузеппе Мелфи показал также, что существует бесконечно много практичных чисел Фибоначчи (последовательность A124105 в OEIS). Аналогичный вопрос о существовании бесконечного числа простых чисел Фибоначчи[англ.] остаётся открытым. Хаусман и Шапиро[13] показали, что существует всегда практичное число в интервале для любого положительного вещественного x, что является аналогом гипотезы Лежандра для простых чисел.
Пусть p(x) подсчитывает количество практичных чисел, не превосходящих x. Маргенштерн[7] высказал гипотезу, что p(x) асимптотически равна cx/log x для некоторой константы c, что напоминает формулу в теореме о распределении простых чисел и усиливает более раннее утверждение Эрдёша и Локстона[14], что практичные числа имеют плотность ноль в множестве целых чисел. Сайес[15] доказал, что для подходящих констант c1 и c2
Наконец, Вайнгартнер[16] доказал гипотезу Маргенштерна, показав, что
для и некоторой константы .
Примечания
[править | править код]- ↑ Маргентшерн(Margenstern 1991), цитируя Робинсона(Robinson 1979) и Хейворта(Heyworth 1980), использует название «панаритмичные числа».
- ↑ 1 2 Sigler, 2002.
- ↑ 1 2 3 4 5 6 7 Srinivasan, 1948.
- ↑ 1 2 3 Stewart, 1954.
- ↑ 1 2 3 Sierpiński, 1955.
- ↑ Hausman, Shapiro (1984) ; Margenstern (1991) ; Melfi (1996) ; Saias (1997) .
- ↑ 1 2 Margenstern, 1991.
- ↑ Vose, 1985.
- ↑ Tenenbaum, Yokota, 1990.
- ↑ A Conjecture on Unit Fractions Involving Primes . Дата обращения: 30 мая 2018. Архивировано из оригинала 19 октября 2018 года.
- ↑ 0xDE: Egyptian fractions with practical denominators . Дата обращения: 30 мая 2018. Архивировано 2 января 2019 года.
- ↑ Melfi, 1996.
- ↑ Hausman, Shapiro, 1984.
- ↑ Erdős, Loxton, 1979.
- ↑ Saias, 1997.
- ↑ Weingartner, 2015.
Литература
[править | править код]- Paul Erdős, Loxton J. H. Some problems in partitio numerorum // Journal of the Australian Mathematical Society (Series A). — 1979. — Т. 27, вып. 03. — С. 319–331. — doi:10.1017/S144678870001243X.
- Heyworth M. R. More on panarithmic numbers // New Zealand Math. Mag.. — 1980. — Т. 17, вып. 1. — С. 24–28.. Как процитировано у Маргенштерна (Margenstern 1991).
- Miriam Hausman, Harold N. Shapiro. On practical numbers // Communications on Pure and Applied Mathematics. — 1984. — Т. 37, вып. 5. — С. 705–713. — doi:10.1002/cpa.3160370507.
- Maurice Margenstern. Résultats et conjectures sur les nombres pratiques // Comptes Rendus de l'Académie des Sciences, Série I. — 1984. — Т. 299, вып. 18. — С. 895–898. Как процитировано у Маргенштерна (Margenstern 1991).
- Maurice Margenstern. Les nombres pratiques: théorie, observations et conjectures // Journal of Number Theory. — 1991. — Т. 37, вып. 1. — С. 1–36. — doi:10.1016/S0022-314X(05)80022-8.
- Giuseppe Melfi. On two conjectures about practical numbers // Journal of Number Theory. — 1996. — Т. 56, вып. 1. — С. 205–210. — doi:10.1006/jnth.1996.0012.
- Dragoslav S. Mitrinović, József Sándor, Borislav Crstici. III.50 Practical numbers // Handbook of number theory, Volume 1. — Kluwer Academic Publishers, 1996. — Т. 351. — С. 118–119. — (Mathematics and its Applications). — ISBN 978-0-7923-3823-9.
- Robinson D. F. Egyptian fractions via Greek number theory // New Zealand Math. Mag.. — 1979. — Т. 16, вып. 2. — С. 47–52.. Как процитировано у Маргенштерна (Margenstern 1991) и Митриновича Mitrinović, Sándor & Crstici (1996) .
- Entiers à diviseurs denses, I // Journal of Number Theory. — 1997. — Т. 62, вып. 1. — С. 163–191. — doi:10.1006/jnth.1997.2057.
- Fibonacci's Liber Abaci / Laurence E. Sigler (перевод). — Springer-Verlag, 2002. — С. 119–121. — ISBN 0-387-95419-8.
- Wacław Sierpiński. Sur une propriété des nombres naturels // Annali di Matematica Pura ed Applicata. — 1955. — Т. 39, вып. 1. — С. 69–74. — doi:10.1007/BF02410762.
- Srinivasan A. K. Practical numbers // Current Science. — 1948. — Т. 17. — С. 179–180.
- Stewart B. M. Sums of distinct divisors // American Journal of Mathematics. — The Johns Hopkins University Press, 1954. — Т. 76, вып. 4. — С. 779–785. — doi:10.2307/2372651. — .
- Tenenbaum G., Yokota H. Length and denominators of Egyptian fractions // Journal of Number Theory. — 1990. — Т. 35, вып. 2. — С. 150–156. — doi:10.1016/0022-314X(90)90109-5.
- Vose M. Egyptian fractions // Bulletin of the London Mathematical Society. — 1985. — Т. 17, вып. 1. — С. 21. — doi:10.1112/blms/17.1.21.
- Weingartner A. Practical numbers and the distribution of divisors // The Quarterly Journal of Mathematics. — 2015. — Т. 66, вып. 2. — С. 743–758. — doi:10.1093/qmath/hav006. — arXiv:1405.2585.
Ссылки
[править | править код]- Tables of practical numbers Архивная копия от 26 декабря 2017 на Wayback Machine compiled by Giuseppe Melfi.
- Practical Number (англ.) на сайте PlanetMath.
- Weisstein, Eric W. Practical Number (англ.) на сайте Wolfram MathWorld.
Для улучшения этой статьи желательно:
|