QUICK COMPUTATION OF THE PARITY OF ∏(x)

QUICK COMPUTATION OF THE PARITY OF ∏(x) By H. LIFCHITZ March 1998

Let ∏(x) = Number of prime numbers below or equal to x. |x|=integer part of x, and Ω(x) the number of prime divisors of x (with repetition). Ω(x) is additive, Ω(1) = Ω(0) = 0, Ω(p) = 1 and Ω(x.y) = Ω(x) + Ω(y)

Ω(x!) = ∑_{P_{i}≤x} |\frac{x}{P_{i}} | + ∑_{P_{i}≤x^{1/2}} |\frac{x}{P_{i}^{2}} | + ∑_{P_{i}≤x^{1/3}} |\frac{x}{P_{i}^{3}} | + ⋯ (1)

Indeed x! = 2^{|^{\frac{x}{2}}|+|\frac{x}{2^{2}} |+···} .3^{|^{\frac{x}{3}}|+|\frac{x}{3^{2}} |+···} .5^{|^{\frac{x}{5}}|+|\frac{x}{5^{2}} |+···} ⋯, therefore Ω(x!) = |\frac{x}{2} | + |\frac{x}{2^{2}} | + |\frac{x}{2^{3}} | + ⋯

+ |\frac{x}{3} | + |\frac{x}{3^{2}} | + |\frac{x}{3^{3}} | + ⋯

⋮ ⋮ ⋮

Summing vertically we obtain (1)

∑_{P_{i}≤x^{1/a}} |\frac{x}{P_{i}^{a}} | = ∑_{i=1}^{i=|\frac{x}{2^{a}} |} ∏ [(\frac{x}{i})^{1/a}] (2)

Indeed |\frac{x}{P_{i}^{a}} | = 1 when 1 ≤ \frac{x}{P_{i}^{a}} < 2 or \frac{x}{2} < P_{i}^{a} ≤ x or (\frac{x}{2})^{1/a} < P_{i} ≤ x^{1/a}

H. LIFCHITZ  1/ 4  03/98

QUICK COMPUTATION OF THE PARITY OF ∏(x)

Therefore ∑_{P_{i}≤x^{1/a}} |\frac{x}{P_{i}^{a}} | = ∑_{P_{i}≤(\frac{x}{2})^{1/a}} |\frac{x}{P_{i}^{a}} | + ∏ [x^{1/a}] − ∏ [(\frac{x}{2})^{1/a}]

afterwards ∑_{P_{i}≤x^{1/a}} |\frac{x}{P_{i}^{a}} | = ∑_{P_{i}≤(\frac{x}{3})^{1/a}} |\frac{x}{P_{i}^{a}} | + ∏ [x^{1/a}] − ∏ [(\frac{x}{2})^{1/a}] − 2 ∏ [(\frac{x}{3})^{1/a}]

and comes (2) continuing the process.

Let Ψ_{Ω}(x) = ∑_{i=1}^{i=|log_{2}n|} ∏ (x^{1/i}) (3)

By moebius inversion we have ∏(x) = ∑_{i=1}^{i=|log_{2}n|}μ(i)Ψ_{Ω} (x^{1/i}) (4) Then we have ∑_{i≤x}Ψ_{Ω} (\frac{x}{i}) = Ω(x!) (5)

because ∑_{i≤x}Ψ_{Ω} (\frac{x}{i}) = ∑_{P_{i}≤x} |\frac{x}{P_{i}} | + ∑_{P_{i}≤|x^{1/2}|} |\frac{x}{P_{i}^{2}} | + ∑_{P_{i}≤|x^{1/3}|} |\frac{x}{P_{i}^{3}} | + ⋯

Inverting (5) comes Ψ_{Ω}(x) = ∑_{i≤x}μ(i)Ω [(\frac{x}{i})!] (6) Expanding the right part of (6) we find :

Ψ_{Ω}(x) = ∑_{P_{i}≤x} |\frac{x}{P_{i}} |−2∗ ∑_{P_{i}<P_{j}≤x} |\frac{x}{P_{i}.P_{j}} |+3∗ ∑_{P_{i}<P_{j}<P_{k}≤x} |\frac{x}{P_{i}.P_{j}.P_{k}} |−4∗ ∑_{P_{i}<P_{j}<P_{k}<P_{l}≤x} |\frac{x}{P_{i}.P_{j}.P_{k}.P_{l}} |+⋯

Let A_{1}(x) = ∑_{P_{i}≤x} |\frac{x}{P_{i}} | , A_{2}(x) = ∑_{P_{i}<P_{j}≤x} |\frac{x}{P_{i}.P_{j}} | , A_{3}(x) = ∑_{P_{i}<P_{j}<P_{k}≤x} |\frac{x}{P_{i}.P_{j}.P_{k}} | , etc ⋯

Then Ψ_{Ω}(x) = A_{1}(x) − 2.A_{2}(x) + 3.A_{3}(x) − 4.A_{4}(x) + ⋯ (7)

But ∑_{i≤x}μ(i) |\frac{x}{i}| = 1

Also let x − 1 = A_{1}(x) − A_{2}(x) + A_{3}(x) − A_{4}(x) + ⋯ (8)

(7)-(8) result in Ψ_{Ω}(x) = x − 1 − A_{2}(x) + 2.A_{3}(x) − 3.A_{4}(x) + 4.A_{5}(x) − ⋯ (9)

We note that Ψ_{Ω}(x) = x − 1 for x < 6

So we have Ψ_{Ω}(x) ≡ x − 1 − A_{2}(x) − A_{4}(x) − A_{6}(x) − ⋯ [2] (10)

QUICK COMPUTATION OF THE PARITY OF ∏(x)

But ∑_{i≤x}Q (\frac{x}{i}) = 2(A_{2}(x) + A_{4}(x) + A_{6}(x) + ⋯) + 2x − 1 (11)

with Q(x) number of ”squarefree” ≤ x Indeed let ∏_{k}(x) = number of ”squarefree”≤ x having k prime factors, we have:

A_{1}(x) = ∑_{i≤|\frac{x}{2}|} ∏ (\frac{x}{i}) , A_{2}(x) = ∑_{i≤|\frac{x}{6}|} ∏_{2} (\frac{x}{i}) , A_{3}(x) = ∑_{i≤|\frac{x}{30}|} ∏_{3} (\frac{x}{i}) , etc ⋯

and A_{1}(x) + A_{2}(x) + A_{3}(x) + A_{4}(x) + ⋯ = ∑_{i≤|\frac{x}{2}|} ∏ (\frac{x}{i})+ ∑_{i≤|\frac{x}{6}|} ∏_{2} (\frac{x}{i})+ ∑_{i≤|\frac{x}{30}|} ∏_{3} (\frac{x}{i}) + ⋯

But Q(x) = 1 + ∏(x) + ∏_{2}(x) + ∏_{3}(x) + ∏_{4}(x) + ⋯

So A_{1}(x) + A_{2}(x) + A_{3}(x) + A_{4}(x) + ⋯ = ∑_{i≤x}Q (\frac{x}{i}) − x (12)

Let SQ(x) = ∑_{i≤x}Q (\frac{x}{i})

(8) and (12) result in 2(A_{2}(x) + A_{4}(x) + A_{6}(x) + A_{8}(x) + ⋯) = SQ(x) − 2x + 1, which proves (11)

and also SQ(x) = ∑_{i≤x}Q (\frac{x}{i}) ≡ 1 [2] ∀x (13)

(10) et (11) result in Ψ_{Ω}(x) ≡ \frac{SQ(x)−1}{2} [2] (14) Let F 1(x)=∑_{i≤x} |\frac{x}{i}| , it is easy to show that F 1(x)=2 ∑_{i=1}^{i=|\sqrt{x}|} |\frac{x}{i}| − |\sqrt{x}|^{2}

Let F 1r(x) = ∑_{i≤|\sqrt{x}|} |\frac{x}{i}| , so we have F 1(x) = 2.F 1r(x)−|\sqrt{x}|^{2} and F 1(x) ≡ |\sqrt{x}| [2] (15)

But F 1(x) = ∑_{i≤|\sqrt{x}|}SQ (\frac{x}{i^{2}} ) (16) and by moebius inversion SQ(x) = ∑_{i≤|\sqrt{x}|}μ(i).F 1 (\frac{x}{i^{2}} ) (17)

So SQ(x) = ∑_{i≤|\sqrt{x}|}μ(i) [2.F 1r (\frac{x}{i^{2}} ) − |\sqrt{\frac{x}{i^{2}}} |^{2}] = 2 ∑_{i≤|\sqrt{x}|}μ(i).F 1r (\frac{x}{i^{2}} ) − ∑_{i≤|\sqrt{x}|}μ(i). |\frac{\sqrt{x}}{i}|^{2}

Let SQ_{1}(x) = \frac{SQ(x)−1}{2} = ∑_{i≤|\sqrt{x}|}μ(i).F 1r (\frac{x}{i^{2}} ) − (\frac{∑_{i≤|\sqrt{x}|}μ(i) |\frac{\sqrt{x}}{i}|^{2} + 1}{2}) (18)

QUICK COMPUTATION OF THE PARITY OF ∏(x)

Let SR(x) = ∑_{i≤|\sqrt{x}|}μ(i) |\frac{\sqrt{x}}{i}|^{2}

|\frac{\sqrt{x}}{i} | = 1 for \frac{\sqrt{x}}{2} < i ≤ \sqrt{x} , so SR(x) = ∑_{i≤| \frac{\sqrt{x}}{2} |}μ(i) |\frac{\sqrt{x}}{i}|^{2} + ∑_{i=| \frac{\sqrt{x}}{2} |+1}^{i=|\sqrt{x}|}μ(i)

|\frac{\sqrt{x}}{i} | = 2 for \frac{\sqrt{x}}{3} < i ≤ \frac{\sqrt{x}}{2} , so SR(x) = ∑_{i≤| \frac{\sqrt{x}}{3} |}μ(i) |\frac{\sqrt{x}}{i}|^{2} + 4 ∑_{i=| \frac{\sqrt{x}}{3} |+1}^{i=| \frac{\sqrt{x}}{2} |}μ(i) + ∑_{i=| \frac{\sqrt{x}}{2} |+1}^{i=|\sqrt{x}|}μ(i)

Continuing the process comes SR(x) = ∑_{i=1}^{i=|\sqrt{x}|}i^{2} ∑_{j=| \frac{\sqrt{x}}{i+1} |+1}^{j=| \frac{\sqrt{x}}{i} |}μ(j)

Seeing that x^{2} ≡ 0[4] for even x and x^{2} ≡ 1[4] for odd x

we have SR(x) ≡ ∑_{i odd≤|\sqrt{x}|} ∑_{j=| \frac{\sqrt{x}}{i+1} |+1}^{j=| \frac{\sqrt{x}}{i} |}μ(j) [4]

But ∑_{i=a+1}^{i=b}μ(i) = M(b) − M(a) with M(x) Moebius summatory function So SR(x) ≡ M (\sqrt{x}) − M (\frac{\sqrt{x}}{2}) + M (\frac{\sqrt{x}}{3}) − M (\frac{\sqrt{x}}{4}) + ⋯ [4] But M(x) − M (\frac{x}{2}) + M (\frac{x}{3}) − M (\frac{x}{4}) + ⋯ =−1 property of M(x) for x ≥ 2

So SR(x) = ∑_{i≤\sqrt{x}}μ(i) |\frac{\sqrt{x}}{i}| ≡ −1[4] for x ≥ 4

And (18) results in SQ_{1}(x) ≡ ∑_{i≤|\sqrt{x}|}μ(i)F 1r (\frac{x}{i^{2}} ) [2] (19)

So Ψ_{Ω}(x) ≡ SQ_{1}(x)[2] (20)

And finally with (4)  ∏ (x) ≡ ∑_{i=1}^{i=|log_{2}x|}μ(i)SQ_{1}(x^{1/i})[2]  (21)

This expression allows to compute the parity of ∏(x) with a complexity in O (x^{1/2} ∗ logx) and with a storage space in O(1).

H. LIFCHITZ  4/ 4  03/98