Contando fracciones con$n$ dígitos en el numerador y el denominador

Question

Jugando con fracciones, finalmente he tenido que plantearse la siguiente pregunta:

Existe una formula para contar cuántas fracciones propias en términos mínimos con $n$ base$b$ dígitos, tanto en el numerador y el denominador hay?

Así, por ejemplo, cosas como $0$, $\frac24$, $\frac22$, y $\frac43$ no cuentan.

Mi primer pensamiento fue que estarían relacionados con los números triangulares, pero esto parece recuento de las fracciones no en términos mínimos así. Supongo que la última fórmula se puede expresar como un número triangular menos alguna corrección, pero no puedo averiguar lo que el término de corrección debe ser.

Gracias!

Answer 1

Fijo $s$, el número de $r$, $1\le r\le s$, $\gcd(r,s)=1$, se denota $\phi(s)$, y se llama la phi de Euler-función. Fijo $x$, el número de pares de $(r,s)$ con $1\le r\le s\lt x$, $\gcd(r,s)=1$, en otras palabras, el número correcto de la reducción de fracciones con denominador menor que $x$$\sum_{s\lt x}\phi(s)$. Llamar a esto $\Phi(x)$. Se sabe que $\Phi(x)$ es asintótica a $(3/\pi^2)x^2$. El número correcto de la reducción de fracciones con denominador de exactamente $n$ dígitos en base $b$ luego $\Phi(b^n)-\Phi(b^{n-1})$, que es aproximadamente el $(3/\pi^2)(b^{2n}-b^{2n-2})$. Ahora quieres saber cómo muchos de estos tienen un $n$dígitos numerador. Para$s$$b^{n-1}$, apenas va a calificar. Para $s$ cerca de $b^n$, parece plausible para mí que acerca de $b-1$ cada $b$ va a calificar, simplemente porque $b-1$ cada $b$ números de cerca de $b^n$ ha $n$ dígitos. Así que me gustaría dividir la diferencia y la figura que estamos viendo alrededor de $(3/\pi^2)(b^{2n}-b^{2n-2})(b-1)/(2b)$.