Tengo un entero grande $N$ . ¿Cuál es la probabilidad de que tenga al menos un factor que sea menor que $B$ ?
Respuesta
¿Demasiados anuncios?
Si $N$ tiene algún factor menor o igual a $B$, entonces debe haber algún factor primo menor o igual a $B$.
Deje que el número de números primos menores o iguales a $B$ ser $\pi(B)$.
De acuerdo con el teorema de los números primos, esto es asintóticamente $$\pi(B) \sim \frac{B}{\ln B}$$
Si $p_n$ es el $n^{\text{th}}$ primer número, $p_{\pi(B)}$ es el más grande de prime menos de $B$.
Si $N$ es significativamente mayor que el primorial $p_{\pi(B)}\#$, entonces podemos asumir que la probabilidad de que $N$ es divisible por alguno de los primeros a$\pi(B)$ de los números primos es aproximadamente igual a la probabilidad de que cualquier número natural elegido de $\{1,2,3,4,...,p_{\pi(B)}\#-1, p_{\pi(B)}\#\}$ es divisible por alguno de los primeros a$\pi(B)$ números primos.
Podemos proceder ahora por la inclusión-exclusión.
Deje $$S = \{1,2,3,4,...,p_{\pi(B)}\#-1, p_{\pi(B)}\#\}$$
$$T = \{2,3,5,7,..., p_{\pi(B)-1}, p_{\pi(B)}\}$$
$$R = \{1,2,3,4,...,\pi(B)-1, \pi(B)\}$$
Supongamos $s$ es elegido uniformemente al azar de los elementos de $S$. Queremos saber la probabilidad de que esta elegida al azar, $s\in S$ es divisible por algún factor primordial $t\in T$.
El número de elementos de a$s\in S$ que son divisibles por $p_1=2$ es $$\left\lfloor\frac{p_{\pi(B)}\#}{2}\right\rfloor$$
El número de elementos de a$s\in S$ que son divisibles por $p_n$ es, igualmente, $$\left\lfloor\frac{p_{\pi(B)}\#}{p_n}\right\rfloor$$
Nuestro primer recuento del número de elementos de a$S$ que son divisibles por algún factor principal en la $T$, muy overcounting, es por lo tanto
$$\displaystyle\sum_{k=1}^{\pi(B)}\left\lfloor\frac{p_{\pi(B)}\#}{p_k}\right\rfloor$$
Ahora debemos contar los elementos de $S$ que tienen exactamente dos factores primos en $T$, ya que ha contado con aquellos dos veces.
El número de elementos de a$s \in S$ que son divisibles por $p_1p_2 = 2\cdot 3=6$ es
$$\left\lfloor\frac{p_{\pi(B)}\#}{6}\right\rfloor$$
El número de elementos de a$s\in S$ que son divisibles por $p_i$ e $p_j$ es, igualmente, $$\left\lfloor\frac{p_{\pi(B)}\#}{p_ip_j}\right\rfloor$$
Tendremos que restar todos los términos de este formulario para cualquiera de las dos opciones distintas de $i,j \in R$
Después de eso, vamos a añadir de nuevo los términos de la forma $$\left\lfloor\frac{p_{\pi(B)}\#}{p_ip_jp_k}\right\rfloor$$ , porque dichos términos han sido omitidas.
A continuación, tendremos que restar términos de la forma $$\left\lfloor\frac{p_{\pi(B)}\#}{p_ip_jp_kp_l}\right\rfloor$$
En general, si hay un número par de factores primos, a continuación, el término con su producto en el denominador, se restan, y si hay un número impar de factores primos, a continuación, el término con su producto en el denominador será añadido.
Deje que el juego de poder de $R$ ser $\mathcal{P}(R)$. Entonces para cualquier conjunto $A \in \mathcal{P}(R)$, el correspondiente término que se deben incluir o excluir es $$\left\lfloor\displaystyle\frac{p_{\pi(B)}\#}{\displaystyle\prod_{k\in A} p_k}\right\rfloor$$
Si podemos o no restar o sumar este término depende de la cardinalidad de a$A$, por lo que podemos incorporar esta multiplicando por $(-1)^{|A|}$.
El resultado final de la totalidad de la inclusión-exclusión en el cálculo de
$$\displaystyle\sum_{A\in \mathcal{P}(R)} \left(\left(-1\right)^{|A|}\left\lfloor\displaystyle\frac{p_{\pi(B)}\#}{\displaystyle\prod_{k\in A} p_k}\right\rfloor\right)$$
Este es el número de elementos de a$s\in S$ que no divisible por algunos el primer factor de $t \in T$.
Desde $S$ ha $p_{\pi(B)}\#$ elementos, la probabilidad de que un elegido al azar elemento de $S$ tiene algún factor de $t \in T$ es $$P(N \text{ has some factor less than or equal to } B) \,\,\, \approx \,\,\,1 - \displaystyle\frac{\displaystyle\sum_{A\in \mathcal{P}(R)} \left(\left(-1\right)^{|A|}\left\lfloor\displaystyle\frac{p_{\pi(B)}\#}{\displaystyle\prod_{k\in A} p_k}\right\rfloor\right)}{p_{\pi(B)}\#}$$
donde
- $p_n$ es el $n^\text{th}$ número primo
- $\pi(B)$ es el número de números primos menores o iguales a $B$
- $p_n\#$ es el $n^\text{th}$ primorial
- $R = \{1,2,3,4,...,\pi(B)\}$
- $\mathcal{P}(R)$ es el juego de poder de $R$
