Русская Википедия:Практичное число

Материал из Онлайн справочника
Версия от 01:34, 7 сентября 2023; EducationBot (обсуждение | вклад) (Новая страница: «{{Русская Википедия/Панель перехода}} thumb|Практичное число 12 '''Практичное число''' или '''панаритмичное число'''<ref>Маргентшерн{{harv|Margenstern|1991}}, цитируя Робинсона{{harv|Robinson|1979}} и Хейворта{{harv|Heyworth|1980}}, использует название «панаритми...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

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

Практичное число или панаритмичное число[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.

Последовательность практичных чисел (Шаблон: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) в связи с задачей представления рациональных чисел в виде египетских дробей. Фибоначчи не определял формально практичные числа, но он дал таблицу представления египетских дробей для дробей с практичными знаменателямиШаблон:Sfn.

Название «практичное число» дал ШринивасанШаблон:Sfn. Он заметил, что «разбиение денег, веса и других мер, использующие числа, такие как 4, 12, 16, 20 и 28, которые обычно так неудобны, что заслуживают замены на степени 10.» Он переоткрыл ряд теоретических свойств таких чисел и первым попытался классифицировать эти числа, а СтюартШаблон:Sfn и СерпинскийШаблон:Sfn завершили классификацию. Определение практичных чисел делает возможным определить, является ли число практичным путём просмотра разложения числа на простые множители. Любое чётное совершенное число и любая степень двойки является практичным числом.

Можно показать, что практичные числа аналогичны простым числам во многих отношениях[2].

Описание практичных чисел

Исходное описание ШринивасанаШаблон:Sfn утверждает, что практичное число (кроме степени двойки) не может быть недостаточным числом. Если для практичного числа <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 и СерпинскийШаблон:Sfn, которые показали, что определение, является ли число практичным, определяется его разложением на простые делители. Положительное целое число, большее единицы с разложением <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 от 2 до Шаблон:Mvar, для каждого следующего простого числа <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Шаблон:Sfn:

  • Пусть <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 заметил, что отличные от 1 и 2 практичные числа делятся на 4 и/или 6.
  • Произведение двух практичных чисел является также практичным числомШаблон:Sfnp. Более сильное утверждение, наименьшее общее кратное любых двух практичных чисел, является также практичным числом. Эквивалентно, множество всех практичных чисел замкнуто по умножению.
  • Из описания чисел Стюартом и Серпинским можно видеть, что в случае, когда n является практичным числом, а d является одним из его делителей, число n*d должно быть также практичным числом.
  • В множестве всех практичных чисел существует множество простых практичных чисел. Простое практичное число — это либо практичное и свободное от квадратов число, либо практичное и при делении на любой его простой делитель, показатель которого в разложении больше 1, перестаёт быть практичным. Последовательность простых практичных чисел (Шаблон: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.
  • Любая степень двойки является практичным числом Шаблон:Sfn. Степень двойки тривиально удовлетворяет описанию практичных чисел в терминах разложения целых чисел — все простые числа в разложении числа, p1, равны двум, что и требуется.
  • Любое чётное совершенное число является также практичным числомШаблон:Sfn. Это следует из результата Эйлера, что чётное совершенное число должно иметь вид <math>2^{n - 1}(2^n - 1)</math>. Нечётная часть этого разложения равна сумме делителей чётной части, так что любое нечётный простой делитель такого числа должен быть не больше суммы делителей чётной части числа. Таким образом, это число должно удовлетворять описанию практичных чисел.
  • Любой праймориал (произведение первых i простых для некоторого числа i) является практичным числомШаблон:Sfn. Для первых двух праймориалов, двойки и шестёрки это ясно. Каждый последующий праймориал образуется умножением простого числа pi на меньший праймориал, который делится как на двойку, так и на предыдущее простое число <math>p_{i - 1}</math>. Согласно постулату Бертрана <math>p_i < 2p_{i - 1}</math>, так что каждый предшествующий простой делитель праймориала меньше, чем один из делителей предыдущего праймориала. По индукции, из этого следует, что любой праймориал удовлетворяет описанию практичных чисел. Поскольку праймориал по определению свободен от квадратов, он также является простым практичным числом.
  • Обобщая праймориалы, любое число, являющееся произведением ненулевых степеней первых k простых чисел, должно быть практичным. В это множество попадают сверхсоставные числа Рамануджана (числа с количеством делителей, большим любого меньшего положительного числа), а также факториалыШаблон:Sfn.

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

Если n является практичным, то любое рациональное число вида m/n с m < n может быть представлен в виде суммы <math>\sum{\tfrac{d_i}{n}}</math>, где все di являются различными делителями числа 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 приводит некоторые методы поиска представления рационального числа в виде египетской дроби. Из них первый метод заключается в проверке, не является ли число уже долей единицы, а второй метод заключается в представлении числителя в виде суммы делителей знаменателя, как описано выше. Это метод гарантирует успех только в случае, когда знаменатель является практичным числом. Фибоначчи привёл таблицы таких представлений для дробей, имеющих в качестве знаменателей практичные числа 6, 8, 12, 20, 24, 60 и 100.

ВоузШаблон:Sfn показал, что любое число x/y имеет представление в виде египетской дроби с <math>\scriptstyle O(\sqrt{\log y})</math> членами. Доказательство использует поиск последовательности практичных чисел ni со свойством, что любое число, меньшее ni, может быть записано в виде суммы <math>\scriptstyle O(\sqrt{\log n_{i-1}})</math> различных делителей числа ni. Тогда 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>. Разложив числители в правой части формулы на сумму делителей числа ni получим представление числа в виде египетской дроби. Тененбаум и ЙокотаШаблон:Sfn использовали подобную технику, использующую другую последовательность практичных чисел, чтобы показать, что любое число x/y имеет представление в виде египетской дроби, в которой наибольший знаменатель равен <math>\scriptstyle O(\frac{y\log^2 y}{\log\log y})</math>.

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

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

Одна из причин интереса к практичным числам заключается в том, что многие из их свойств подобны свойствам простых чисел. Более того, теоремы, аналогичные гипотезе Гольдбаха и гипотезе о числах-близнецах, известны для практичных чисел — любое положительное чётное число является суммой двух практичных чисел и существует бесконечно много троек практичных чисел <math>x - 2, x, x + 2</math>Шаблон:Sfn. Джузеппе Мелфи показал также, что существует бесконечно много практичных чисел Фибоначчи (Шаблон:OEIS). Аналогичный вопрос о существовании бесконечного числа Шаблон:Не переведено 5 остаётся открытым. Хаусман и ШапироШаблон:Sfn показали, что существует всегда практичное число в интервале <math>[x^2,(x + 1)^2]</math> для любого положительного вещественного x, что является аналогом гипотезы Лежандра для простых чисел.

Пусть p(x) подсчитывает количество практичных чисел, не превосходящих x. МаргенштернШаблон:Sfn высказал гипотезу, что p(x) асимптотически равна cx/log x для некоторой константы c, что напоминает формулу в теореме о распределении простых чисел и усиливает более раннее утверждение Эрдёша и ЛокстонаШаблон:Sfn, что практичные числа имеют плотность ноль в множестве целых чисел. СайесШаблон:Sfn доказал, что для подходящих констант c1 и c2

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

Наконец, ВайнгартнерШаблон:Sfn доказал гипотезу Маргенштерна, показав, что

<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>.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Ссылки


Шаблон:Классы натуральных чисел Шаблон:Числа по характеристикам делимости Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ МаргентшернШаблон:Harv, цитируя РобинсонаШаблон:Harv и ХейвортаШаблон:Harv, использует название «панаритмичные числа».
  2. ↑ Шаблон:Harvtxt; Шаблон:Harvtxt; Шаблон:Harvtxt; Шаблон:Harvtxt.
  3. ↑ Шаблон:Cite web
  4. ↑ Шаблон:Cite web
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Практичное_число&oldid=10637702