¿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?
-
29-09-2020 - |
Pregunta
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.
Solución
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
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}. $$