2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.