# Counting fractions with $n$ digits in the numerator and denominator

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!

-
Do you mean exactly $n$ digits or at most $n$? –  Srivatsan Sep 5 '11 at 7:10
Srivatsan, "exactly". –  Billy Bob Suggs Sep 5 '11 at 7:11
Basically you want the number of pairs $(r,s)$, each $\in[b^{n-1},b^n-1]$, with $r<s$ and $\gcd(r,s)=1$. I'm doubtful there's a pretty formula for this. –  anon Sep 5 '11 at 7:37
I googled the first few numbers for $b=10$ and came up with no results at all, neither at the integer search database. Looks bad for your formula. –  Listing Sep 5 '11 at 8:26
Each term in the $b=2$ sequence is pretty close to 4 times the previous term, as one would expect. –  Gerry Myerson Sep 5 '11 at 10:33

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