Counting a condition indirectly
Given positive integers bounded by , how many unordered pairs of distinct indices have ? Repeated values are allowed; different indices still form a pair. Testing every pair is direct, but a divisor count can reuse information across many pairs.
Definition 6.1.1
(Möbius function)
The Möbius function is defined on positive integers by ; if a prime square divides , then ; otherwise, if is the product of distinct primes, then .
The results below assume unique prime factorization.
The divisor indicator
Theorem 6.1.2
(Möbius sum over divisors)
For a positive integer ,
Consequently, for positive integers , .
Proof
(Divisors correspond to subsets of the prime factors)
If , the only divisor is one and . Otherwise, let its distinct prime factors be , with . Divisors containing a square contribute zero. Each remaining divisor is a product of distinct primes among , so it corresponds to a subset of these primes and contributes . Hence the sum is
For the consequence, the common divisors of and are exactly the divisors of . Applying the identity to gives when and otherwise.
Proof X-ray
Why the sum is one only at g equal to one
The one non-routine move is to discard every divisor that contains a square and to index the rest by subsets of the primes of ; that step uses unique factorization. The binomial expansion is zero only when . With the same expression is the empty product , which is exactly the case , so the two cases of the identity are one computation. The weight on non-squarefree divisors is essential: without it the sum over all divisors of no longer cancels.
Let count indices for which .
Theorem 6.1.3
(Coprime pairs as a Möbius sum)
With and all ,
Proof
(Interchanging two finite sums)
Insert the divisor indicator for each pair and swap the order of summation:
The set counted on the right consists of pairs of distinct indices chosen from the indices divisible by , so its size is . A divisor of some is at most , and for we have ; so the sum may stop at .
The binomial coefficient counts pairs of indices, not distinct numerical values. For it is zero. Negative terms are inclusion–exclusion corrections; the final count is nonnegative.
Counterexample mode
A squared prime changes the weight
It is wrong to give every divisor a sign using only its total number of prime factors. For , the correct values are , and . Assigning would make their sum instead of and falsely label gcd as one.
A small trace
Worked example 6.1.4
(Five entries)
For , we have , (the entries ) and (the entries ). For every other , at most one entry is divisible by . Thus the formula gives
The four index pairs correspond to the values , , and . A direct check of all ten pairs confirms this: the other six have gcd .
Worked example 6.1.5
(Equal entries have no coprime pair)
Let . Then , and for . The formula gives , as it must: every pair has gcd . The repeated values are counted by index, and the two terms cancel exactly.
Computing the counts
Let be the number of inputs equal to . For each , compute by summing . The Möbius values can also be obtained from the divisor identity, without factoring every input:
mu[1] = 1; mu[2..M] = 0
for d = 1..M:
for multiple = 2d, 3d, ... while multiple <= M:
mu[multiple] -= mu[d]
Proposition 6.1.6
(The sieve computes the Möbius values)
When the outer loop reaches index , ; consequently, at the end, for all .
Proof
(Strong induction on the index)
For nothing has been subtracted, and . Let and assume that when the loop reaches each . The entry starts at and is decreased by exactly once for each with and , that is, for each proper divisor of . Hence at index it equals . By the divisor identity with , , so this equals . Later iterations only change entries beyond their own index.
Both multiple loops visit at most positions. Including input frequencies and the final sum gives time and auxiliary space, assuming exact constant-time integer arithmetic. The count can exceed a fixed-width integer's range, so an implementation must choose an adequate representation. This bound depends on the maximum value , not only the number of inputs.
Worked example 6.1.7
(The sieve for M equal to 6)
Start with for indices . Index subtracts from indices : . Index subtracts from indices and : . Index subtracts from index : . Indices have no multiples at most beyond themselves. The result agrees with the definition; in particular and .
Common mistake
(Counting distinct values instead of indices)
For there are two coprime index pairs, namely and , although only one pair of distinct values is coprime. The formula gives , which counts indices. Deduplicating the input first answers a different question.
Common mistake
(Reading the cost as a function of the input length only)
The sieve allocates and scans tables of length . For and the input is tiny, but the range makes the table size, and so the running time and memory, large.
Exercises with solutions
Quick check
(What is ?)
Factor .
Solution · Answer
, because divides .
Quick check
(What is ?)
Is squarefree?
Solution · Answer
, since is a product of two distinct primes.
Quick check
(For the two entries , how many coprime index pairs are there?)
Use the index-pair count, not distinct values.
Solution · Answer
One: the only pair is and its gcd is one. The formula agrees: , so the sum is .
Quick check
(Why is the stated sieve not necessarily efficient for a tiny input containing a huge value?)
Which parameter controls the table size?
Solution · Answer
Its time and auxiliary memory depend on ; a small alone does not make the allocated range small.
Quick check
(Use the formula to count coprime index pairs in .)
Compute and , and check whether .
Solution · Answer
, (the entries ), and . The count is . Directly: and , so two pairs.