4
$\begingroup$

Playing around with fractions, I eventually had to consider the following question:

Is there a formula for counting how many proper fractions in lowest terms with $n$ base-$b$ digits in both the numerator and the denominator are there?

So, for instance, things like $0$, $\frac24$, $\frac22$, and $\frac43$ don't count.

My first thought was that they'd be related to triangular numbers, but this seems to count the fractions not in lowest terms as well. I presume the final formula can be expressed as a triangular number minus some correction, but I can't figure out what that correction term ought to be.

Thanks!

  • 0
    @J. M., in my answer, I used the result, $\Phi(x)$ asymptotic to $(3/\pi^2)x^2$, which I think of as analytic number theory. And I'm sure if anyone is going to get a more accurate answer than mine, some analytic techniques will be needed. But I won't object if someone re-tags the question.2011-09-05

1 Answers 1

4

For fixed $s$, the number of $r$, $1\le r\le s$, $\gcd(r,s)=1$, is denoted $\phi(s)$, and is called the Euler phi-function. For fixed $x$, the number of pairs $(r,s)$ with $1\le r\le s\lt x$, $\gcd(r,s)=1$, in other words the number of proper reduced fractions with denominator less than $x$, is $\sum_{s\lt x}\phi(s)$. Call this $\Phi(x)$. It is known that $\Phi(x)$ is asymptotic to $(3/\pi^2)x^2$. The number of proper reduced fractions with denominator of exactly $n$ digits in base $b$ is then $\Phi(b^n)-\Phi(b^{n-1})$, which is roughly $(3/\pi^2)(b^{2n}-b^{2n-2})$. Now you want to know how many of these have an $n$-digit numerator. For $s$ just over $b^{n-1}$, hardly any will qualify. For $s$ close to $b^n$, it seems plausible to me that about $b-1$ out of every $b$ will qualify, simply because $b-1$ out of every $b$ numbers near $b^n$ have $n$ digits. So I'd split the difference and figure that we're looking at about $(3/\pi^2)(b^{2n}-b^{2n-2})(b-1)/(2b)$.