Euler Problem 73
================

Consider the fraction, n/d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 3 fractions between 1/3 and 1/2.

How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?


```python
from sympy import sieve
import numpy as np

N = 12000
mu = np.ones(N+1, dtype=int16)
for p in sieve.primerange(1, N+1):
    for k in range(p, N+1, p):
        mu[k] *= -1
    pp = p*p
    for k in range(pp, N+1, pp):
        mu[k] = 0
g = lambda n: int((n-2.0)**2/12+0.5)
print sum(mu[d] * g(N/d) for d in xrange(1, 10000))
```

    7295372


**Discussion:**

Let $g(n)$ denote the number of pairs of positive integers $(x,y)$ such that $y \le n$ and $\frac13 < \frac{x}{y} < \frac{1}{2}$. 
Let $f(n)$ denote the number of pairs with the above properties and the additional condition that $x$ and $y$ are relatively prime. Then 
$$g(n) = \sum_{k=1}^n f(n/k).$$ 
By the Mobius inversion formula, 
$$f(n) = \sum_{k=1}^n \mu(k) g(n/k).$$
It can be shown that if $n$ is an integer, $g(n)$ is the integer nearest to $\frac1{12} (n-2)^2$. 

Putting this information together gives an efficient algorithm for calculating $f(n)$.


```python

```

f5c7aca005c10ac59fe43712ce9b4c73e6bb3ab3
ipynb
Jupyter Notebook
Euler 073 - Counting primes in a range.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
2016-05-11T18:55:35.000Z
2019-12-27T21:38:43.000Z
Euler 073 - Counting primes in a range.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
Euler 073 - Counting primes in a range.ipynb
Radcliffe/project-euler
5eb0c56e2bd523f3dc5329adb2fbbaf657e7fa38
MIT
Qwen/Qwen-72B
1. YES
2. YES