Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
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
3  
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
1  
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
1  
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

1 Answer 1

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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