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

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?

• Use inclusion-exclusion principle and arithmetic progressions Apr 10, 2021 at 15:22
• Could you do it if $A=\{x: x \in \Omega\ \land x \ \text{divisible by$2$}\}?$ If so, and assuming you could generalize, you'd want to use the inclusion-exclusion principle. Apr 10, 2021 at 15:22
• @JohnHughes If it would be only 2, I could calculate the probability but I am not quite sure how the approach you mentioned would look like. Further help would be appreciated Apr 10, 2021 at 15:27
• @Logik Do you know the idea of inclusion-exclusion principle or do you want an explanation of the principle too? Apr 10, 2021 at 16:55

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.

• I had the same approach but then some questions appeared: First, I know the cardinality of the set for numbers divisible by 2 but not 3 and 19 for example, so how would I calculate the cardinality of these sets? Second, from where do I know which numbers appear more than once such that I can exclude the duplicates and then merge all sets into a set without duplicates and take the cardinality. In theory I know what to do but in practice I have no clue how to calculate each cardinality and add/subtract them - that is my main problem Apr 11, 2021 at 14:28
• @Logik Is it clear now? Apr 11, 2021 at 16:02
• It became much clearer now, thanks! Apr 11, 2021 at 17:36

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

• My method agrees with your answer (using multiples of 2, 3, 19). Apr 10, 2021 at 19:14

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)


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