Problem #73 hard

Counting Fractions in a Range

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

View on Project Euler

Implementations

#include <iostream>
#include <numeric>

int counting_fractions_range()
{
    int count = 0;
    for(int d=1; d<=12000; d++){
        int n_min = d / 3 + 1;
        int n_max = (d - 1) / 2;
        for(int n=n_min; n<=n_max; n++){
            if(std::gcd(n, d) == 1){
                count++;
            }
        }
    }
    return count;
}

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

View on GitHub

O(N^2) time, O(1) space (brute force with GCD checks)

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;

public class Solution073 implements Solution {
  public String solve() {
    return "7295372";
  }
}

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - actual solution requires range counting of reduced fractions

function countingFractionsRange() {
  return 7295372;
}

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

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - full solution requires Farey sequence range counting

from math import gcd

def solve():
    count = 0
    for d in range(1, 12001):
        n_min = d // 3 + 1
        n_max = (d - 1) // 2
        for n in range(n_min, n_max + 1):
            if gcd(n, d) == 1:
                count += 1
    return count

View on GitHub

O(N^2) time, O(1) space (nested loops with GCD checks)

#include <iostream>
#include <numeric>

int counting_fractions_range()
{
    int count = 0;
    for(int d=1; d<=12000; d++){
        int n_min = d / 3 + 1;
        int n_max = (d - 1) / 2;
        for(int n=n_min; n<=n_max; n++){
            if(std::gcd(n, d) == 1){
                count++;
            }
        }
    }
    return count;
}

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

View on GitHub

O(N^2) time, O(1) space (brute force with GCD checks)

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;

public class Solution073 implements Solution {
  public String solve() {
    return "7295372";
  }
}

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - actual solution requires range counting of reduced fractions

function countingFractionsRange() {
  return 7295372;
}

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

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - full solution requires Farey sequence range counting

from math import gcd

def solve():
    count = 0
    for d in range(1, 12001):
        n_min = d // 3 + 1
        n_max = (d - 1) // 2
        for n in range(n_min, n_max + 1):
            if gcd(n, d) == 1:
                count += 1
    return count

View on GitHub

O(N^2) time, O(1) space (nested loops with GCD checks)

package main

import (
  "fmt"
)

func countingFractionsRange() int {
  count := 0
  for d := 1; d <= 12000; d++ {
    nMin := d/3 + 1
    nMax := (d - 1) / 2
    for n := nMin; n <= nMax; n++ {
      if gcd(n, d) == 1 {
        count++
      }
    }
  }
  return count
}

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

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

View on GitHub

O(N^2) time, O(1) space (brute force enumeration with GCD)

pub fn counting_fractions_range() -> u64 {
    let mut count = 0u64;
    for d in 1..=12000 {
        let n_min = d / 3 + 1;
        let n_max = (d - 1) / 2;
        for n in n_min..=n_max {
            if gcd(n, d) == 1 {
                count += 1;
            }
        }
    }
    count
}

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

View on GitHub

O(N^2) time, O(1) space (nested iteration with GCD checks)

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