Project Euler Problem 71 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, \frac 3 8, \mathbf{\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 $\dfrac 2 5$ is the fraction immediately to the left of $\dfrac 3 7$.

By listing the set of reduced proper fractions for $d \le 1\,000\,000$ in ascending order of size, find the numerator of the fraction immediately to the left of $\dfrac 3 7$.

Solution

Rephrasing the problem

Project Euler Problem 71 involves finding fractions between 0 and 1 that are closest to a given fraction \( \frac{a}{b} \) with denominators up to \( n \). The goal is to identify the fraction \( \frac{c}{d} \) such that:

• \( \frac{c}{d} < \frac{a}{b} \)
• \( d \leq n \)
• The difference \( \frac{a}{b} - \frac{c}{d} \) is minimized.

for _ in range(int(input())):
    a, b, n = map(int, input().split())
    ln, ld, rn, rd = 0, 1, 1, 1
    while ld + rd <= n:
        mn, md = ln + rn, ld + rd
        if a * md < b * mn:
            rn, rd = mn, md
        elif a == mn and b == md:
            nums = (n - ld - b) // b
            ln += a * nums
            ld += b * nums
            rn, rd = mn, md
        else:
            ln, ld = mn, md
    print(ln, ld)

Variables Explained

• ln, ld: Numerator and denominator of the current left fraction (initially \( \frac{0}{1} \)).
• rn, rd: Numerator and denominator of the current right fraction (initially \( \frac{1}{1} \)).
• mn, md: Numerator and denominator of the middle fraction calculated as \( \frac{ln + rn}{ld + rd} \).

Solving Method

1. Initialization:

   Start with two boundary fractions: \( \frac{0}{1} \) (left) and \( \frac{1}{1} \) (right).

2. While Loop:

   The loop continues as long as the sum of the denominators \( ld + rd \) does not exceed \( n \). In each iteration, compute the middle fraction \( \frac{mn}{md} = \frac{ln + rn}{ld + rd} \).

3. Comparing Fractions:
   • Condition 1: If \( a \times md < b \times mn \), it implies \( \frac{a}{b} < \frac{mn}{md} \). Hence, update the right fraction to the middle fraction.
   • Condition 2: If \( a == mn \) and \( b == md \), perform an optimization to jump ahead by calculating how many times the denominator can be incremented by \( b \) without exceeding \( n \).
   • Else: Update the left fraction to the middle fraction since \( \frac{mn}{md} \) is less than \( \frac{a}{b} \).
4. Termination:

   Once \( ld + rd > n \), the loop terminates, and the closest fraction \( \frac{ln}{ld} \) is printed.

Step-by-Step Walkthrough

Let's walk through an example to illustrate how the script operates.

Example Input

1
3 7 8

• \( a = 3 \)
• \( b = 7 \)
• \( n = 8 \)

Initial State

• Left Fraction: \( \frac{ln}{ld} = \frac{0}{1} \)
• Right Fraction: \( \frac{rn}{rd} = \frac{1}{1} \)

Iteration 1

• Compute Middle Fraction:

  \[ mn = ln + rn = 0 + 1 = 1 \]

  \[ md = ld + rd = 1 + 1 = 2 \]

  \[ \frac{mn}{md} = \frac{1}{2} \]

• Compare with \( \frac{3}{7} \):

  \[ 3 \times 2 = 6 < 7 \times 1 = 7 \]

  Since \( 6 < 7 \), update the right fraction to \( \frac{1}{2} \).

• Updated State:
  • Left Fraction: \( \frac{0}{1} \)
  • Right Fraction: \( \frac{1}{2} \)

Iteration 2

• Compute Middle Fraction:

  \[ mn = 0 + 1 = 1 \]

  \[ md = 1 + 2 = 3 \]

  \[ \frac{mn}{md} = \frac{1}{3} \]

• Compare with \( \frac{3}{7} \):

  \[ 3 \times 3 = 9 > 7 \times 1 = 7 \]

  Since \( 9 > 7 \), update the left fraction to \( \frac{1}{3} \).

• Updated State:
  • Left Fraction: \( \frac{1}{3} \)
  • Right Fraction: \( \frac{1}{2} \)

Iteration 3

• Compute Middle Fraction:

  \[ mn = 1 + 1 = 2 \]

  \[ md = 3 + 2 = 5 \]

  \[ \frac{mn}{md} = \frac{2}{5} \]

• Compare with \( \frac{3}{7} \):

  \[ 3 \times 5 = 15 > 7 \times 2 = 14 \]

  Since \( 15 > 14 \), update the left fraction to \( \frac{2}{5} \).

• Updated State:
  • Left Fraction: \( \frac{2}{5} \)
  • Right Fraction: \( \frac{1}{2} \)

Iteration 4

• Compute Middle Fraction:

  \[ mn = 2 + 1 = 3 \]

  \[ md = 5 + 2 = 7 \]

  \[ \frac{mn}{md} = \frac{3}{7} \]

• Compare with \( \frac{3}{7} \):

  \[ 3 = 3 \quad \text{and} \quad 7 = 7 \]

  This triggers Condition 2. Calculate how many times we can add \( b \) to \( ld \) without exceeding \( n \):

  \[ nums = \left\lfloor \frac{8 - 5 - 7}{7} \right\rfloor = \left\lfloor \frac{-4}{7} \right\rfloor = -1 \]

  Since \( nums \) is negative, no further updates are made. The loop exits.

Termination

• The loop condition \( ld + rd = 5 + 2 = 7 \leq 8 \) holds, but after updating, the next \( ld + rd = 5 + 2 = 7 \) remains within bounds.
• Finally, the closest fraction found is \( \frac{2}{5} \), which is printed.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 71

HackerRank Project Euler 71: By listing the set of reduced proper fractions for $d\le N$ in ascending order of size, find the numerator and denominator of the fraction immediately to the left of $\frac{a}{b}$.