Variación de euler totient/phi función

Question

Es allí cualquier manera eficiente , a encontrar para un determinado n, la cardinalidad del conjunto formado por todos los números coprimes a n, pero más grande que m(suponiendo que yo sepa el primer factorización de n y m)

Estoy buscando la aplicación que es fácil+rápido (como el de euler totient/phi función, que dada la factorización de n sólo tendrá O(logn) pasos).

Answer 1

Usted puede tratar de encontrar su lugar el número de números de $1 \leq x \leq m$ que son relativamente primos a $n$. Permite denotar $d(m,n)$ este número. Su respuesta es $\phi(n)- d(m,n)$.

Si $p_1,..,p_k$ son todos los números primos dividiendo $n$, un simple inclusión-exclusión en el cálculo nos dice lo $m-d(m,n)$ (es decir, los números que no son primos relativos con n) es:

Hay $\left\lfloor \frac{m}{p_i} \right\rfloor$ múltiplos de $p_i$, $\left\lfloor \frac{m}{p_ip_j} \right\rfloor$ múltiplos de $p_i p_j$ y así sucesivamente. Así

$$m-d(m,n)= \sum_{i=1}^k \left\lfloor \frac{m}{\,p_i\,} \right\rfloor -\sum_{ 1 \leq i < j \leq k} \left\lfloor \frac{m}{p_ip_j} \right\rfloor+\sum_{ 1 \leq i < j< l \leq k} \left\lfloor \frac{m}{p_ip_jp_k} \right\rfloor-\ldots+(-1)^{k-1} \left\lfloor \frac{m}{p_1p_2....p_k} \right\rfloor$$

Por lo tanto, a menos que cometí un error, su número es

$$\phi(n)-m+\sum_{i=1}^k \left\lfloor \frac{m}{p_i} \right\rfloor -\sum_{ 1 \leq i < j \leq k} \left\lfloor \frac{m}{p_ip_j} \right\rfloor+\sum_{ 1 \leq i < j< l \leq k} \left\lfloor \frac{m}{p_ip_jp_k} \right\rfloor-\ldots+(-1)^{k-1} \left\lfloor \frac{m}{p_1p_2....p_k} \right\rfloor$$

P. S. no estoy seguro de si la suma es calculable en tiempo razonable, no se $2^k$ que $k$ es el número de factores primos de $n$. $k$ es normalmente menor que $\log_2(n)$ pero no estoy seguro de si es siempre menor que $\log(\log(n))$.

Además, es improbable que la suma puede ser simplificado aún más, debido a la parte entera. El caso fácil es al $m$ tiene exactamente el mismo divisores como $n$, y, a continuación, se puede simplificar a $\phi(n)-\phi(m)$, pero en este caso, este resultado puede ser obtenido fácilmente directamente.

Answer 2

Usted variación parece tener 2 parámetros, $n$$m$, pero no importa - para cualquier $n$, {\em all} de los números primos, excepto el (finito) conjunto de factores primos, se coprime a cualquier número de $n$ (excepto a sí misma), así que el conjunto de los números primos $\ge m$ todavía va a ser infinito.