Просмотр кода страницы Практичное число

[[Файл:Practical number Cuisenaire rods 12.png|thumb|Практичное число 12]]

'''Практичное число''' или '''панаритмичное число'''<ref>Маргентшерн{{harv|Margenstern|1991}}, цитируя Робинсона{{harv|Robinson|1979}} и Хейворта{{harv|Heyworth|1980}}, использует название «панаритмичные числа».</ref> — это положительное целое число ''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.

Последовательность практичных чисел ({{OEIS|A005153}}) начинается с 
: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) в связи с задачей представления рациональных чисел в виде [[Египетские дроби|египетских дробей]]. Фибоначчи не определял формально практичные числа, но он дал таблицу представления египетских дробей для дробей с практичными знаменателями{{sfn|Sigler|2002}}.

Название «практичное число» дал Шринивасан{{sfn|Srinivasan|1948}}. Он заметил, что «разбиение денег, веса и других мер, использующие числа, такие как 4, 12, 16, 20 и 28, которые обычно так неудобны, что заслуживают замены на степени 10.» Он переоткрыл ряд теоретических свойств таких чисел и первым попытался классифицировать эти числа, а Стюарт{{sfn|Stewart|1954}} и [[Серпинский, Вацлав|Серпинский]]{{sfn|Sierpiński|1955}} завершили классификацию. Определение практичных чисел делает возможным определить, является ли число практичным путём просмотра разложения числа на простые множители. Любое чётное [[совершенное число]] и любая {{не переведено 5|степень двойки|||power of two}} является практичным числом.

Можно показать, что практичные числа аналогичны [[Простое число|простым числам]] во многих отношениях<ref>{{harvtxt|Hausman, Shapiro|1984}}; {{harvtxt|Margenstern|1991}}; {{harvtxt|Melfi|1996}}; {{harvtxt|Saias|1997}}.</ref>.

==Описание практичных чисел==
Исходное описание Шринивасана{{sfn|Srinivasan|1948}} утверждает, что практичное число не может быть [[Недостаточные числа|недостаточным числом]], это число, сумма всех делителей которого (включая 1 и само число) меньше удвоенного числа, если не считать недостаток, равный единице. Если для практичного числа <math>n</math> выписать упорядоченное множество делителей <math>{d_1, d_2,..., d_j}</math>, где <math>d_1=1</math> и <math>d_j=n</math>, то утверждение Шринивасана можно выразить неравенством
:<math>2n\leqslant 1+\sum_{i=1}^j d_i</math>.

Другими словами, упорядоченная последовательность всех делителей <math>{d_1<d_2<...<d_j}</math>  практичного числа должна быть [[Полная последовательность|полной подпоследовательностью]].

Это определение расширили и завершили Стюарт{{sfn|Stewart|1954}} и Серпинский{{sfn|Sierpiński|1955}}, которые показали, что определение, является ли число практичным, определяется его [[Факторизация целых чисел|разложением на простые делители]].
Положительное целое число, большее единицы с разложением <math>n=p_1^{\alpha_1}...p_k^{\alpha_k}</math> (с сортировкой простых делителей по возрастанию <math>p_1<p_2<\dots<p_k</math>), является практичным тогда и только тогда, когда каждый его простой делитель <math>p_i</math> достаточно мал, чтобы <math>p_i-1</math> имело представление в виде суммы меньших делителей. Чтобы это было верно, первое простое число <math>p_1</math> должно быть равно 2, а для любого {{mvar|i}} от 2 до {{mvar|k}}, для каждого следующего простого числа <math>p_i</math> должно выполняться неравенство
:<math>p_i\leqslant 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},</math>
где <math>\sigma(x)</math> означает [[Функция делителей|сумму делителей]] числа ''x''. Например, <math>2 \times 3^2 \times 29 \times 823 = 429606</math> является практичным, поскольку неравенство выполняется для каждого простого делителя: <math>3 \leqslant \sigma(2) + 1 = 4, 29 \leqslant \sigma(2 \times 3^2) + 1 = 40</math> и <math>823 \leqslant \sigma(2 \times 3^2 \times 29) + 1 = 1171</math>.

Условие, приведённое выше, является необходимым и достаточным. В одном направлении, это условие является необходимым, чтобы можно было представить <math>p_i-1</math> в виде суммы делителей числа ''n'', поскольку в случае нарушения неравенства сложение всех меньших делителей дало бы сумму, слишком маленькую, чтобы получить <math>p_i-1</math>. В другом направлении, условие является достаточным, что можно получить по индукции. 
Более строго, если разложение числа ''n'' удовлетворяет вышеприведённому условию, то любое число <math>m \leqslant \sigma(n)</math> может быть представлено в виде суммы делителей числа ''n'' после следующих шагов{{sfn|Stewart|1954}}{{sfn|Sierpiński|1955}}:
* Пусть <math>q = \min\{\lfloor m/p_k^{\alpha_k}\rfloor, \sigma(n/p_k^{\alpha_k})\}</math>, и пусть <math>r = m - qp_k^{\sigma_k}</math>.
* Учитывая, что можно показать по индукции, что <math>q\leqslant\sigma(n/p_k^{\alpha_k})</math> и <math>n/p_k^{\alpha_k}</math> являются практичными, мы можем найти представление ''q'' в виде суммы делителей <math>n/p_k^{\alpha_k}</math>.
* Учитывая, что можно показать по индукции, что <math>r\leqslant \sigma(n) - p_k^{\alpha_k}\sigma(n/p_k^{\alpha_k}) = \sigma(n/p_k)</math> и <math>n/p_k</math> являются практичными, мы можем найти представление ''r'' в виде суммы делителей <math>n/p_k</math>.
* Представление в виде делителей ''r'', вместе с коэффициентом <math>p_k^{\alpha_k}</math> для каждого делителя представления в виде делителей ''q'', вместе образуют представление ''m'' в виде суммы делителей ''n''.

==Свойства==
*Единственное нечётное практичное число — 1, поскольку если ''n'' > 2 является нечётным числом, то 2 нельзя представить в виде суммы различных делителей  числа ''n''. Шринивасан{{sfn|Srinivasan|1948}} заметил, что отличные от 1 и 2 практичные числа делятся на 4 или 6 (или на оба).
*Произведение двух практичных чисел является также практичным числом{{sfnp|Margenstern|1991}}. Более сильное утверждение, [[наименьшее общее кратное]] любых двух практичных чисел, является также практичным числом. Эквивалентно, множество всех практичных чисел замкнуто по умножению.
*Из описания чисел Стюартом и Серпинским можно видеть, что в случае, когда ''n'' является практичным числом, а ''d'' является одним из его делителей, число ''n*d'' должно быть также практичным числом. 
*В множестве всех практичных чисел существует множество простых практичных чисел. Простое практичное число — это либо практичное и [[свободное от квадратов число]], либо практичное и при делении на любой его простой делитель, показатель которого в [[Факторизация целых чисел|разложении]] больше 1, перестаёт быть практичным. Последовательность простых практичных чисел ({{OEIS|A267124|}}) начинается с 
::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.
*Любая {{не переведено 5|степень двойки|||power of two}} является практичным числом {{sfn|Srinivasan|1948}}. Степень двойки тривиально удовлетворяет описанию практичных чисел в терминах разложения целых чисел — все простые числа в разложении числа, ''p''<sub>1</sub>, равны двум, что и требуется. 
*Любое чётное [[совершенное число]] является также практичным числом{{sfn|Srinivasan|1948}}. Это следует из результата [[Эйлер, Леонард|Эйлера]], что чётное совершенное число должно иметь вид <math>2^{n - 1}(2^n - 1)</math>. Нечётная часть этого разложения равна сумме делителей чётной части, так что любое нечётный простой делитель такого числа должен быть не больше суммы делителей чётной части числа. Таким образом, это число должно удовлетворять описанию практичных чисел.
*Любой [[праймориал]] (произведение первых ''i'' простых для некоторого числа ''i'') является практичным числом{{sfn|Srinivasan|1948}}. Для первых двух праймориалов, двойки и шестёрки это ясно. Каждый последующий праймориал образуется умножением простого числа ''p''<sub>''i''</sub> на меньший праймориал, который делится как на двойку, так и на предыдущее простое число <math>p_{i - 1}</math>. Согласно [[Постулат Бертрана|постулату Бертрана]] <math>p_i < 2p_{i - 1}</math>, так что каждый предшествующий простой делитель праймориала меньше, чем один из делителей предыдущего праймориала. По индукции, из этого следует, что любой праймориал удовлетворяет описанию практичных чисел. Поскольку праймориал по определению свободен от квадратов, он также является простым практичным числом.
*Обобщая праймориалы, любое число, являющееся произведением ненулевых степеней первых ''k'' простых чисел, должно быть практичным. В это множество попадают [[Сверхсоставное число|сверхсоставные числа]] [[Сриниваса Рамануджан Айенгор|Рамануджана]] (числа с количеством делителей, большим любого меньшего положительного числа), а также [[факториал]]ы{{sfn|Srinivasan|1948}}.

==Практические числа и египетские дроби==
Если ''n'' является практичным, то любое [[рациональное число]] вида ''m''/''n'' с ''m'' < ''n'' может быть представлен в виде суммы <math>\sum{\tfrac{d_i}{n}}</math>, где все ''d<sub>i</sub>'' являются различными делителями числа ''n''. Каждый член в этой сумме приводится к [[Доля единицы|доле единицы]], так что такая сумма даёт представление числа ''m''/''n'' в виде [[Египетские дроби|египетской дроби]]. Например,
:<math>\frac{13}{20}=\frac{10}{20}+\frac{2}{20}+\frac{1}{20}=\frac12+\frac1{10}+\frac1{20}.</math>

Фибоначчи в своей книге 1202 года ''[[Книга абака|Liber Abaci]]''{{sfn|Sigler|2002}} приводит некоторые методы поиска представления рационального числа в виде египетской дроби. Из них первый метод заключается в проверке, не является ли число уже долей единицы, а второй метод заключается в представлении числителя в виде суммы делителей знаменателя, как описано выше. Это метод гарантирует успех только в случае, когда знаменатель является практичным числом. Фибоначчи привёл таблицы таких представлений для дробей, имеющих в качестве знаменателей практичные числа 6, 8, 12, 20, 24, 60 и 100.

Воуз{{sfn|Vose|1985}} показал, что любое число ''x''/''y'' имеет представление в виде египетской дроби с <math>\scriptstyle O(\sqrt{\log y})</math> членами. Доказательство использует поиск последовательности практичных чисел ''n''<sub>''i''</sub> со свойством, что любое число, меньшее ''n''<sub>''i''</sub>, может быть записано в виде суммы <math>\scriptstyle O(\sqrt{\log n_{i-1}})</math> различных делителей числа ''n''<sub>''i''</sub>. Тогда ''i'' выбирается так, что <math>n_{i  - 1} < y \leqslant n_i</math> и  <math>xn_i</math> делится на ''y'', давая частное ''q'' и остаток ''r''. Из этого выбора следует, что <math>\scriptstyle\frac{x}{y}=\frac{q}{n_i}+\frac{r}{yn_i}</math>. Разложив числители в правой части формулы на сумму делителей числа ''n''<sub>''i''</sub> получим представление числа в виде египетской дроби. Тененбаум и Йокота{{sfn|Tenenbaum, Yokota|1990}} использовали подобную технику, использующую другую последовательность практичных чисел, чтобы показать, что любое число ''x''/''y'' имеет представление в виде египетской дроби, в которой наибольший знаменатель равен <math>\scriptstyle O(\frac{y\log^2 y}{\log\log y})</math>.

Согласно сентябрьской 2015 года гипотезе Чжи-Вэй Сунь<ref>[http://maths.nju.edu.cn/~zwsun/UnitFraction.pdf A Conjecture on Unit Fractions Involving Primes]</ref> любое положительное рациональное число имеет представление в виде египетской дроби, в котором любой знаменатель является практичным числом. Существует доказательство гипотезы в блоге Дэвида Эппштейна<ref>[https://11011110.github.io/blog/2016/11/20/egyptian-fractions-with.html 0xDE: Egyptian fractions with practical denominators]</ref>.

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

Одна из причин интереса к практичным числам заключается в том, что многие из их свойств подобны свойствам [[Простое число|простых чисел]]. 
Более того, теоремы, аналогичные [[Проблема Гольдбаха|гипотезе Гольдбаха]] и [[Числа-близнецы|гипотезе о числах-близнецах]], известны для практичных чисел — любое положительное чётное число является суммой двух практичных чисел и существует бесконечно много троек практичных чисел <math>x - 2, x, x + 2</math>{{sfn|Melfi|1996}}. Джузеппе Мелфи показал также, что существует бесконечно много практичных [[Числа Фибоначчи|чисел Фибоначчи]] ({{OEIS|id=A124105}}). Аналогичный вопрос о существовании бесконечного числа {{не переведено 5|Простое число Фибоначчи|простых чисел Фибоначчи||Fibonacci prime}} остаётся открытым. Хаусман и Шапиро{{sfn|Hausman, Shapiro|1984}} показали, что существует всегда практичное число в интервале <math>[x_2,(x + 1)^2]</math> для любого положительного вещественного ''x'', что является аналогом [[Гипотеза Лежандра|гипотезы Лежандра]] для простых чисел.

Пусть ''p''(''x'') подсчитывает количество практичных чисел, не превосходящих ''x''.
Маргенштерн{{sfn|Margenstern|1991}} высказал гипотезу, что ''p''(''x'') асимптотически равна ''cx''/log&nbsp;''x'' для некоторой константы ''c'', что напоминает формулу в [[Теорема о распределении простых чисел|теореме о распределении простых чисел]] и усиливает более раннее утверждение Эрдёша и Локстона{{sfn|Erdős, Loxton|1979}}, что практичные числа имеют плотность ноль в множестве целых чисел.
Сайес{{sfn|Saias|1997}} доказал, что для подходящих констант ''c''<sub>1</sub> и ''c''<sub>2</sub>

:<math>c_1\frac x{\log x}<p(x)<c_2\frac x{\log x},</math>

Наконец, Вайнгартнер{{sfn|Weingartner|2015}} доказал гипотезу Маргенштерна, показав, что

:<math>p(x) = \frac{c x}{\log x}\left(1 + O\!\left(\frac{\log \log x}{\log x}\right)\right),</math>

для <math>x \geqslant 3</math> и некоторой константы <math>c > 0</math>.

==Примечания==
{{примечания|2}}

==Литература==
{{refbegin|colwidth=30em}}
*{{статья
|автор=[[Эрдёш, Пал|Paul Erdős]], Loxton J. H.
|ref=Erdős, Loxton
|doi = 10.1017/S144678870001243X
|издание= Journal of the Australian Mathematical Society (Series A)
|страницы= 319–331
|выпуск= 03
|заглавие= Some problems in partitio numerorum
|том= 27
|год= 1979
}}
*{{статья
|ref=Heyworth
|автор = Heyworth M. R.
|выпуск= 1
|издание= New Zealand Math. Mag.
|страницы= 24–28
|заглавие= More on panarithmic numbers
|том= 17
|год= 1980}}. Как процитировано у Маргенштерна {{harv|Margenstern|1991}}.
*{{статья
|автор =Miriam Hausman, Harold N. Shapiro
|ref =Hausman, Shapiro
|заглавие= On practical numbers
|издание= [[Communications on Pure and Applied Mathematics]]
|том= 37
|год= 1984
|выпуск= 5
|страницы= 705–713
|mr = 0752596
|doi = 10.1002/cpa.3160370507
}}
*{{статья
|ref =Margenstern
|автор =Maurice Margenstern
|выпуск= 18
|издание= Comptes Rendus de l'Académie des Sciences, Série I
|страницы= 895–898
|заглавие= Résultats et conjectures sur les nombres pratiques
|том= 299
|год= 1984
}} Как процитировано у Маргенштерна {{harv|Margenstern|1991}}.
*{{статья
|ref =Margenstern
|автор =Maurice Margenstern
|заглавие= Les nombres pratiques: théorie, observations et conjectures
|издание= [[Journal of Number Theory]]
|том= 37
|год= 1991
|выпуск= 1
|страницы= 1–36
|mr = 1089787
|doi = 10.1016/S0022-314X(05)80022-8
}}
*{{статья
|автор=Giuseppe Melfi
|ref =Melfi|first
|заглавие= On two conjectures about practical numbers
|издание= Journal of Number Theory
|том= 56
|год= 1996
|выпуск= 1
|страницы= 205–210
|mr = 1370203
|doi = 10.1006/jnth.1996.0012
}}
*{{книга
|автор= Dragoslav S. Mitrinović, József Sándor, Borislav Crstici
|ref=Mitrinović, Sándor, Crstici
|часть = III.50 Practical numbers
|isbn = 978-0-7923-3823-9
|страницы= 118–119
|издательство= Kluwer Academic Publishers
|серия = Mathematics and its Applications
|заглавие= Handbook of number theory, Volume 1
|том= 351
|год= 1996
}}
*{{статья
|ref=Robinson
|автор= Robinson D. F.
|выпуск= 2
|издание= New Zealand Math. Mag.
|страницы= 47–52
|заглавие= Egyptian fractions via Greek number theory
|том= 16
|год= 1979
}}. Как процитировано у Маргенштерна {{harv|Margenstern|1991}} и Митриновича {{harvtxt|Mitrinović|Sándor|Crstici|1996}}.
*{{статья
|ref=Saias
|автор Eric Saias
|заглавие= Entiers à diviseurs denses, I
|издание= Journal of Number Theory
|том= 62
|выпуск= 1
|год= 1997
|страницы= 163–191
|mr = 1430008
|doi = 10.1006/jnth.1997.2057
}}
*{{книга
|заглавие= Fibonacci's Liber Abaci
|ответственный = Laurence E. Sigler (перевод)
|ref=Sigler
|издательство= Springer-Verlag
|год= 2002
|isbn = 0-387-95419-8
|страницы= 119–121
}}
*{{статья
|автор =[[Серпинский, Вацлав|Wacław Sierpiński]]
|ref=Sierpiński
|doi = 10.1007/BF02410762
|выпуск= 1
|издание= Annali di Matematica Pura ed Applicata
|страницы= 69–74
|заглавие= Sur une propriété des nombres naturels
|том= 39
|год= 1955
}}
*{{статья
|ref=Srinivasan
|автор =Srinivasan A. K.
|заглавие= Practical numbers
|издание= [[Current Science]]
|том= 17
|год= 1948
|страницы= 179–180
|mr = 0027799
|ссылка = http://www.currentscience.ac.in/Downloads/article_id_017_06_0179_0180_0.pdf
}}
*{{статья
|автор =Stewart B. M.
|ref=Stewart
|заглавие= Sums of distinct divisors
|издание= [[American Journal of Mathematics]]
|том= 76
|год= 1954
|страницы= 779–785
|mr = 0064800
|doi = 10.2307/2372651
|jstor = 2372651
|выпуск= 4
|издательство= The Johns Hopkins University Press
}}
*{{статья
|автор =Tenenbaum G., Yokota H.
|ref=Tenenbaum, Yokota
|doi = 10.1016/0022-314X(90)90109-5
|mr = 1057319
|издание= Journal of Number Theory
|страницы= 150–156
|выпуск= 2
|заглавие= Length and denominators of Egyptian fractions
|том= 35
|год= 1990
}}
*{{статья
|ref=Vose
|автор= Vose M.
|doi = 10.1112/blms/17.1.21
|mr = 0766441
|издание= [[London Mathematical Society|Bulletin of the London Mathematical Society]]
|страницы = 21
|заглавие= Egyptian fractions
|выпуск= 1
|том= 17
|год= 1985
}}
*{{статья
|автор= Weingartner A.
|ref=Weingartner
|выпуск= 2
|издание= The Quarterly Journal of Mathematics
|страницы= 743–758
|заглавие= Practical numbers and the distribution of divisors
|том= 66
|год= 2015
|doi = 10.1093/qmath/hav006| arxiv = 1405.2585
 }}
{{refend}}

== Ссылки ==
*[http://www.dm.unipi.it/gauss-pages/melfi/public_html/pratica.html Tables of practical numbers] compiled by Giuseppe Melfi.
*{{PlanetMath |urlname=PracticalNumber |title=Practical Number}}
*{{Mathworld |urlname=PracticalNumber |title=Practical Number}}


{{Классы натуральных чисел}}
{{Числа по характеристикам делимости}}
[[Категория:Египетские дроби]]
[[Категория:Целочисленные последовательности]]
{{rq|checktranslate|style}}