Probability for finding product?

Question

A number is chosen randomly from the first billion natural numbers. What is the probability that the product of the number with its two immediate successors is divisible by 24 ?

Answer 1

You pick an integer $k$ and look at the product $k(k+1)(k+2)$ to see if it is divisible by $24$. Any three consecutive integers will have one integer divisible by $3$, so the real question is how many such products are divisible by $8$.

Half of the time, $k$ will be even, if the picking mechanism is random. In those cases $k+2$ will be the next even number. It is well known that two consecutive even numbers will consist of one number that is divisible only once by $2$, and another number that is divisible by a power of two, so certainly divisible by $4$. Thus, when $k$ is randomly chosen to be even, the product $k(k+1)(k+2)$ will be divisible by both $3$ and $8$ and hence divisible by $24$.

If $k$ is chosen to be odd, then $k+1$ will be even, and divisible by $8$ only one quarter of the time, because the progression of even numbers $2,4,6,8,10,12,14,16,18,20\dots$ features powers of $2$ that progress $1,2,1,3,1,2,1,4,1\dots$ and only every fourth such number will have an exponent $\ge 3$ and be divisible by $8$. Thus When $k$ is chosen to be odd, The product $k(k+1)(k+2)$ will be divisible by $24$ one quarter of the time.

The total probability is $0.5\cdot 1+0.5\cdot 0.25=0.625$ or five eighths.

Answer 2

By "first billion natural numbers", I'm going to assume you mean all the numbers from $1$-$1,000,000,000$ (so 0 is not included). The trick here is to look at the numbers in terms of congruence classes mod $24$, of course. Given integers $x_{1}$ and $x_{2}$, they can be written as $24k_{1}+r_{1}$ and $24k_{2}+r_{2}$ respectively for some integers $k_1,k_2,r_1,r_2$. It is a fact of modular arithmetic that if $a_1\equiv b_1\mod(n)$ and $a_2\equiv b_2\mod(n)$, then $a_1a_2 \equiv b_1b_2 \mod(n)$.

Applied to $x_1$ and $x_2$, this means that $x_1x_2\equiv r_1r_2 \mod(24)$. If we were to add another integer into the mix, this would still hold (after being adjusted with an $r_3$ term). Since the remainder after division by $24$ can only be an integer strictly less than that, and we are concerned with triples of consecutive numbers, we need only examine triples from $(1,2,3)$ to $(24,25,26)$ for divisibility of their product by $24$. This is actually not that bad to simply enumerate: the first triple to qualify is $(6,7,8)$. The next three are $(7,8,9),(8,9,10)$ and $(10,11,12)$. $(12,13,14)$ is the one after that; the rest are $$(14,15,16),(15,16,17),(16,17,18),(18,19,20),(20,21,22),(22,23,24),(23,24,25),(24,25,26)$$ In other words, considering the $24$ congruence classes mod$(24)$, there are $13$ triples of consecutive classes whose product is congruent to $0$. $\frac{13}{24}$ is a little over $0.5$, and we should expect it to be fairly close to the final answer.

The second-to-last step is to figure out how many subsets of size $24$ there are in our range, noting that there are $1,000,000,000-2=999,999,998$ allowable first entries for an arbitrary triple in this range and hence the same number of possible triples altogether (a triple cannot start with $999,999,999$ or $1,000,000,000$). It so happens that $999,999,998 = 41,666,666\cdot 24 + 14$; in other words, there are $41,666,666$ sets of $24$ consecutive triples of numbers between $1$ and $1,000,000,000$, plus a set of $14$ triples of such numbers.

The final step is to compute how many valid triples there are altogether and the probability of finding one overall. Recall that in every set of $24$ triples, $13$ were valid. This means that each of the $41,666,666$ sets contributes $13$ valid triples, for a total of $541,666,658$. Out of the remaining $14$ triples, $6$ are valid, for a final total of $541,666,664$. The probability of choosing a number between $1$ and $1,000,000,000$ and having its product with its two successors be divisible by $24$ is therefore $\frac{541,666,664}{999,999,998}$, which is $0.542$ rounded to the nearest thousandth.