What is the probability of choosing a number divisible by $2,3$ or $19$ from $1,2,...,\ 1{,}000{,}000$?

Question

A number of $1,2,...,\ 1{,}000{,}000$ is randomly selected, each number with the same probability. Specify a suitable probability space and calculate the probability that the chosen number is divisible by $2,3$ or $19$.

The probability space $(\Omega, P) $ would be $\Omega = \{1,2...,\ 1{,}000{,}000 \}$ and $P(A)= \frac{|A|}{1{,}000{,}000}$ with $A \subset \Omega$. Now I just have to find the set $A=\{x: x \in \Omega\ \land x \ \text{divisible by} \ 2, \ 3\ \text{or} \ 19 \}$. But I do not know how to calculate the cardinality of the set. Can someone explain me that?

Answer 1

For divisibility by $2$, the sequence is $$2,4,6,8,.....\ 1000000$$ For divisibility by $3$, $$3,6,9,12,.....\ 999999$$ For divisibility by $19$, $$19,38,57,76,.....\ 999989$$ But if we add all of these, we will be counting some numbers like $6, 38,57$ more than once. So we have to use inclusion-exclusion principle.

For divisibility by $6$, the sequence is $$6, 12, 18, 24,......\ 999996$$ For divisibility by $38$, $$38,76,114,.....\ 999970$$ For divisibility by $57$, $$57,114,.....\ 999951$$

So now we can subtract these sequences from the first three.

But then we will be subtracting multiples of $114$ once more than necessary. So we need to add in the sequence of multiples of $114$, $$114,228,.....999894$$

Now you can find the cardinality of each of these and add/subtract according to the inclusion-exclusion principle.

EDIT according to comment:

The sequence of numbers divisible by $3$ is an arithmetic progression (with common difference $3$ and first term $3$). Using the formula for general term, $$a_n=a+(n-1)d$$ $$999999=3+(n-1)3$$ $$n=333333$$ So the cardinality of this set is $333333$. This method can be used for any such sequence.

An alternative method is as follows: If we divide all of the terms by a specific number, the number of terms remains the same. So $3,6,9,12,.....\ 999999$ has the same number of terms as $1,2,3,4......\ 333333$. It's obvious that the number of terms is $333333$. You can use this method for all such sequences.

Now to clear your second doubt, those numbers will have to be excluded which appear in more than one of the $3$ sets. For example, which numbers will be common to the first two sets? The first one has multiples of $2$, and the second one has multiples of $3$. So naturally, the common numbers are the ones that are multiples of both $2$ and $3$, i.e. they are multiples of $6$.

Similarly, the numbers common to the first and third sets are multiples of $38$, the numbers common to the second and third sets are multiples of $57$, and the numbers common to all three sets are multiples of $114$. I have already mentioned above how to calculate the cardinality of these.

---

Now, to make you understand which sets to include and exclude, I'm going to take a simpler example. Please note that it is not the same question as above. Consider the numbers from $1$ to $30$. If you want to find numbers that are multiples of $2$, $3$ and $5$, the three sets are as follows- $$2,4,6,.....30$$ $$3,6,9,.....30$$ $$5,10,15,.....30$$

We see that the first set has $15$ elements, the second has $10$ and the third has $6$.

The sets of common numbers to each pair of sets are (multiples of $6$, $10$ and $15$ respectively): $$6,12,18,24,30$$ $$10,20,30$$ $$15,30$$ We see that exactly one number is common to these three sets: $$30$$

Now: if we count only the first three sets, we end up with cardinality of $$15+10+6=31$$ We see that numbers like $6, 10, 15$ etc. are being counted twice. So we subtract the cardinalities of these three. $$31-(5+3+2)=21$$ But wait! We've counted $30$ thrice, and subtracted it thrice too. So we need to count it once more. $$21+1=22$$ We can confirm that the final set that we need is (by counting manually) $$2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30$$ Which has a cardinality of $22$, so our answer is correct.

---

Now we can extend this principle to the question and solve it.

Answer 2

A number $n\in{\mathbb Z}$ is admissible if it is a multiple of at least one of the primes $2$, $3$, $19$. The $(2,3,19)$ divisibility pattern of the numbers $n\in{\mathbb Z}$ is periodic with period $2\cdot3\cdot19=114$. From $[1..114]$ the $38$ numbers $$6k+1, \ 6k+5\qquad(0\leq k\leq18)$$ are neither multiples of $2$ nor $3$. It is easy to check that among the first multiples of $19$ two numbers belong to this set, namely $19$ and $95$. We can therefore say that $(114-38)+2=78$ numbers in $[1..114]$ are admissible.

Now $8772\cdot114=1\,000\,008$. When the problem had dealt with all admissible numbers in $[1..1\,000\,008]$ we could answer $p={78\over114}$. Since the given range ends at $1\,000\,000$ we have to be more precise: From the $8772\cdot78=684\,216$ admissible numbers in $[1..1\,000\,008]$ we have to dismiss the admissible numbers in $[1\,000\,001..1\,000\,008]$. A case analysis shows that $5$ numbers have to be dismissed. Therefore the final probability is $$p={684\,216-5\over 1\,000\,000}=0.684\,211\ .$$

Answer 3

Comment: Implementing @Righter's (+1) program, you could let a computer do the counting. Using R, I counted $692\,308.$ [I did it for multiples of 2, 3, and 13, to illustrate the idea without giving the exact answer.]

d.2 = seq(2,10^6, by = 2)
length(d.2)
[1] 500000

d.3 = seq(3,10^6, by = 3)
length(d.3)
[1] 333333

d.13 = seq(13,10^6, by = 13)
length(d.13)
[1] 76923

c = c(d.2, d.3, d.13)  # concatenate
length(c)
[1] 910256

u = unique(c)          # eliminate duplicates
length(u)
[1] 692308             # Answer

Look at unique values up to 100.

sort(u[u <= 100])
 [1]   2   3   4   6   8   9  10  12  13  14  15  16
[13]  18  20  21  22  24  26  27  28  30  32  33  34
[25]  36  38  39  40  42  44  45  46  48  50  51  52
[37]  54  56  57  58  60  62  63  64  65  66  68  69
[49]  70  72  74  75  76  78  80  81  82  84  86  87
[61]  88  90  91  92  93  94  96  98  99 100

Before elimination of duplicates, a few of which are noted by hand, there were 'more':

sort(c[c <= 100])
 [1]   2   3   4   6   6   8   9  10  12  12  13  14  # 2 6's
[13]  15  16  18  18  20  21  22  24  24  26  26  27  # 2 18's
[25]  28  30  30  32  33  34  36  36  38  39  39  40  # 2 35's
[37]  42  42  44  45  46  48  48  50  51  52  52  54  # 2 42's
[49]  54  56  57  58  60  60  62  63  64  65  66  66  # 2 54's
[61]  68  69  70  72  72  74  75  76  78  78  78  80  # 3 78's
[73]  81  82  84  84  86  87  88  90  90  91  92  93
[85]  94  96  96  98  99 100