0

I was looking at anomalous cancellation and started to wonder what percentage of proper fractions using n digits or less are in their simplest form? (not including $\frac x x$ as a proper fraction).For example $\frac 4 8$ uses two digits (not including 0 before a digit as a digit) or less, but wouldn't count, because it's not in it's simplest form.

  • Firstly how would you work out how many proper fractions there are using n digits or less ( I assume a triangular number?)
  • Could this be generalised to other bases?
  • Has the percentage got to do with the distribution of primes since it's linked to divisibility?
  • In that case could you approximate the percentage using the approximations of the number of primes in an interval?
TStancek
  • 1,027
  • 5
  • 14
Oddly Asymmetric
  • 940
  • Are you double counting $\frac{2}{1}$ and $\frac{1}{2}$? If these two are both included in the total, then you have $n^2-n$ possible fractions ($n^2$ for fractions $\frac{1}{1} \dots \frac{n}{n}$ and $-n$ cause there are $n$ occurrences of $\frac{x}{x}$) – Dando18 Jun 22 '17 at 15:18
  • Only proper fractions. – Oddly Asymmetric Jun 22 '17 at 16:43
  • In that case there are $\frac{n(n-1)}{2}$ possible fractions. Your intuition about the triangle numbers is correct, because there $\frac{n(n+1)}{2}$ combinations up to $n$, where the denominator is larger, and you subtract $n$ possibilities where we have $\frac{x}{x}$. – Dando18 Jun 22 '17 at 17:19

2 Answers2

0

For each denominator $n$, there are $\phi(n)$ numerators $k$ between $1$ and $n$ which are relatively prime to $n$, and therefore each $k/n$ is proper and in lowest terms. Pick a bound $N$ on the denominators. Then there are $N(N+1)/2$ fractions with denominator less than $N$. For each $n=1\ldots N$, there are $\phi(n)$ fractions in lowest terms.

So the number of fractions of denominator less than or equal to $N$ in lowest terms is

$$\Phi(n) = \sum_n^N \phi(n) \sim \frac{3N^2}{\pi^2} +O(N \ln N)$$

according to

http://mathworld.wolfram.com/TotientSummatoryFunction.html

Dividing, we get the ration you ask for

$$ \sim \frac{\frac{3N^2}{\pi^2} +O(N \ln N)}{\frac{N(N+1)}{2} } \sim \frac{6}{\pi^2} = 60.8\%.$$

B. Goddard
  • 1
0

A problem like this it helps to write out the first couple terms, $$ \frac 1 2, \frac 1 3, \frac 2 3, \color{red}{\frac 1 4}, \boxed{\color{red}{\frac 2 4}}, \color{red}{\frac 3 4}, \frac 1 5, \frac 2 5, \frac 3 5, \frac 4 5, \color{red}{\frac 1 6}, \boxed{\color{red}{\frac 2 6}}, \boxed{\color{red}{\frac 3 6}}, \boxed{\color{red}{\frac 4 6}}, \color{red}{\frac 5 6}, \\ \frac 1 7, \frac 2 7, \frac 3 7, \frac 4 7, \frac 5 7, \frac 6 7, \color{red}{\frac 1 8}, \boxed{\color{red}{\frac 2 8}}, \color{red}{\frac 3 8}, \boxed{\color{red}{\frac 4 8}}, \color{red}{\frac 5 8}, \boxed{\color{red}{\frac 6 8}}, \color{red}{\frac 7 8}, \dots $$

First off, notice that we are counting the $n^{th}$-denominator $n-1$ times, so your intuition about triangle numbers is correct. The total number of possible fractions up to $n$ is $\frac{n(n+1)}{2}$.

We want to look for the probability that two numbers share no factors (are coprime), which is $\frac{6}{\pi^2} \approx 61\%$.

For numerical confirmation I wrote some c++ code to analyze the number of proper fractions that are reducible. Below is the output and the code is at the bottom, 

1 digits - 20.0000 % - 9/45 are reducible
2 digits - 37.3333 % - 1848/4950 are reducible
3 digits - 38.9810 % - 194710/499500 are reducible
4 digits - 39.1870 % - 19591516/49995000 are reducible
5 digits - 39.2052 % - 1960239248/4999950000 are reducible

Here we see the number of reducible fractions slowly approaches $40\%$.

std::tuple<ull, ull> percent_reducible_with_prime_search(unsigned digs) 
{
    ull reducible_sum = 0;
    ull lim = pow(10, digs);
    ull total_reducible = lim * (lim-1) / 2.0;
    for(ull d=2; d<lim; d++) {
        if(is_prime(d)) continue;
        for(ull n=1; n<d; n++) {
            if(gcd(n,d) != 1) reducible_sum += 1;
        }
    }
    return std::make_tuple(reducible_sum, total_reducible);
}
Dando18
  • 5,368