Problem #72 hard

Counting 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, \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 $21$ elements in this set.

How many elements would be contained in the set of reduced proper fractions for $d \le 1\,000\,000$ ?

View on Project Euler

Implementations

#include <iostream>
#include <vector>

long long counting_fractions()
{
    const int MAXN = 1000000;
    std::vector<long long> phi(MAXN+1);
    for(int i=0; i<=MAXN; i++) phi[i] = i;

    for(int i=2; i<=MAXN; i++){
        if(phi[i] == i){ // prime
            for(long long j=i; j<=MAXN; j+=i){
                phi[j] = phi[j] / i * (i-1);
            }
        }
    }

    long long sum = 0;
    for(int i=2; i<=MAXN; i++){
        sum += phi[i];
    }
    return sum;
}

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

View on GitHub

O(N log log N) time, O(N) space (totient sieve with summation)

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.math.BigInteger;

public class Solution072 implements Solution {
  public String solve() {
    return "303963552391";
  }
}

View on GitHub

O(1) time (hardcoded answer due to complexity)

Implementation placeholder - actual solution requires efficient totient computation

function countingFractions() {
  return 303963552391;
}

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

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - full solution requires totient function sieve

def solve():
    limit = 1000000
    phi = list(range(limit + 1))
    for i in range(2, limit + 1):
        if phi[i] == i:
            for j in range(i, limit + 1, i):
                phi[j] = phi[j] // i * (i - 1)
    return sum(phi[2:limit+1])

View on GitHub

O(N log log N) time, O(N) space (sieve-based totient computation)

package main

import (
  "fmt"
)

func countingFractions() int {
  limit := 1000000
  phi := make([]int, limit+1)
  for i := range phi {
    phi[i] = i
  }
  for i := 2; i <= limit; i++ {
    if phi[i] == i {
      for j := i; j <= limit; j += i {
        phi[j] = phi[j] / i * (i - 1)
      }
    }
  }
  sum := 0
  for i := 2; i <= limit; i++ {
    sum += phi[i]
  }
  return sum
}

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

View on GitHub

O(N log log N) time, O(N) space (totient sieve implementation)

pub fn counting_fractions() -> u64 {
    const LIMIT: usize = 1_000_000;
    let mut phi = vec![0u64; LIMIT + 1];
    for i in 0..=LIMIT {
        phi[i] = i as u64;
    }
    for i in 2..=LIMIT {
        if phi[i] == i as u64 {
            let mut j = i;
            while j <= LIMIT {
                phi[j] = phi[j] / i as u64 * (i as u64 - 1);
                j += i;
            }
        }
    }
    let mut sum = 0u64;
    for i in 2..=LIMIT {
        sum += phi[i];
    }
    sum
}

View on GitHub

O(N log log N) time, O(N) space (linear sieve for totient function)

#include <iostream>
#include <vector>

long long counting_fractions()
{
    const int MAXN = 1000000;
    std::vector<long long> phi(MAXN+1);
    for(int i=0; i<=MAXN; i++) phi[i] = i;

    for(int i=2; i<=MAXN; i++){
        if(phi[i] == i){ // prime
            for(long long j=i; j<=MAXN; j+=i){
                phi[j] = phi[j] / i * (i-1);
            }
        }
    }

    long long sum = 0;
    for(int i=2; i<=MAXN; i++){
        sum += phi[i];
    }
    return sum;
}

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

View on GitHub

O(N log log N) time, O(N) space (totient sieve with summation)

package org.tvarley.euler.solutions;

import org.tvarley.euler.Solution;
import java.math.BigInteger;

public class Solution072 implements Solution {
  public String solve() {
    return "303963552391";
  }
}

View on GitHub

O(1) time (hardcoded answer due to complexity)

Implementation placeholder - actual solution requires efficient totient computation

function countingFractions() {
  return 303963552391;
}

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

View on GitHub

O(1) time (hardcoded answer)

Placeholder implementation - full solution requires totient function sieve

def solve():
    limit = 1000000
    phi = list(range(limit + 1))
    for i in range(2, limit + 1):
        if phi[i] == i:
            for j in range(i, limit + 1, i):
                phi[j] = phi[j] // i * (i - 1)
    return sum(phi[2:limit+1])

View on GitHub

O(N log log N) time, O(N) space (sieve-based totient computation)

package main

import (
  "fmt"
)

func countingFractions() int {
  limit := 1000000
  phi := make([]int, limit+1)
  for i := range phi {
    phi[i] = i
  }
  for i := 2; i <= limit; i++ {
    if phi[i] == i {
      for j := i; j <= limit; j += i {
        phi[j] = phi[j] / i * (i - 1)
      }
    }
  }
  sum := 0
  for i := 2; i <= limit; i++ {
    sum += phi[i]
  }
  return sum
}

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

View on GitHub

O(N log log N) time, O(N) space (totient sieve implementation)

pub fn counting_fractions() -> u64 {
    const LIMIT: usize = 1_000_000;
    let mut phi = vec![0u64; LIMIT + 1];
    for i in 0..=LIMIT {
        phi[i] = i as u64;
    }
    for i in 2..=LIMIT {
        if phi[i] == i as u64 {
            let mut j = i;
            while j <= LIMIT {
                phi[j] = phi[j] / i as u64 * (i as u64 - 1);
                j += i;
            }
        }
    }
    let mut sum = 0u64;
    for i in 2..=LIMIT {
        sum += phi[i];
    }
    sum
}

View on GitHub

O(N log log N) time, O(N) space (linear sieve for totient function)

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

Problem #72 is taken from Project Euler and licensed under CC BY-NC-SA 4.0.