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

1 Answer 1

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
  • 1
    $\begingroup$ Ah, I should’ve known this was a common function! Cool. $\endgroup$ Apr 13, 2019 at 11:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .