Вопрос о функции, подобной функции Эйлера

[ZeroMem]

Добрый день!

Некоторое время бьюсь над одной проблемой, и пока точного аналитического решения вопроса не нашел (лишь очень грубое эмпирическое), построил достаточно оптимизированный алгоритм численного вычисления. Прошу содействия людей по дискретной математике и теории чисел.

Собственно, проблема.
Функция Эйлера $ \varphi(n), n \in N $ выражает количество взаимно-простых чисел с $n$ из отрезка $[1;n]$. Пусть дано некоторое $q > n, q \in N$. Чему будет равно количество взаимно-простых c $q$ чисел в отрезке $[1;n]$?

Пытаюсь построить аналитический вывод формулы, так как на основании теоремы о включении-исключении программа-решение была "накидана".

[maxal]

ZeroMem в сообщении #532923 писал(а):

Чему будет равно количество взаимно-простых c $q$ чисел в отрезке $[1;n]$?

$$\sum_{d|q} \mu(d)\cdot \left\lfloor \frac{n}{d}\right\rfloor$$

[ZeroMem]

Немного покопался, попытаюсь интерпретировать подобный ответ. Где не прав, прошу поправьте. С функцией Мёбиуса практически не работал.

Сумма проходит по всем делителям $d | q$. При разложении $q=p_1^{k_1}p_2^{k_2}...p_n^{k_n}$, в Вашей сумме те делители, что состоят из одного и более простого числа, где хотя бы одно $p_i$ имеет степень $k_i \geqslant 2 $, будет давать $\mu(d)=0$. Значит в сумме учитываются лишь всевозможные $d=\prod p_i, i \in [1;n]$.

$\left\lfloor \frac{n}{d} \right\rfloor$ - говорит сколько чисел из отрезка $[1;n]$ делится на простые $2, 3, 5$ и.т.д, а также на всевозможные произведения простых, вида $d=\prod p_i, i \in [1;n]$ (вот тут хотелось бы поподробнее, непонятно почему именно всегда $\left\lfloor \frac{n}{d} \right\rfloor$ дает количество чисел из отрезка, делящихся, например, на $2, 3, 5$). Применяя теорему о включениях-исключениях, получаем количество чисел, имеющих общие делители $d$ с $q, d \ne 1$.

Но если мне нужно количество взаимно-простых чисел, значит формула должна принять вид:

$$n - \sum_{d|q} \mu(d)\cdot \left\lfloor \frac{n}{d}\right\rfloor$$

Или я где-то ошибаюсь?

[maxal]

Формула имеет именно тот вид, что я написал (в частности, $d=1$ соответствует всему интервалу - оно входит в сумму с знаком +).
Проверьте свои выкладки на любом численном примере.

[ZeroMem]

Спасибо, понял!

Мое недопонимание было из-за того, что в определении как раз не учитывал $d=1$, Мой вопрос в этом случае автоматически отпадает.