CALCUL RAPIDE DE LA PARITE DE ∏(x)

CALCUL RAPIDE DE LA PARITE DE ∏(x) Par H. LIFCHITZ Mars 1998

Soit ∏(x) = Nombre de nombres premiers inférieurs ou égaux à x. |x|=partie entière de x, et Ω(x) le nombre de diviseurs premiers de x (avec répétition). Ω(x) est additive, Ω(1) = Ω(0) = 0, Ω(p) = 1 et Ω(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)

En effet 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}} |+···} ⋯, donc Ω(x!) = |\frac{x}{2} | + |\frac{x}{2^{2}} | + |\frac{x}{2^{3}} | + ⋯

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

⋮ ⋮ ⋮

En sommant verticalement on obtient (1)

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

En effet |\frac{x}{P_{i}^{a}} | = 1 quand 1 ≤ \frac{x}{P_{i}^{a}} < 2 ou \frac{x}{2} < P_{i}^{a} ≤ x ou (\frac{x}{2})^{1/a} < P_{i} ≤ x^{1/a}

H. LIFCHITZ  1/ 4  03/98

CALCUL RAPIDE DE LA PARITE DE ∏(x)

Donc ∑_{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}]

puis ∑_{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}]

et il vient (2) en continuant le processus.

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

Par inversion de moëbius on a ∏(x) = ∑_{i=1}^{i=|log_{2}n|}μ(i)Ψ_{Ω} (x^{1/i}) (4) On a alors ∑_{i≤x}Ψ_{Ω} (\frac{x}{i}) = Ω(x!) (5)

puisque ∑_{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}} | + ⋯

En inversant (5) il vient Ψ_{Ω}(x) = ∑_{i≤x}μ(i)Ω [(\frac{x}{i})!] (6) En développant la partie droite de (6) on trouve :

Ψ_{Ω}(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}} |+⋯

Posons 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 ⋯

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

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

Soit aussi x − 1 = A_{1}(x) − A_{2}(x) + A_{3}(x) − A_{4}(x) + ⋯ (8)

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

On notera que Ψ_{Ω}(x) = x − 1 pour x < 6

On a donc Ψ_{Ω}(x) ≡ x − 1 − A_{2}(x) − A_{4}(x) − A_{6}(x) − ⋯ [2] (10)

CALCUL RAPIDE DE LA PARITE DE ∏(x)

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

avec Q(x) nombre de ”squarefree” ≤ x En effet si l’on pose ∏_{k}(x) = nombre de ”squarefree”≤ x ayant k facteurs premiers, on a:

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 ⋯

et 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}) + ⋯

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

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

Si l’on pose SQ(x) = ∑_{i≤x}Q (\frac{x}{i})

(8) et (12) entrainent 2(A_{2}(x) + A_{4}(x) + A_{6}(x) + A_{8}(x) + ⋯) = SQ(x) − 2x + 1, ce qui démontre (11)

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

(10) et (11) entrainent Ψ_{Ω}(x) ≡ \frac{SQ(x)−1}{2} [2] (14) Soit F 1(x)=∑_{i≤x} |\frac{x}{i}| , il est facile de montrer que F 1(x)=2 ∑_{i=1}^{i=|\sqrt{x}|} |\frac{x}{i}| − |\sqrt{x}|^{2}

Appelons F 1r(x) = ∑_{i≤|\sqrt{x}|} |\frac{x}{i}| , on a donc F 1(x) = 2.F 1r(x)−|\sqrt{x}|^{2} et F 1(x) ≡ |\sqrt{x}| [2] (15)

Or F 1(x) = ∑_{i≤|\sqrt{x}|}SQ (\frac{x}{i^{2}} ) (16) et par inversion de moëbius SQ(x) = ∑_{i≤|\sqrt{x}|}μ(i).F 1 (\frac{x}{i^{2}} ) (17)

Donc 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}

Posons 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)

CALCUL RAPIDE DE LA PARITE DE ∏(x)

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

|\frac{\sqrt{x}}{i} | = 1 pour \frac{\sqrt{x}}{2} < i ≤ \sqrt{x} , donc 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 pour \frac{\sqrt{x}}{3} < i ≤ \frac{\sqrt{x}}{2} , donc 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)

En continuant le processus il vient SR(x) = ∑_{i=1}^{i=|\sqrt{x}|}i^{2} ∑_{j=| \frac{\sqrt{x}}{i+1} |+1}^{j=| \frac{\sqrt{x}}{i} |}μ(j) Comme x^{2} ≡ 0[4] pour x pair et x^{2} ≡ 1[4] pour x impair

On a donc SR(x) ≡ ∑_{i impair≤|\sqrt{x}|} ∑_{j=| \frac{\sqrt{x}}{i+1} |+1}^{j=| \frac{\sqrt{x}}{i} |}μ(j) [4]

Or ∑_{i=a+1}^{i=b}μ(i) = M(b) − M(a) avec M(x) fonction sommatoire de moëbius Donc SR(x) ≡ M (\sqrt{x}) − M (\frac{\sqrt{x}}{2}) + M (\frac{\sqrt{x}}{3}) − M (\frac{\sqrt{x}}{4}) + ⋯ [4] Or M(x) − M (\frac{x}{2}) + M (\frac{x}{3}) − M (\frac{x}{4}) + ⋯ =−1 propriété de M(x) pour x ≥ 2 Donc SR(x) = ∑_{i≤\sqrt{x}}μ(i) |\frac{\sqrt{x}}{i}| ≡ −1[4] pour x ≥ 4

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

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

Et finalement avec (4)  ∏ (x) ≡ ∑_{i=1}^{i=|log_{2}x|}μ(i)SQ_{1}(x^{1/i})[2]  (21)

Cette expression permet de calculer la parité de ∏(x) avec une complexité en O (x^{1/2} ∗ logx) et avec un espace de stockage en O(1).

H. LIFCHITZ  4/ 4  03/98