Existe-t-il un algorithme efficace pour déterminer la probabilité qu'un gros entier choisi de manière aléatoire n'est pas divisible par un entier d'un certain ensemble?
-
29-09-2020 - |
Question
donné un ensemble de 10 entiers $ a= a_1, a_2, \ cdots a_ {10} $ , y a-t-il un algorithme efficace qui peut me dire quelle est la probabilitéun entier choisi au hasard entre 1 $ $ et 10 $ ^ {10} $ n'est pas divisible par n'importe quel membre de cet ensemble.
Je comprends que le principe d'exclusion d'inclusion peut être utilisé pour résoudre ce problème, mais je ne peux pas comprendre comment la mettre en œuvre afin que cela fonctionne efficacement.
La solution
let $ \ mathbf x $ être un nombre aléatoire dans la plage 1 $, \ ldots, n $ , et laissez $ e_i $ désignant l'événement que $ \ mathbf x $ est divisible par $ a_i $ . Vous êtes intéressé par la probabilité qu'aucun des événements $ E_1, \ LDOTS, E_M $ se produise (dans votre cas, $ m= 10 $ ). Utilisation du principe d'exclusion d'inclusion, cela réduit à calculer la probabilité des événements de la forme $ e_ {i_1} \ terres \ cdots \ terres e_ {i_k} $ , c'est-à-dire que $ \ mathbf x $ est divisible par tout $ a_ {i_1}, \ ldots, a_ {i_k} $ . Depuis une $ \ mathbf x $ est divisible par une bande de nombres IFF il est divisible par leur LCM, il suffit de déterminer la probabilité que $ \ mathbf x $ est divisible par $ A $ .
parmi 1 $, \ ldots, n $ , les chiffres divisibles par $ a $ sont $$ a, 2a, 3a, \ ldots, \ llfloor n / a \ rfloor a, $$ Dans Total $ \ LFLOOR N / A \ RFLOOR $ $ numéros. D'où la probabilité que $ \ mathbf x $ est divisible par $ a $ est exactement $$ \ frac {\ lflfor n / a \ rfloor} {n}. $$