Главная
Новости
Статьи
Ремонт
Каркасный дом
Несущие конструкции
Металлические конструкции
Прочность дорог
Дорожные материалы
Стальные конструкции
Грунтовые основания
Опорные сооружения




19.09.2021


19.09.2021


18.09.2021


16.09.2021


16.09.2021


15.09.2021


14.09.2021





Яндекс.Метрика

Функция делителей

04.08.2021

Функция делителей — арифметическая функция, связанная с делителями целого числа. Функция известна также под именем функция дивизоров. Применяется, в частности, при исследовании связи дзета-функции Римана и рядов Эйзенштейна для модулярных форм. Изучалась Рамануджаном, который вывел ряд важных равенств в модульной арифметике и арифметических тождествах.

С этой функцией тесно связана суммирующая функция делителей, которая, как следует из названия, является суммой функции делителей.

Определение

Функция «сумма положительных делителей» σx(n) для вещественного или комплексного числа x определяется как сумма x-х степеней положительных делителей числа n. Функцию можно выразить формулой

σ x ( n ) = ∑ d | n d x , {displaystyle sigma _{x}(n)=sum _{d|n}d^{x},!,}

где d | n {displaystyle {d|n}} означает «d делит n». Обозначения d(n), ν(n) и τ(n) (от немецкого Teiler = делитель) используются также для обозначения σ0(n), или функции числа делителей . Если x равен 1, функция называется сигма-функцией или суммой делителей, и индекс часто опускается, так что σ(n) эквивалентна σ1(n).

Аликвотная сумма s(n) для n — это сумма собственных делителей (то есть всех делителей, за исключением самого n, и равна σ1(n) − n. Аликвотная последовательность для n образуется последовательным вычислением аликвотной суммы, то есть каждое последующее значение в последовательности равно аликвотной сумме предыдущего значения.

Примеры

Например, σ0(12) — количество делителей числа 12:

σ 0 ( 12 ) = 1 0 + 2 0 + 3 0 + 4 0 + 6 0 + 12 0 = 1 + 1 + 1 + 1 + 1 + 1 = 6 , {displaystyle {egin{aligned}sigma _{0}(12)&=1^{0}+2^{0}+3^{0}+4^{0}+6^{0}+12^{0}&=1+1+1+1+1+1=6,end{aligned}}}

в то время как σ1(12) — сумма всех делителей:

σ 1 ( 12 ) = 1 1 + 2 1 + 3 1 + 4 1 + 6 1 + 12 1 = 1 + 2 + 3 + 4 + 6 + 12 = 28 , {displaystyle {egin{aligned}sigma _{1}(12)&=1^{1}+2^{1}+3^{1}+4^{1}+6^{1}+12^{1}&=1+2+3+4+6+12=28,end{aligned}}}

и аликвотная сумма s(12) собственных делителей равна:

s ( 12 ) = 1 1 + 2 1 + 3 1 + 4 1 + 6 1 = 1 + 2 + 3 + 4 + 6 = 16. {displaystyle {egin{aligned}s(12)&=1^{1}+2^{1}+3^{1}+4^{1}+6^{1}&=1+2+3+4+6=16.end{aligned}}}

Таблица значений

Случаи x = 2 {displaystyle x=2} , x = 3 {displaystyle x=3} и так далее входят в последовательности A001157, A001158, A001159, A001160, A013954, A013955 …

Свойства

Для целых, не являющихся квадратами, каждый делитель d числа n имеет парный делитель n/d, а значит, σ 0 ( n ) {displaystyle sigma _{0}(n)} всегда чётно для таких чисел. Для квадратов один делитель, а именно n {displaystyle {sqrt {n}}} , не имеет пары, так что для них σ 0 ( n ) {displaystyle sigma _{0}(n)} всегда нечётно.

Для простого числа p,

σ 0 ( p ) = 2 σ 0 ( p n ) = n + 1 σ 1 ( p ) = p + 1 {displaystyle {egin{aligned}sigma _{0}(p)&=2sigma _{0}(p^{n})&=n+1sigma _{1}(p)&=p+1end{aligned}}}

поскольку, по определению, простое число делится только на единицу и самого себя. Если pn# означает праймориал, то

σ 0 ( p n # ) = 2 n {displaystyle sigma _{0}(p_{n}#)=2^{n}}


Ясно, что 1 < σ 0 ( n ) < n {displaystyle 1<sigma _{0}(n)<n} и σ ( n ) > n {displaystyle sigma (n)>n} для всех n > 2 {displaystyle n>2} .

Функция делителей мультипликативна, но не вполне мультипликативна.

Если мы запишем

n = ∏ i = 1 r p i a i {displaystyle n=prod _{i=1}^{r}p_{i}^{a_{i}}} ,

где r = ω(n) — число простых делителей числа n, pii-й простой делитель, а ai — максимальная степень pi, на которую делится n, то

σ x ( n ) = ∏ i = 1 r p i ( a i + 1 ) x − 1 p i x − 1 {displaystyle sigma _{x}(n)=prod _{i=1}^{r}{frac {p_{i}^{(a_{i}+1)x}-1}{p_{i}^{x}-1}}} ,

что эквивалентно:

σ x ( n ) = ∏ i = 1 r ∑ j = 0 a i p i j x = ∏ i = 1 r ( 1 + p i x + p i 2 x + ⋯ + p i a i x ) . {displaystyle sigma _{x}(n)=prod _{i=1}^{r}sum _{j=0}^{a_{i}}p_{i}^{jx}=prod _{i=1}^{r}(1+p_{i}^{x}+p_{i}^{2x}+cdots +p_{i}^{a_{i}x}).}

Если положить x = 0, получим, что d(n) равно:

σ 0 ( n ) = ∏ i = 1 r ( a i + 1 ) . {displaystyle sigma _{0}(n)=prod _{i=1}^{r}(a_{i}+1).}

Например, число n = 24 имеет два простых делителя — p1 = 2 и p2 = 3. Поскольку 24 — это произведение 23×31, то a1 = 3 и a2 = 1.

Теперь мы можем вычислить σ 0 ( 24 ) {displaystyle sigma _{0}(24)} :

σ 0 ( 24 ) = ∏ i = 1 2 ( a i + 1 ) = ( 3 + 1 ) ( 1 + 1 ) = 4 × 2 = 8. {displaystyle {egin{aligned}sigma _{0}(24)&=prod _{i=1}^{2}(a_{i}+1)&=(3+1)(1+1)=4 imes 2=8.end{aligned}}}

Восемь делителей числа 24 — это 1, 2, 4, 8, 3, 6, 12, и 24.

Заметим также, что s(n) = σ(n) − n. Здесь s(n) обозначает сумму собственных делителей числа n, то есть делителей, за исключением самого числа n. Эта функция используется для определения совершенности числа — для них s(n) = n. Если s(n) > n, n называется избыточным, а если s(n) < n, n называется недостаточным.

Если n — степень двойки, то есть n = 2 k {displaystyle n=2^{k}} , то σ ( n ) = 2 × 2 k − 1 = 2 n − 1 , {displaystyle sigma (n)=2 imes 2^{k}-1=2n-1,} и s(n) = n — 1, что делает n почти совершенным.

Как пример, для двух простых p и q (где p < q), пусть

n = p q . {displaystyle n=pq.}

Тогда

σ ( n ) = ( p + 1 ) ( q + 1 ) = n + 1 + ( p + q ) , {displaystyle sigma (n)=(p+1)(q+1)=n+1+(p+q),} ϕ ( n ) = ( p − 1 ) ( q − 1 ) = n + 1 − ( p + q ) , {displaystyle phi (n)=(p-1)(q-1)=n+1-(p+q),}

и

n + 1 = ( σ ( n ) + ϕ ( n ) ) / 2 , {displaystyle n+1=(sigma (n)+phi (n))/2,} p + q = ( σ ( n ) − ϕ ( n ) ) / 2 , {displaystyle p+q=(sigma (n)-phi (n))/2,}

где φ(n) — функция Эйлера.

Тогда корни p и q уравнения:

( x − p ) ( x − q ) = x 2 − ( p + q ) x + n = x 2 − [ ( σ ( n ) − ϕ ( n ) ) / 2 ] x + [ ( σ ( n ) + ϕ ( n ) ) / 2 − 1 ] = 0 {displaystyle (x-p)(x-q)=x^{2}-(p+q)x+n=x^{2}-[(sigma (n)-phi (n))/2]x+[(sigma (n)+phi (n))/2-1]=0}

можно выразить через σ(n) и φ(n) :

p = ( σ ( n ) − ϕ ( n ) ) / 4 − [ ( σ ( n ) − ϕ ( n ) ) / 4 ] 2 − [ ( σ ( n ) + ϕ ( n ) ) / 2 − 1 ] , {displaystyle p=(sigma (n)-phi (n))/4-{sqrt {[(sigma (n)-phi (n))/4]^{2}-[(sigma (n)+phi (n))/2-1]}},} q = ( σ ( n ) − ϕ ( n ) ) / 4 + [ ( σ ( n ) − ϕ ( n ) ) / 4 ] 2 − [ ( σ ( n ) + ϕ ( n ) ) / 2 − 1 ] . {displaystyle q=(sigma (n)-phi (n))/4+{sqrt {[(sigma (n)-phi (n))/4]^{2}-[(sigma (n)+phi (n))/2-1]}}.}

Зная n и либо σ(n), либо φ(n) (или зная p+q и либо σ(n), либо φ(n)) мы легко можем найти p и q.

В 1984 году Хиз-Браун (Roger Heath-Brown) доказал, что

σ 0 ( n ) = σ 0 ( n + 1 ) {displaystyle sigma _{0}(n)=sigma _{0}(n+1)}

встречается бесконечно много раз.

Связь с рядами

Два ряда Дирихле, использующие функцию делителей:

∑ n = 1 ∞ σ a ( n ) n s = ζ ( s ) ζ ( s − a ) , {displaystyle sum _{n=1}^{infty }{frac {sigma _{a}(n)}{n^{s}}}=zeta (s)zeta (s-a),}

и при обозначении d(n) = σ0(n) получим

∑ n = 1 ∞ d ( n ) n s = ζ 2 ( s ) , {displaystyle sum _{n=1}^{infty }{frac {d(n)}{n^{s}}}=zeta ^{2}(s),}

и второй ряд,

∑ n = 1 ∞ σ a ( n ) σ b ( n ) n s = ζ ( s ) ζ ( s − a ) ζ ( s − b ) ζ ( s − a − b ) ζ ( 2 s − a − b ) . {displaystyle sum _{n=1}^{infty }{frac {sigma _{a}(n)sigma _{b}(n)}{n^{s}}}={frac {zeta (s)zeta (s-a)zeta (s-b)zeta (s-a-b)}{zeta (2s-a-b)}}.}

Ряд Ламбера, использующий функцию делителей:

∑ n = 1 ∞ q n σ a ( n ) = ∑ n = 1 ∞ n a q n 1 − q n {displaystyle sum _{n=1}^{infty }q^{n}sigma _{a}(n)=sum _{n=1}^{infty }{frac {n^{a}q^{n}}{1-q^{n}}}}

для любого комплексного |q| ≤ 1 и a.

Эта сумма появляется также в рядах Фурье для рядов Эйзенштейна и в инвариантах эллиптических функций Вейерштрасса.

Асимптотическая скорость роста

В терминах о-малое функция делителей удовлетворяет неравенству (см. стр. 296 книги Апостола)

для всех ϵ > 0 , d ( n ) = o ( n ϵ ) . {displaystyle epsilon >0,quad d(n)=o(n^{epsilon }).}

Северин Вигерт дал более точную оценку

lim sup n → ∞ log ⁡ d ( n ) log ⁡ n / log ⁡ log ⁡ n = log ⁡ 2. {displaystyle limsup _{n o infty }{frac {log d(n)}{log n/log log n}}=log 2.}

С другой стороны, ввиду бесконечности количества простых чисел,

lim inf n → ∞ d ( n ) = 2. {displaystyle liminf _{n o infty }d(n)=2.}

В терминах О-большое, Дирихле показал, что средний порядок функции делителей удовлетворяет следующему неравенству (см. теорему 3.3 книги Апостола)

для всех x ≥ 1 , ∑ n ≤ x d ( n ) = x log ⁡ x + ( 2 γ − 1 ) x + O ( x ) , {displaystyle xgeq 1,sum _{nleq x}d(n)=xlog x+(2gamma -1)x+O({sqrt {x}}),}

где γ {displaystyle gamma } — постоянная Эйлера — Маскерони.

Задача улучшить границу O ( x ) {displaystyle O({sqrt {x}})} в этой формуле — это проблема Дирихле о делителях

Поведение сигма-функции неравномерно. Асимптотическую скорость роста сигма-функции можно выразить формулой:

lim sup n → ∞ σ ( n ) n log ⁡ log ⁡ n = e γ , {displaystyle limsup _{n ightarrow infty }{frac {sigma (n)}{n,log log n}}=e^{gamma },}

где lim sup — верхний предел. Этот результат является теоремой Грёнвалла (Grönwall), опубликованной в 1913 году. Его доказательство использует третью теорему Мертенса, которая утверждает, что

lim n → ∞ 1 log ⁡ n ∏ p ≤ n p p − 1 = e γ , {displaystyle lim _{n o infty }{frac {1}{log n}}prod _{pleq n}{frac {p}{p-1}}=e^{gamma },}

где p — простое.

В 1915 году Рамануджан доказал, что при выполнении гипотезы Римана неравенство

  σ ( n ) < e γ n log ⁡ log ⁡ n {displaystyle sigma (n)<e^{gamma }nlog log n} (неравенство Робина)

выполняется для всех достаточно больших n. В 1984 году Гай Робин доказал, что неравенство верно для всех n ≥ 5041 в том и только в том случае, если гипотеза Римана верна. Это теорема Робина и неравенство стало широко известно после доказательства теоремы. Наибольшее известное число, нарушающее неравенство — это n=5040. Если гипотеза Римана верна, то нет чисел, больших этого и нарушающих неравенство. Робин показал, что в случае ошибочности гипотезы существует бесконечно много чисел n, нарушающих неравенство, и известно, что наименьшее из таких чисел n ≥ 5041 должно быть сверхизбыточным числом. Было показано, что неравенство выполняется для больших нечётных свободных от квадратов чисел, и что гипотеза Римана эквивалентна выполнению неравенства для всех чисел n, делящихся на пятую степень простого числа

Джефри Лагариас (Jeffrey Lagarias) в 2002 году доказал, что гипотеза Римана эквивалентна утверждению

σ ( n ) ≤ H n + ln ⁡ ( H n ) e H n {displaystyle sigma (n)leq H_{n}+ln(H_{n})e^{H_{n}}}

для любого натурального n, где H n {displaystyle H_{n}} — n-е гармоническое число.

Робин доказал, что неравенство

  σ ( n ) < e γ n log ⁡ log ⁡ n + 0.6483   n log ⁡ log ⁡ n {displaystyle sigma (n)<e^{gamma }nlog log n+{frac {0.6483 n}{log log n}}}

выполняется для n ≥ 3 без каких-либо дополнительных условий.


Имя:*
E-Mail:
Комментарий: