Задача по ТЧ

ssz1977

Модуль то сумы по n<=x (M(n)/n) <=1, где M(n)-функция Мёбиуса.
Доказать!

margo11

а как там функция мебиуса определяется?

ssz1977

μ(n) определена для всех положительных натуральных чисел n и принимает значения {-1, 0, 1} в зависимости от характера разложения числа n на простые сомножители:
μ(n) = 1 если n не делится на квадрат простого числа и разложение n на простые множители состоит из чётного числа сомножителей;
μ(n) = −1 если n не делится на квадрат простого числа и разложение n на простые множители состоит из нечётного числа сомножителей;
μ(n) = 0 если n делится на квадрат простого числа.
Принято считать что μ(1) = 1.

margo11

уже не раз писалось решение этой задачи, но поиском не нашел. будем вспоминать.
1 = n - [n/p1] - .. - [n/p2] - ... - [n/pk] + [n/p1p2] + [n/p1p3] + ... - [n/p1p2p3] - ....
Пояснение: берем все числа, вычитаем делящиеся на p1, p2, ..., pk (вычлись все числа, кроме 1, но некоторые по несколько раз добавляем делящиеся на p1 и p2, p1 и p3 и т.д., потом вычитаем делящиеся на p1p2p3, и т.д. и т.п.
Теперь избавляемся от целых частей, и получаем
1 = n*(1 - 1/p1 - .. - 1/pk + 1/p1p2 + ...) + S, где S - сумма оставшихся дробных частей. Сумма в скобах - искомая. Делим на n, переносим, видим
t <= n sum(M(t)/t) = 1/n - S/n. Остается объяснить, почему то, что справа, не превосходит по модулю единицы.

margo11

Каждое из чисел p_i1*p_i2*...*p_is не превосходит n и не равно 1. Поэтому разных дробных частей в S не более n-1.

ssz1977

Большое спасибо!
Оставить комментарий
Имя или ник:
Комментарий: