Member Avatar for mrnutty

You are given a number D, for which 0 < D < 1,000,000

Your task : is to find the number of irreducible fractions for a fraction of the
sequence, (D-1)/D , (D-2)/D ... 1/D.

For example, let D = 12; Then listing all fraction increments of 1/D we get :
1/12 , 2/12 , 3/12 , 4/12 , 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12.

From the list of fractions above, the only fraction not reducible are: 1/12, 3/12, 5/12,
7/12, 9/12, 11/12. While the rest are reducible, for example 2/12 reduces to 1/12, and
10/12 reduces to 5/6.


Problem: Given a denominator D, for which, 0 < D < 1,000,000. Find the number
of irreducible fractions starting from the fraction 1/D to (D-1)/D, while incrementing
the series by 1/D.

  • 2 Contributors
  • 2 Replies
  • 309 Views
  • 9 Hours Discussion Span
  • Latest Post Latest Post by mrnutty

Dani AI

Generated

Short answer: the count equals Euler's totient function phi(D) (for D > 1). As posed the problem and spotted reduction mistakes in the example, the general criterion is simple: k/D is irreducible iff gcd(k,D) = 1, so the number of irreducible fractions k/D with 1 <= k <= D-1 is the number of integers in that range coprime to D — i.e. phi(D). (For D = 1 the sequence 1/D..(D-1)/D is empty, so return 0.)

Reason sketch: if g = gcd(k,D) > 1 then k/D reduces to (k/g)/(D/g), so not irreducible; if gcd(k,D) = 1 there is no nontrivial common factor, so k/D is already in lowest terms. Example: phi(12) = 4, so the irreducible fractions with denominator 12 between 0 and 1 are 1/12, 5/12, 7/12, 11/12.

Efficient computation:

  • Single D: factor D in O(sqrt(D)). Start result = D; for each distinct prime p dividing D do result -= result / p; final result is phi(D).
  • Many queries up to a known max (<= 1e6): precompute phi for all n with a sieve (modified Eratosthenes) in O(N log log N) or linear time.

C++ (single-D, fast enough for D < 1e6):

#include <bits/stdc++.h>
using namespace std;

long long phi(long long n) {
    if (n <= 1) return 0; // problem counts 1..n-1, so empty for n==1
    long long res = n, t = n;
    for (long long p = 2; p * p <= t; ++p) {
        if (t % p == 0) {
            while (t % p == 0) t /= p;
            res -= res / p;
        }
    }
    if (t > 1) res -= res / t;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long D;
    if (!(cin >> D)) return 0;
    cout << phi(D) << '\n';
    return 0;
}

Caution: for many queries prefer a phi-sieve; for single queries the factor method is trivial and safe for the problem bounds.

Recommended Answers

All 2 Replies

Member Avatar for sfuo

Doesn't 3/12 reduce to 1/4 and 9/12 to 3/4.

Also 2/12 reduces to 1/6 not 1/12 (typo I think).

Member Avatar for mrnutty

Doesn't 3/12 reduce to 1/4 and 9/12 to 3/4.

Also 2/12 reduces to 1/6 not 1/12 (typo I think).

Oops, your completely right. Thanks. Was thinking that, but typed something else.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.