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
    Do you mean exactly $n$ digits or at most $n$?2011-09-05
  • 0
    Srivatsan, "exactly".2011-09-05
  • 3
    Basically you want the number of pairs $(r,s)$, each $\in[b^{n-1},b^n-1]$, with $r and $\gcd(r,s)=1$. I'm doubtful there's a pretty formula for this.2011-09-05
  • 0
    Would [tag:elementary-number-theory] be appropriate to add? I'm not sure...2011-09-05
  • 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.2011-09-05
  • 0
    Huh, $1, 6, 26, 111, 440, 1767, 7057, 28305, 113158$ (the sequence for $b=2$) isn't in the OEIS either... this looks hard.2011-09-05
  • 0
    Short of it having something to do with the Euler totient function, I have nothing to add.2011-09-05
  • 1
    Each term in the $b=2$ sequence is pretty close to 4 times the previous term, as one would expect.2011-09-05
  • 0
    @J. M., I'm having trouble reproducing your numbers. The 3-bit numbers are 4, 5, 6, and 7. The reduced proper fractions are 4/5, 4/7, 5/6, 5/7, 6/7. That's 5; you say 6. The 4-bit fractions are 8/9, 8/11, 8/13, 8/15, 9/10, 9/11, 9/13, 9/14, 10/11, 10/13, 11/12, 11/13, 11/14, 11/15, 12/13, 13/14, 13/15, 14/15, which is 18; how do you get 26?2011-09-05
  • 0
    @Gerry: Ooh, you're right; apparently I screwed up in my program somewhere. Here's what I got after fixing my program: $1, 5, 18, 82, 306, 1251, 4952, 19978, 79630$2011-09-05
  • 0
    ...by the way, @Gerry, I would have understood tagging this [tag:number-theory], but why precisely the analytic sort?2011-09-05
  • 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