Project Euler Problem 73 Solution

Project Euler Problem 73 Statement

Consider the fraction, $\dfrac n d$, where $n$ and $d$ are positive integers. If $n \lt d$ and $\operatorname{HCF}(n, d)=1$, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for $d \le 8$ in ascending order of size, we get: $$\frac 1 8, \frac 1 7, \frac 1 6, \frac 1 5, \frac 1 4, \frac 2 7, \frac 1 3, \mathbf{\frac 3 8, \frac 2 5, \frac 3 7}, \frac 1 2, \frac 4 7, \frac 3 5, \frac 5 8, \frac 2 3, \frac 5 7, \frac 3 4, \frac 4 5, \frac 5 6, \frac 6 7, \frac 7 8$$

It can be seen that there are $3$ fractions between $\dfrac 1 3$ and $\dfrac 1 2$.

How many fractions lie between $\dfrac 1 3$ and $\dfrac 1 2$ in the sorted set of reduced proper fractions for $d \le 12\,000$?

Solution

Project Euler Problem 73 asks us to count the number ofreduced proper fractions (fractions in lowest terms) that lie between two given fractions. Commonly, the specific problem is to count the fractions in the interval $(\tfrac{1}{3}, \tfrac{1}{2})$. More generally, we might want to count fractions in $(\tfrac{1}{a+1}, \tfrac{1}{a})$. For each denominator $d$, we look for numerators $p$ such that

We want the count of such $p/d$ when $p/d$ is in lowest terms (i.e., $\gcd(p,d) = 1$) for all $d \leq D$, where $D$ is an upper limit on the denominators.

Methodology

1. ceildiv = lambda a, b: -(-a // b)

   This lambda “ceiling division” function that returns $\lceil a/b \rceil$. We use Python’s floor-division on negative numbers to get the ceiling.

2. Array n
   n = [0] * D
   The list n stores, for each denominator d (from 0 up to $D-1$), how many numerators $p$ fit in the interval $\bigl(d/(a+1),\ d/a\bigr)$ *before considering the “reduced” condition*. Later, we’ll adjust these counts to account for fractions that are not in lowest terms.

3. Main Loop (from d = 1 to d = D-1)
   

   for d in range(1, D):
       n[d]+= ceildiv(d, A) - ceildiv(d, A+1) - 1
       n[2*d::d] = [k - n[d] for k in n[2*d::d]]

   • n[d]+= ...:

     This computes how many integer numerators p lie strictly between $d/(A+1)$ and $d/A$. The expression

     $$\text{ceildiv}(d, A) - \text{ceildiv}(d, A+1) - 1$$

     basically finds how many integers p satisfy

     $$\frac{d}{A+1} < p < \frac{d}{A}.$$

     The $-1$ is there to exclude edge cases or off-by-one overlaps when counting integers strictly in that open interval.

   • n[2*d::d] = [k - n[d] for k in n[2*d::d]]:
     This line is the sieve-like step that removes fractions which are not in lowest terms. If you’ve just found $n[d]$ valid fractions for denominator $d$, then any multiple of $d$ (like 2*d, 3*d, etc.) inherits some of those fractions in a non-reduced form. By subtracting n[d] from n[2*d], n[3*d], etc., we ensure we don’t overcount. Essentially, if a fraction can be reduced to denominator d, it shouldn’t be counted again with a larger denominator that shares the same gcd.

Overview

• Counting numerators that fit in the fraction range:
  For each denominator $d$, we want the number of integer numerators $p$ so that $\tfrac{p}{d}$ is in the interval $\bigl(\tfrac{1}{a+1}, \tfrac{1}{a}\bigr)$. The difference of the two ceiling divisions (plus the $-1$) gives exactly the count of integer $p$ in that open interval.
• Ensuring fractions are in lowest terms:
  The second step, updating n[2*d::d], works like a sieve (similar in spirit to the Sieve of Eratosthenes). When you find $n[d]$ “new” fractions for denominator $d$, you know that any denominator that is a multiple of $d$ should not count those fractions again because they would not be in lowest terms. Subtracting n[d] from n[2*d], n[3*d], etc., removes duplicates caused by non-reduced forms.
• Summing the results:
  At the end, sum(n) gives the total number of fractions across all denominators up to $D-1$ (or $D$, depending on how you set the loop), that lie in the desired interval and are in lowest terms.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 73

HackerRank Project Euler 73: How many fractions lie between $\frac{1}{A+1}$ and $\frac{1}{A}$ where (1 < A ≤ 100) in the sorted set of reduced proper fractions with denominator less than or equal to $D$ where (1 < D < 2×10^6)?

Last Word