¿Existe un algoritmo eficiente para determinar la probabilidad de que un entero grande aleatoriamente elegido no sea divisible por cualquier entero de algún conjunto?

Question

Dado un conjunto de 10 enteros $ a= a_1, a_2, \ cdots a_ {10} $ , ¿hay un algoritmo eficiente que pueda decirme cuál puede decirme cuál es la probabilidad?Un entero elegido al azar entre $ 1 $ y $ 10 ^ {10} $ es no Divisible por cualquier miembro de este conjunto.

Entiendo que el principio de exclusión de inclusión se puede usar para resolver este problema, pero no puedo averiguar cómo implementarlo para que funcione de manera eficiente.

nota : cuando digo "eficiente", me refiero a un tiempo polinomial, pero no estoy completamente seguro de lo que califica como el tiempo polinomial es este caso, ya que ambas variables son fijas.

Answer 1

Let $ \ mathbf x $ ser un número aleatorio en el rango $ 1, \ ldots, n $ , y deja que $ e_i $ denote el evento que $ \ mathbf x $ es divisible por $ A_I $ . Le interesa la probabilidad de que ninguno de los eventos $ E_1, \ LDOTS, E_M $ suceda (en su caso, $ m= 10 $ ). Utilizando el principio de exclusión de inclusión, esto se reduce a calcular la probabilidad de los eventos del formulario $ e_ {i_1} \ land \ cdots \ land e_ {i_k} $ , Es decir, $ \ mathbf x $ es divisible por todo $ a_ {i_1}, \ ldots, a_ {i_k} $ . Desde una $ \ mathbf x $ es divisible por un montón de números IFF es divisible por su LCM, se basa en determinar la probabilidad de que $ \ mathbf x $ es divisible por $ a $ .

entre $ 1, \ ldots, n $ , los números divisibles por $ a $ son $$ A, 2A, 3A, \ LDOTS, \ LFLOOR N / A \ RFLOOR A, $$ en total $ \ lfloor n / a \ rfloor $ números. Por lo tanto, la probabilidad de que $ \ mathbf x $ es divisible por $ a $ es exactamente $$ \ frac {\ lfloor n / a \ rfloor} {n}. $$