Some probability and number theory

(This post was featured in Crikey Math)

When I was doing my undergraduate studies, Number Theory was one of my most favourite courses. I thought I’d go into it but then my interests switched to Probability & Statistics and kind of moved away from the area a little bit. I still dabble in Number Theory from time to time though, which prompts the subject of this post.

My brother (who is a computer engineer) and I were talking about cryptography a few weeks ago and he casually mentioned that, just as a quick-and-easy check, if you have an unknown number that is not divisible by any of the first prime digits (that would be 2, 3, 5, and 7), then there’s a “pretty good chance” that said unknown number is prime. Just to formalize things a little bit, I would like to know what proportion of natural numbers are divisible by 2,3,5 or 7.

Let us start by setting n\in\mathbb{N} . We would like to know what is the probability that n is divisible by 2,3,5 or 7. Since 2 divides half of the set of \mathbb{N} we know right from the beginning that the probability is > 0.5.

The least common multiple of 2,3,5 and 7 is 2x3x5x7=210.

We know that 210 has the following list of factors. We build this list by systematically multiplying the numbers 2,3,5,7:

1-element factors: 1, 2, 3, 5, 7

2-element factors: 2×3=6, 2×5=10, 2×7=14, 3×5=15, 3×7=21, 5×7=35

3-element factors: 2x3x5=30, 2x3x7=42, 2x5x7=70, 3x5x7=105

4-element factor: 2x3x5x7=210

Let S(n)=\{210(n-1)+1, 210(n-1)+2, ..., 210n\}, n=1,2,... It is trivial to show S\subset \mathbb{N}. And in S(n) there are 210 integers. So by the inclusion-exclusion principle:

210-(105+70+42+30-35-21-15-14-10-6+7+5+3+2+1)= 210-162=48

Which implies there are 48 of such integers not divisible by 2, 3, 5 or 7.

Overall, it is possible to say then that \frac{48}{210}=\frac{8}{35}\approx 0.22857 approximates the proportion of natural numbers that are not a multiple of 2, 3, 5 or 7 as n becomes larger and larger.

By the Prime Number Theorem, we know that \frac{\pi(x)}{x}\sim \frac{1}{ln(x)} where \frac{\pi(x)}{x} is the prime-counting function. So whereas the probability of finding a prime number becomes smaller as x becomes larger, the probability of finding a natural number not divisible by 2, 3, 5 or 7 approaches 0.22857 as n becomes larger and larger.

In general, around 78% of natural numbers are divisible by 2, 3, 5 or 7.

Quick simulation to verify my stuff:

n <- 1:1000000 ##large n, the larger n the closer the true probability
n2 <- n%%2 ## %% gives me the division remainder
n3 <- n%%3
n5 <- n%%5
n7 <- n%%7


dd <- data.frame(n, n2, n3, n5, n7)

roww <- apply(dd, 1, function(row) all(row !=0 ))

dd1<-dd[roww,]


dim(dd1)[1]/1000000
[1] 0.228571