Solution
In this problem, we want to count the number of reduced fractions below a certain denominator. For example, if we’re working with \(d=8\), then reduced fractions are
Group these fractions by their denominator as follows:
and observe that the numerators are exactly those numbers relatively prime to the denominator in each case. For example \(1\) and \(5\) are the only relatively prime to \(6\) which are less than \(6\). This exactly Euler’s Totient function (which we also used in problem 69 and problem 70). Given an integer \(n\), the Totient function \(\phi(n)\) is the number of positive integers not exceeding \(n\) and are relatively prime to \(n\). Hence this problem reduces to calculating the Totient number. However, we need to calculate the Totient number not just \(8\) but rather we need to calculate it for all \(n\) less than \(8\).
In order to calculate \(\sum_{n=2}^{8}\varphi(n)\). We use a totient sieve. First, initialize a working array \(A\) by setting \(A[n]=n\) as follows
These are not yet the actual totient values. Each value is just a working counter that initially represents \(n\) candidates. We then process every prime \(p\). For each multiple \(m\) of \(p\), update the counter using
This removes the proportion \(1/p\) of the remaining candidates that are divisible by \(p\). So after processing the prime \(p = 2\), we will update \(A\) such that
After processing \(p=3\), we will get
After all primes up to 8 have been processed, the array contains the actual totient values:
Therefore, the number of positive proper reduced fractions with denominators at most 8 is
This is implemented in
unsigned long long countProperReducedFractions(unsigned int d) {
std::vector<unsigned long long> phi(d + 1);
// Initially phi[n] = n
std::iota(phi.begin(), phi.end(), 0);
// Totient sieve
for (unsigned int p = 2; p <= d; ++p) {
if (phi[p] == p) { // this is prime since it hasn't been touched yet
// since it's prime, we will erase it from all its multiples
for (unsigned int multiple = p; multiple <= d; multiple += p) {
phi[multiple] -= phi[multiple] / p;
}
}
}
unsigned long long count = 0;
for (unsigned int denominator = 2;
denominator <= d;
++denominator) {
count += phi[denominator];
}
return count;
}