Take two numbers x and y between 1 and 100. What’s the probability that x/y is an integer?

It was stated, as an inconsequential remark, in some lecture notes I was reading that if we are to choose two natural numbers in a certain interval and divide one by the other, that it is quite likely that the quotient will not be an integer. Seems reasonable, but I wanted to quantify this.

Take two numbers $$x, y \in [1,m] \cap \mathbb{N}, m \in \mathbb{N}$$. What is the probability that $$\frac{x}{y}$$ is an integer? Can we find a closed-form expression for this?

Well, it is clear that $$\frac{x}{y}$$ is an integer if and only if $$x$$ is divisible by $$y$$. In other words, $$x = yk$$, for some $$k \in \mathbb{Z}$$, which is our result after computing the quotient.

Consider the case $$m = 100$$. For each possible value for $$y$$, we need to count the number of multiples of $$y$$ within this interval. For $$y = 1$$, there are 100 possible values, from 1 to $$m$$. For $$y = 2$$, there are 50 as $$50 \cdot 2 = 100$$, for $$y = 3$$ there are 33 as $$3 \cdot 33 = 99$$, etc. The number of possible pairs is then the sum of these counts.

In general, the number of multiples of $$y$$ between 1 and $$m$$ is given by $$\lfloor \frac{m}{y} \rfloor$$. Thus, dividing by the number of possible pairs, our probability is:

$$\frac{1}{m^2} \sum_{n=1}^{m} \lfloor {\frac{m}{n}} \rfloor$$

When $$y > \frac{m}{2}$$ we only have one possible value for x, and so we can make a slight optimisation by summing only halfway and then adding on the correct number of extra $$x$$ values. We have:

$$\frac{1}{m^2} (( \sum_{n=1}^{\frac{m}{2}} \lfloor {\frac{m}{n}} \rfloor ) + \frac{m}{2} )$$

which can be further simplified to

$$\frac{1}{m^2} \sum_{n=1}^{\frac{m}{2}} \lfloor {\frac{m}{n}} \rfloor + \frac{1}{2m}$$

Now this is a reasonably neat closed-form expression. My question is though, can we write this in a simpler way? It’s not obvious to me how we can express this sum in some other way, as the floor function will cause us trouble if we naively apply a series formula.

If you’re curious, the probability in the case $$m = 100$$ is $$0.0482$$, which is rather unlikely!

$$\frac{1}{m^2} \to 0$$, $$\frac{1}{2m} \to 0$$ and our sum is bounded so the probability approaches zero as expected.

For $$m = 1000$$ it’s $$0.007069$$, and for $$m = 10000$$ it’s $$0.00093668$$.

Let $$E$$ be the event "$$x/y$$ is an integer".

Then $$P(E)=\sum_{x=1}^m P(E | X=x) P(X=x)= \sum_{x=1}^m \frac{d(x)}{m} \frac{1}{m}= \frac{1}{m^2} \sum_{x=1}^m d(x)$$

where $$d(x)$$ is the number-of-divisors function. I doubt that you'll get anything simpler than this.

The sum is quite well known.

Asymptotically (see here, formula 37)

$$P(E) \approx \frac{\log(m)}{m} + \frac{2 \gamma-1}{m}$$

For $$m=100$$ this approximation gives $$0.047596$$ instead of the exact $$0.0482$$

• Ah, I should’ve known this was a common function! Cool. – 雨が好きな人 Apr 13 at 11:32