What is the probability that a large integer has at least one small factor?

Question

I have large integer $N$. What is the probability that it has at least one factor that is less than $B$?

Answer 1

If $N$ has some factor less than or equal to $B$, then it must have some prime factor less than or equal to $B$.

Let the number of primes less than or equal to $B$ be $\pi(B)$.

According to the prime number theorem, this is asymptotically $$\pi(B) \sim \frac{B}{\ln B}$$

If $p_n$ is the $n^{\text{th}}$ prime number, then $p_{\pi(B)}$ is the largest prime less than $B$.

If $N$ is significantly larger than the primorial $p_{\pi(B)}\#$, then we can assume that the probability that $N$ is divisible by any of the first $\pi(B)$ primes is approximately equal to the probability that any natural number chosen from $\{1,2,3,4,...,p_{\pi(B)}\#-1, p_{\pi(B)}\#\}$ is divisible by any of the first $\pi(B)$ primes.

We can proceed now by inclusion-exclusion.

---

Let $$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)\}$$

Suppose $s$ is chosen uniformly randomly from the elements of $S$. We want to know the probability that this randomly chosen $s\in S$ is divisible by some prime factor $t\in T$.

---

The number of elements $s\in S$ that are divisible by $p_1=2$ is $$\left\lfloor\frac{p_{\pi(B)}\#}{2}\right\rfloor$$

The number of elements $s\in S$ that are divisible by $p_n$ is likewise $$\left\lfloor\frac{p_{\pi(B)}\#}{p_n}\right\rfloor$$

Our first count of the number of elements of $S$ that are divisible by some prime factor in $T$, grossly overcounting, is therefore

$$\displaystyle\sum_{k=1}^{\pi(B)}\left\lfloor\frac{p_{\pi(B)}\#}{p_k}\right\rfloor$$

---

We must now count the elements of $S$ that have exactly two prime factors in $T$, since we've counted those twice.

The number of elements $s \in S$ that are divisible by $p_1p_2 = 2\cdot 3=6$ is

$$\left\lfloor\frac{p_{\pi(B)}\#}{6}\right\rfloor$$

The number of elements $s\in S$ that are divisible by $p_i$ and $p_j$ is likewise $$\left\lfloor\frac{p_{\pi(B)}\#}{p_ip_j}\right\rfloor$$

We'll have to subtract all terms of this form, for any two distinct choices of $i,j \in R$

After that, we'll have to add back terms of the form $$\left\lfloor\frac{p_{\pi(B)}\#}{p_ip_jp_k}\right\rfloor$$ because those terms will have been undercounted.

Then we'll need to subtract terms of the form $$\left\lfloor\frac{p_{\pi(B)}\#}{p_ip_jp_kp_l}\right\rfloor$$

In general, if there are an even number of prime factors then the term with their product in the denominator will be subtracted, and if there are an odd number of prime factors then the term with their product in the denominator will be added.

---

Let the power set of $R$ be $\mathcal{P}(R)$. Then for any set $A \in \mathcal{P}(R)$, the corresponding term that we must include or exclude is $$\left\lfloor\displaystyle\frac{p_{\pi(B)}\#}{\displaystyle\prod_{k\in A} p_k}\right\rfloor$$

Whether or not we subtract or add this term is dependent on the cardinality of $A$, so we can incorporate this by multiplying by $(-1)^{|A|}$.

---

The final result of the whole inclusion-exclusion calculation is

$$\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)$$

This is the number of elements $s\in S$ that are not divisible by some prime factor $t \in T$.

---

Since $S$ has $p_{\pi(B)}\#$ elements, the probability that a randomly chosen element of $S$ has some factor $t \in T$ is $$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)}\#}$$

where

• $p_n$ is the $n^\text{th}$ prime number
• $\pi(B)$ is the number of primes less than or equal to $B$
• $p_n\#$ is the $n^\text{th}$ primorial
• $R = \{1,2,3,4,...,\pi(B)\}$
• $\mathcal{P}(R)$ is the power set of $R$

---