Utilizar el principio de inclusión-exclusión para calcular la proporción de números divisibles por factores

Question

Dejemos que $m_1, ..., m_r$ sean números coprimos por pares y $N=\prod\limits_{i=1}^r m_i$ . Así que estoy tratando de calcular la proporción de los números del 1 al N que no son divisibles por ninguno de los $m_i$ Así que he utilizado el Principio de Inclusión-Exclusión, pero tengo una expresión muy larga de sumas y me preguntaba cómo puedo simplificarla.

Así, para el tamaño del conjunto de todos los números entre 1 y n no divisibles por ninguno de los $m_i$ es : $$N-\sum_{i} N/m_i + \sum_{i<j} N/m_im_j - \sum_{i<j<k} N/m_im_jm_k \quad + ...$$ Entonces para la proporción sólo dividiendo por N obtuve: $$1-\sum_{i} 1/m_i + \sum_{i<j} 1/m_im_j - \sum_{i<j<k} 1/m_im_jm_k \quad + ...$$

Answer 1

Así que, en primer lugar, sugeriría no dividir por N, al menos no inicialmente. Imagina que tienes $r=3$ entonces $$ N-\sum_i \frac{N}{m_i} + ... = m_1m_2m_3 + m_1m_2 + m_1m_3 + m_2m_3 - m_1 - m_2 - m_3 - 1 $$ Entonces, claramente $$ m_1m_2m_3 + m_1m_2 + m_1m_3 + m_2m_3 - m_1 - m_2 - m_3 - 1 = (m_1-1)(m_2-1)(m_3-1) $$ Esto puede ampliarse a valores mayores de r.