Центральный Дом Знаний - Арифметическая функция

Информационный центр "Центральный Дом Знаний"

Заказать учебную работу! Жми!



ЖМИ: ТУТ ТЫСЯЧИ КУРСОВЫХ РАБОТ ДЛЯ ТЕБЯ

      cendomzn@yandex.ru  

Наш опрос

Как Вы планируете отдохнуть летом?
Всего ответов: 903

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Форма входа

Логин:
Пароль:

Арифметическая функция

Арифметическая функция, функция, определенная на множестве натуральных чисел , и принимающая значения во множестве комплексных чисел .

Как следует из определения, арифметической функцией называется любая функция f \colon \mathbb{N} \to \mathbb{C}

Название арифметическая функция связано с тем, что в теории чисел известно много функций ~f(n) натурального аргумента ~n, которые выражают те или иные арифметические свойства ~n. Поэтому, неформально говоря, под арифметической функцией понимают функцию ~f(n), которая «выражает некоторое арифметическое свойство» натурального числа ~n(см. примеры арифметических функций ниже).

Многие арифметические функции, рассматриваемые в теории чисел, в действительности являются целозначными.

Операции и связанные понятия

  • Суммой арифметической функции f называют функцию F:[0,+\infty)\to \C, определённую как

F(x)=\sum_{n\le x} f(n).

Эта операция является «дискретным аналогом» неопределённого интеграла; при этом, хотя исходная функция и была определена только на \N, её сумму оказывается удобным считать определённой на всей положительной полуоси (при этом она, естественно, кусочно-постоянна).

  • Свёрткой Дирихле (англ.) двух арифметических функций f и g называется арифметическая функция h, определённая по правилу

h(n)=\sum_{d|n} f(d) g(n/d).

  • Арифметической функции f можно сопоставить её «производящую функцию» — ряд Дирихле

\Phi_f(s)=\sum_n f(n) n^{-s}.

При этом свёртке Дирихле двух арифметических функций соответствует произведение их производящих функций.

  • Поточечное умножение на логарифм,

f\mapsto f', \quad f'(n)=f(n) \cdot \ln n,

является дифференцированием алгебры арифметических функций: относительно свёртки оно удовлетворяет правилу Лейбница,

(f*g)' = f'*g + f*g'.

Переход к производящей функции превращает эту операцию в обычное дифференцирование.

Известные арифметические функции

Количество делителей

Арифметическая функция ~\tau \colon \mathbb{N} \to \mathbb{N} определяется как число положительных делителей натурального числа ~n:

~\tau(n) = \sum_{d|n} 1

Если ~m и ~n взаимно просты, то каждый делитель произведения ~mn может быть единственным образом представлен в виде произведения делителей ~m и ~n, и обратно, каждое такое произведение является делителем ~mn. Отсюда следует, что функция ~\tau мультипликативна:

~\tau(mn) = \tau(m) \tau(n)

Если ~n = \prod_{i=1}^{r} p_i^{s_i} — каноническое разложение натурального ~n, то в силу мультипликативности

~\tau(n) = \tau(p_1^{s_1}) \tau(p_2^{s_2}) \ldots \tau(p_r^{s_r})

Так как положительными делителями числа p_i^{s_i} являются ~s_i+1 чисел 1, p_i, \ldots, p_i^{s_i}, то

~\tau(n) = (s_1+1) (s_2+1) \ldots (s_r+1)

Обобщая функции ~\tau(n) и ~\sigma(n) для произвольного, вообще говоря комплексного, ~k можно определить ~\sigma_k(n) — сумму k-ых степеней положительных делителей натурального числа ~n:

~\sigma_k (n) = \sum_{d|n} d^k

Используя нотацию Айверсона можно записать

~\sigma_k(n) = \sum_{d} d^k[\,d|n\,]

Функция ~\sigma_k мультипликативна:

m \perp n \Rightarrow ~\sigma_k (mn) = \sigma_k (m) \sigma_k (n)

Если ~n = \prod_{i=1}^{r} p_i^{s_i} — каноническое разложение натурального ~n, то

~\sigma_k(n) = \prod_{i=1}^r \frac {p_i^{(s_i+1)k}-1} {p_i - 1}

Сумма делителей числа n растёт в среднем как линейная функция cn, где постоянная c найдена Эйлером и есть c=\zeta(2)=\pi^2/6.

 Функция Эйлера 

Функция Эйлера \varphi(n), или тотиента, определяется как количество положительных целых чисел, не превосходящих ~n, которые взаимно просты с ~n.

Пользуясь нотацией Айверсона можно записать:

\varphi(n) = \sum_{1 \leq k \leq n} [k \perp n]

Функция Эйлера мультипликативна:

m \perp n \Rightarrow ~\varphi (mn) = \varphi (m) \varphi (n)

В явном виде значение функции Эйлера выражается формулой:

\varphi (n) = n \left(1 - \frac{1}{p_1} \right) \left(1 - \frac{1}{p_2} \right) \dots \left(1 - \frac{1}{p_r} \right)

где p_1, p_2, \ldots, p_r — различные простые делители ~n.

 Функция Мёбиуса 

Функцию Мёбиуса ~\mu(n) можно определить как арифметическую функцию, которая удовлетворяет следующему соотношению:

\sum_{d | n} \mu(d) = \begin{cases}1,&n=1\\0,&n>1\end{cases}

То есть сумма значений функции Мёбиуса по всем делителям целого положительного числа ~n равна нулю, если ~n>1, и равна ~1, если ~n=1.

Можно показать, что этому уравнению удовлетворяет лишь одна функция, и ее можно явно задать следующей формулой:

\mu(n) = \begin{cases}(-1)^r, & n = p_1 p_2 \ldots p_r \\0, & p^2 | n \\1, & n=1\end{cases}

Здесь p_i — различные простые числа, p — простое число. Иначе говоря, функция Мёбиуса \mu(n) равна 0, если n не свободно от квадратов (то есть делится на квадрат простого числа), и равна ~\pm 1 в противном случае (плюс или минус выбирается в зависимости от четности числа простых делителей ~n).

Функция Мёбиуса является мультипликативной функцией. Важное значение функции Мёбиуса в теории чисел связано с формулой обращения Мёбиуса. 

Лит.: Чандрасекхаран К. Введение в аналитическую теорию чисел = Introduction to Analytic Number Theory. — М.: «Мир», 1974. — 188 с.

Loading

Календарь

«  Сентябрь 2019  »
ПнВтСрЧтПтСбВс
      1
2345678
9101112131415
16171819202122
23242526272829
30

Архив записей

Друзья сайта

  • Заказать курсовую работу!
  • Выполнение любых чертежей
  • Новый фриланс 24