Coprime Companions
MediumMath & Geometry
Problem
Two meshed gears with n and k teeth return to their starting alignment after lcm(n, k) teeth have passed, and that is the longest possible cycle, n · k, exactly when gcd(n, k) = 1. For a gear with n teeth, count the companion sizes k with 1 ≤ k ≤ n that give the longest cycle.
In other words, return how many integers in [1, n] are coprime with n.
Example 1
- Input:
- n = 9
- Output:
- 6
1, 2, 4, 5, 7 and 8 share no factor with 9.
Example 2
- Input:
- n = 1
- Output:
- 1
gcd(1, 1) = 1.
Example 3
- Input:
- n = 36
- Output:
- 12
Constraints
- 1 ≤ n ≤ 10^12
Hint
Show the first hint
Checking gcd for each k up to 10^12 is too slow. The count only depends on which primes divide n.
Walkthrough
How to approach it
01Clarify before coding
- Is k = n counted? Only when n = 1, since gcd(n, n) = n.
- How large is n? Up to 10^12, so √n is 10^6: trial division is affordable, a sieve up to n is not.
- Is the result guaranteed to fit? Yes, it is at most n.
02Brute force
For each k from 1 to n compute gcd(n, k) and count the ones equal to 1.
Cost: O(n log n): 10^12 gcd calls is far beyond any time limit.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.