Problem 71: Ordered Fractions

Project Euler Problem 71 Solution

EulerSolve provides an optimized solution for Project Euler Problem 71, Ordered Fractions, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary We consider reduced proper fractions $p/q$ with $q \le 1{,}000{,}000$, list them in increasing order, and look for the fraction immediately to the left of $3/7$. Equivalently, we want the largest reduced fraction strictly smaller than $3/7$ whose denominator does not exceed $10^6$. The winning fraction is $428570/999997$, so the required numerator is $428570$. Mathematical Approach The implementation does not construct the ordered list explicitly. Instead, it scans all denominators, computes the best possible numerator for each one, and maintains the largest reduced fraction found so far. That turns the ordering question into a clean arithmetic optimization problem. The best numerator for a fixed denominator Fix a denominator $d$. To stay strictly left of $3/7$, we need $$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$$ Since $3d$ is an integer, the largest integer $n$ satisfying this strict inequality is obtained by replacing it with $7n \le 3d - 1$. Therefore the only numerator worth testing for this denominator is $$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$$ So every denominator contributes at most one serious candidate. Why reduced fractions must be enforced The ordered set in the problem contains each reduced proper fraction exactly once....

Detailed mathematical approach

Problem Summary

We consider reduced proper fractions $p/q$ with $q \le 1{,}000{,}000$, list them in increasing order, and look for the fraction immediately to the left of $3/7$. Equivalently, we want the largest reduced fraction strictly smaller than $3/7$ whose denominator does not exceed $10^6$. The winning fraction is $428570/999997$, so the required numerator is $428570$.

Mathematical Approach

The implementation does not construct the ordered list explicitly. Instead, it scans all denominators, computes the best possible numerator for each one, and maintains the largest reduced fraction found so far. That turns the ordering question into a clean arithmetic optimization problem.

The best numerator for a fixed denominator

Fix a denominator $d$. To stay strictly left of $3/7$, we need

$$\frac{n}{d} \lt \frac{3}{7} \iff 7n \lt 3d.$$

Since $3d$ is an integer, the largest integer $n$ satisfying this strict inequality is obtained by replacing it with $7n \le 3d - 1$. Therefore the only numerator worth testing for this denominator is

$$n_d = \left\lfloor \frac{3d - 1}{7} \right\rfloor.$$

So every denominator contributes at most one serious candidate.

Why reduced fractions must be enforced

The ordered set in the problem contains each reduced proper fraction exactly once. If $\gcd(n_d,d) \ne 1$, then $n_d/d$ is only a non-reduced copy of a fraction that already appears with a smaller denominator. Such a candidate cannot be the new immediate left neighbor in the reduced list, so the implementations skip it.

Comparing candidates without floating point

Suppose the current best reduced fraction is $a/b$, and the new candidate is $n/d$. Because all denominators are positive, we can compare them exactly by cross-multiplication:

$$\frac{n}{d} \gt \frac{a}{b} \iff nb \gt ad.$$

This avoids rounding issues and keeps the whole search in integer arithmetic.

The running invariant of the scan

After processing all denominators up to some value $D$, the stored fraction is the largest reduced fraction below $3/7$ among all denominators $2,3,\dots,D$. The invariant is straightforward: when the next denominator arrives, its unique candidate is either discarded because it is not reduced, ignored because it is not better, or promoted because it is larger than the current best. By induction, the invariant remains true until the scan reaches $10^6$.

Worked example: $N = 8$

The small checkpoint used by the implementations is $N=8$. Evaluating the formula gives

$$ \begin{aligned} d=3 &\Rightarrow n=1 &&\Rightarrow \frac{1}{3},\\ d=4 &\Rightarrow n=1 &&\Rightarrow \frac{1}{4},\\ d=5 &\Rightarrow n=2 &&\Rightarrow \frac{2}{5},\\ d=6 &\Rightarrow n=2 &&\Rightarrow \frac{2}{6}\ \text{(not reduced)},\\ d=7 &\Rightarrow n=2 &&\Rightarrow \frac{2}{7},\\ d=8 &\Rightarrow n=3 &&\Rightarrow \frac{3}{8}. \end{aligned} $$

Among the reduced fractions strictly below $3/7$, the largest is $2/5$. That is why the checkpoint expects the numerator $2$.

A theoretical cross-check from Farey neighbors

The scan is the method actually implemented, but the final answer can be verified number-theoretically. Adjacent reduced fractions $a/b \lt c/d$ in a Farey sequence satisfy

$$bc - ad = 1.$$

For the predecessor $p/q$ of $3/7$, this becomes

$$3q - 7p = 1.$$

Hence $3q \equiv 1 \pmod{7}$, so $q \equiv 5 \pmod{7}$. The largest denominator with that residue and $q \le 10^6$ is $q=999997$. Substituting back gives

$$p = \frac{3q - 1}{7} = \frac{3 \cdot 999997 - 1}{7} = 428570.$$

This confirms that the immediate left neighbor is exactly $428570/999997$.

How the Code Works

The C++, Python, and Java implementations keep a current best numerator and denominator, initialized to $0/1$. They iterate through every denominator from $2$ up to the limit, compute $n=\lfloor(3d-1)/7\rfloor$, reject the candidate when $\gcd(n,d) \ne 1$, and otherwise compare $n/d$ to the stored best fraction using cross-multiplication.

No fraction list is materialized, and no sorting is needed. Each loop iteration does one formula evaluation, one gcd test, and one exact comparison. The C++ and Python versions also include a small check at $N=8$; the Java version runs the same scan directly for the full limit.

Complexity Analysis

The denominator scan performs $N-1$ iterations. Each iteration uses constant-size integer arithmetic plus a gcd computation, so the total running time is $O(N \log N)$ in the standard arithmetic model. For the fixed bound $N=10^6$, this is easily fast enough.

The memory usage is $O(1)$, because the implementation stores only the current best fraction and a handful of loop variables. A closed-form shortcut exists for this particular target, but the implemented scan is simple, exact, and general.

Footnotes and References

Problem page: Project Euler 71
Farey sequence: Wikipedia - Farey sequence
Mediant and neighboring fractions: Wikipedia - Mediant
Euclidean algorithm: Wikipedia - Euclidean algorithm
Modular arithmetic: Wikipedia - Modular arithmetic

Problem 71 source code

C++

#include <cstdint>
#include <iostream>
#include <numeric>
#include <string>

namespace {

using i64 = std::int64_t;

struct Options {
    int limit = 1000000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 2;
}

int solve(const int limit) {
    i64 best_n = 0;
    i64 best_d = 1;

    for (int d = 2; d <= limit; ++d) {
        const i64 n = (3LL * d - 1) / 7LL;
        if (std::gcd(static_cast<i64>(d), n) != 1LL) {
            continue;
        }
        if (n * best_d > best_n * d) {
            best_n = n;
            best_d = d;
        }
    }

    return static_cast<int>(best_n);
}

bool run_checkpoints() {
    if (solve(8) != 2) {
        std::cerr << "Checkpoint failed for limit=8" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

import math
import sys

def solve(limit):
    best_n = 0
    best_d = 1
    
    for d in range(2, limit + 1):
        n = (3 * d - 1) // 7
        if math.gcd(d, n) != 1:
            continue
        if n * best_d > best_n * d:
            best_n = n
            best_d = d
    
    return int(best_n)

def main():
    limit = 1000000
    run_checkpoints = True
    
    args = sys.argv[1:]
    for arg in args:
        if arg == "--skip-checkpoints":
            run_checkpoints = False
        elif arg.startswith("--limit="):
            try:
                limit = int(arg[8:])
            except ValueError:
                sys.stderr.write("Invalid limit value\n")
                sys.exit(1)
        else:
            sys.stderr.write(f"Unknown argument: {arg}\n")
            sys.exit(1)
    
    if limit < 2:
        sys.stderr.write("Limit must be at least 2\n")
        sys.exit(1)
    
    if run_checkpoints:
        if solve(8) != 2:
            sys.stderr.write("Checkpoint failed for limit=8\n")
            sys.exit(2)
    
    print(solve(limit))

if __name__ == "__main__":
    main()

Java

public class Euler71 {
    static long gcd(long a, long b) {
        while (b != 0) {
            long t = b;
            b = a % b;
            a = t;
        }
        return a;
    }

    public static void main(String[] args) {
        long bestN = 0, bestD = 1;
        for (int d = 2; d <= 1000000; d++) {
            long n = (3L * d - 1) / 7;
            if (gcd(n, d) != 1)
                continue;
            if (n * bestD > bestN * d) {
                bestN = n;
                bestD = d;
            }
        }
        System.out.println(bestN);
    }
}