Problem #71 easy

Ordered Fractions

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$ .

View on Project Euler

Implementations

#include <iostream>
#include <numeric>

int ordered_fractions()
{
    long long best_n = 0, best_d = 1;
    for (int d = 1; d <= 1000000; ++d) {
        long long n = (3LL * d - 1) / 7;
        if (n > 0 && std::gcd((int)n, d) == 1) {
            if (best_n * (long long)d < n * best_d) {
                best_n = n;
                best_d = d;
            }
        }
    }
    return best_n;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
    std::cout << "Answer: " << ordered_fractions() << std::endl;
}
#endif // #if ! defined UNITTEST_MODE

View on GitHub

O(N) time, O(1) space (linear scan with GCD checks)

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;

public class Solution071 implements Solution {
  public String solve() {
    return "428570";
  }
}

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - actual solution requires finding closest fraction below 3/7

function orderedFractions() {
  return 428570;
}

module.exports = {
  answer: () => orderedFractions()
};

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - full solution requires Farey sequence iteration

def solve():
    limit = 1000000
    target = 3 / 7
    max_n = 0
    max_d = 1
    for d in range(1, limit + 1):
        n = int(d * target)
        if n / d < target and n / d > max_n / max_d:
            max_n = n
            max_d = d
    return max_n

View on GitHub

O(N) time, O(1) space (simple linear search for closest fraction)

#include <iostream>
#include <numeric>

int ordered_fractions()
{
    long long best_n = 0, best_d = 1;
    for (int d = 1; d <= 1000000; ++d) {
        long long n = (3LL * d - 1) / 7;
        if (n > 0 && std::gcd((int)n, d) == 1) {
            if (best_n * (long long)d < n * best_d) {
                best_n = n;
                best_d = d;
            }
        }
    }
    return best_n;
}

#if ! defined UNITTEST_MODE
int main(int argc, char const *argv[])
{
    std::cout << "Answer: " << ordered_fractions() << std::endl;
}
#endif // #if ! defined UNITTEST_MODE

View on GitHub

O(N) time, O(1) space (linear scan with GCD checks)

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;

public class Solution071 implements Solution {
  public String solve() {
    return "428570";
  }
}

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - actual solution requires finding closest fraction below 3/7

function orderedFractions() {
  return 428570;
}

module.exports = {
  answer: () => orderedFractions()
};

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - full solution requires Farey sequence iteration

def solve():
    limit = 1000000
    target = 3 / 7
    max_n = 0
    max_d = 1
    for d in range(1, limit + 1):
        n = int(d * target)
        if n / d < target and n / d > max_n / max_d:
            max_n = n
            max_d = d
    return max_n

View on GitHub

O(N) time, O(1) space (simple linear search for closest fraction)

package main

import (
  "fmt"
)

func orderedFractions() int {
  limit := 1000000
  maxN := 0
  for d := 5; d <= limit; d++ {
    n := (3*d - 1) / 7
    if n > 0 && gcd(n, d) == 1 {
      if float64(n)/float64(d) > float64(maxN)/float64(limit) {
        maxN = n
      }
    }
  }
  return maxN
}

func gcd(a, b int) int {
  for b != 0 {
    a, b = b, a%b
  }
  return a
}

func main() {
  fmt.Println(orderedFractions())
}

View on GitHub

O(N) time, O(1) space (linear iteration with GCD checks)

pub fn ordered_fractions() -> u64 {
    let limit = 1_000_000;
    let mut max_n = 0;
    let mut max_d = 1;
    for d in 2..=limit {
        let n = (3 * d - 1) / 7;
        if n * 7 < 3 * d && n > 0 && gcd(n, d) == 1 {
            if n as f64 / d as f64 > max_n as f64 / max_d as f64 {
                max_n = n;
                max_d = d;
            }
        }
    }
    max_n
}

fn gcd(a: u64, b: u64) -> u64 {
    if b == 0 { a } else { gcd(b, a % b) }
}

View on GitHub

O(N) time, O(1) space (linear scan with GCD and fraction comparison)

tvarley.github.io/src/content/euler/problem-071.md