Project Euler Problem 73

Project Euler Problem 73

Solution

Answer: 7295372

1. Mathematical analysis

We want the number of reduced proper fractions

$$\frac{n}{d}$$

such that

$$\frac13 < \frac nd < \frac12 \quad\text{and}\quad \gcd(n,d)=1,$$

for all denominators

$$d \le 12000.$$

Step 1: Find the numerator range for each denominator

Fix a denominator $d$. We need:

$$\frac13 < \frac nd < \frac12.$$

Multiply through by $d$:

$$\frac d3 < n < \frac d2.$$

So the valid numerators are integers in

$$\left(\left\lfloor \frac d3 \right\rfloor + 1\right) \le n \le \left\lceil \frac d2 \right\rceil - 1.$$

But we must also require:

$$\gcd(n,d)=1.$$

Hence for each denominator $d$, we count integers $n$ in this interval that are coprime to $d$.

---

Step 2: Direct counting approach

A straightforward algorithm is:

For every denominator $d=2,3,\dots,12000$:

1. Compute the smallest possible numerator:

$$n_{\min}=\left\lfloor \frac d3 \right\rfloor +1$$ 2. Compute the largest possible numerator:

$$n_{\max}=\left\lfloor \frac{d-1}{2}\right\rfloor$$ 3. For every integer $n\in[n_{\min},n_{\max}]$:

• Check whether

$$\gcd(n,d)=1.$$

• If yes, count it.

The search space is manageable because:

• $d \le 12000$
• average interval length is about $d/6$

Total work is roughly a few tens of millions of gcd checks, which Python handles comfortably.

A more sophisticated number-theoretic solution uses the Farey sequence or a Möbius inversion count, but the brute-force gcd approach is already fast enough.

---

2. Python implementation

from math import gcd

def count_fractions(limit):
    total = 0

    # Check every denominator
    for d in range(2, limit + 1):

        # Numerators strictly between 1/3 and 1/2
        n_min = d // 3 + 1
        n_max = (d - 1) // 2

        # Count reduced fractions
        for n in range(n_min, n_max + 1):
            if gcd(n, d) == 1:
                total += 1

    return total

# Problem answer
result = count_fractions(12000)
print(result)

---

3. Code walkthrough

Import gcd

from math import gcd

We use the built-in greatest common divisor function to test whether a fraction is reduced.

---

Main counting function

def count_fractions(limit):
    total = 0

total stores the number of valid fractions.

---

Loop through denominators

for d in range(2, limit + 1):

We consider every denominator from 2 up to 12000.

---

Compute numerator bounds

n_min = d // 3 + 1
n_max = (d - 1) // 2

These ensure:

$$\frac13 < \frac nd < \frac12$$

strictly (not including endpoints).

Examples:

• $d=8$

$$8/3 \approx 2.67,\quad 8/2=4$$

So:

$$n=3$$

giving:

$$\frac38$$

---

Check coprimality

if gcd(n, d) == 1:
    total += 1

Only reduced fractions are counted.

For example, when $d \le 8$, the fractions between $1/3$ and $1/2$ are:

$$\frac38,\quad \frac25,\quad \frac37$$

Exactly 3, matching the problem statement.

---

4. Final verification

The count should be:

• much larger than the total for small $d$,
• positive,
• roughly proportional to $N^2$ (Farey sequence density argument).

For $N=12000$, a result in the millions is reasonable. Running the computation gives:

$$7,!295,!372$$

which matches the known Project Euler result.

Answer: 7295372