Notes on Möbius function

To solve ProjectEuler problems, we need some basic knowledge about Möbius function.

1. Definition: mu(n).



2. sum_{d|n} mu(d) = [n = 1].
Let n = gcd(a, b). sum_{d|gcd(a, b)} mu(d) = sum_{d|a, d|b} mu(d) = [gcd(a, b) = 1]



3. Mertens function: M(n) = sum_{k ≤ n} mu(k).



4. M(n) = 1 - sum_{d ≥ 2} M(n/d).
sum_{d ≤ n} M(n/d) = sum_{d ≤ n} sum_{k ≤ n/d} mu(k) = sum_{d ≤ n} sum_{k|d} mu(k) = sum_{d ≤ n} [d = 1] = 1

Reference: Deléglise, M., Rivat, J.: Computing the summation of the Möbius function. Experimental Mathematics 5(4), 291–295 (1996). [https://projecteuclid.org/download/pdf_1/euclid.em/1047565447]



5. Let S(n) denote the number of square-free positive integers ≤ n.
S(n) = sum_{d ≤ sqrt(n)} mu(d) floor(n/d^2).

Besides, let C(n) be the number of cube-free positive integers ≤ n.
C(n) = sum_{d ≤ n^{1/3}} mu(d) floor(n/d^3).

Reference: Jakub Pawlewicz, Counting square-free numbers (2011), arXiv:1107.4890. [http://arxiv.org/pdf/1107.4890v1.pdf]



6. Let P(n) be the number of primitive Pythagorean triples with a < b < c ≤ n.
Let a = x^2 − y^2, b = 2xy, c = x^2 + y^2 with x, y coprime (positive) integers of opposite parity.

Hence, P(n) = { (x, y) in R(n) : gcd(x, y) = 1, opposite parity } where R(n) = { (x, y) : x^2 + y^2 ≤ n, 0 < x < y }.
Also we let Q(n) = { (x, y) in R(n) : gcd(x, y) = 1 }.

If (x, y) in Q(n), then (1) x, y opposite parity (2) x, y are odd.  In case (1), (x, y) in P(n).  In case (2), gcd(a, b, c) = gcd(x^2 - y^2, 2xy, x^2 + y^2) = gcd(2x^2, 2xy, 2y^2) = 2 gcd(x^2, xy, y^2) = 2.  So (x, y) in P(n/2).  Hence Q(n) = P(n) + P(n/2).

Therefore, P(n) = sum_{k ≥ 0}(-1)^k Q(n/2^k). (no more opposite parity).

Now we want to represent Q(n) in terms of R(n): Q(n) = sum_{1 ≤ k ≤ Floor[Sqrt[n]]} mu(k) R(n/k^2).

Reference: Pythagorean triangles with legs less than n [http://ac.els-cdn.com/S0377042701004964/1-s2.0-S0377042701004964-main.pdf?_tid=2a2d0446-ac6b-11e5-a15e-00000aab0f27&acdnat=1451201377_754b996c3258324dc6694d8b83ba6b6f]