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.
A Computer Science friend of mine 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 . We would like to know what is the probability that is divisible by 2,3,5 or 7. Since 2 divides half of the set of 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 It is trivial to show . And in there are 210 integers. So by the inclusion-exclusion principle:
Which implies there are 48 of such integers not divisible by 2, 3, 5 or 7.
Overall, it is possible to say then that approximates the proportion of natural numbers that are not a multiple of 2, 3, 5 or 7 as becomes larger and larger.
By the Prime Number Theorem, we know that where is the prime-counting function. So whereas the probability of finding a prime number becomes smaller as becomes larger, the probability of finding a natural number not divisible by 2, 3, 5 or 7 approaches 0.22857 as 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 ))