Sită Legendre

În matematică , sita lui Legendre este cea mai simplă metodă din teoria sitelor moderne. Se aplică conceptul de Eratostene sită pentru a găsi limite inferioare și superioare pentru estimarea cantității de PRIMES într - un anumit interval de numere întregi. Deoarece este o simplă extensie a ideii de Eratostene, uneori este denumită sită Legendre-Eratostene .

Identitatea lui Legendre

Ideea de bază a metodei este exprimată prin această identitate, uneori numită identitatea lui Legendre :

S(A,P)=\sum _{a\in A}\sum _{d|a;d|P}\mu (d)=\sum _{d|P}\mu (d)|A_{d}|

{\ displaystyle S (A, P) = \ sum _ {a \ in A} \ sum _ {d | a; d | P} \ mu (d) = \ sum _ {d | P} \ mu (d) | A_ {d} |}

{\ displaystyle S (A, P) = \ sum _ {a \ in A} \ sum _ {d | a; d | P} \ mu (d) = \ sum _ {d | P} \ mu (d) | A_ {d} |}

unde este $LA$ ${\ displaystyle A}$ $LA$ este un interval de numere întregi, $P.$ ${\ displaystyle P}$ $P.$ este produsul numerelor prime distincte, $\mu$ ${\ displaystyle \ mu}$ $\ mu$ este funcția Möbius , $A_{d}$ ${\ displaystyle A_ {d}}$ ${\ displaystyle A_ {d}}$ este mulțimea numerelor întregi $LA$ ${\ displaystyle A}$ $LA$ divizibil cu $d$ ${\ displaystyle d}$ $d$ , Și $S(A,P)$ ${\ displaystyle S (A, P)}$ ${\ displaystyle S (A, P)}$ este definit ca:

S(A,P)=|\{n:n\in A,(n,P)=1\}|,

{\ displaystyle S (A, P) = | \ {n: n \ în A, (n, P) = 1 \} |,}

{\ displaystyle S (A, P) = | \ {n: n \ în A, (n, P) = 1 \} |,}

adică numărul de numere întregi din $LA$ ${\ displaystyle A}$ $LA$ care nu au factori comuni cu $P.$ ${\ displaystyle P}$ $P.$ .

În cele mai multe cazuri $LA$ ${\ displaystyle A}$ $LA$ toate sunt numere întregi mai mici sau egale cu un anumit număr $X$ ${\ displaystyle X}$ $X$ , $P.$ ${\ displaystyle P}$ $P.$ este produsul tuturor primilor mai mici sau egali cu un număr întreg $z<X$ ${\ displaystyle z <X}$ ${\ displaystyle z <X}$ , deci identitatea lui Legendre devine:

S(A,P)

{\ displaystyle S (A, P)}

{\ displaystyle S (A, P)}

=\sum _{d|P}\mu (d)\left\lfloor {\frac {X}{p_{1}}}\right\rfloor

{\ displaystyle = \ sum _ {d | P} \ mu (d) \ left \ lfloor {\ frac {X} {p_ {1}}} \ right \ rfloor}

{\ displaystyle = \ sum _ {d | P} \ mu (d) \ left \ lfloor {\ frac {X} {p_ {1}}} \ right \ rfloor}

=[X]-\sum _{p_{1}<z}\left\lfloor {\frac {X}{p_{1}}}\right\rfloor +\sum _{p_{1}<p_{2}<z}\left\lfloor {\frac {X}{p_{1}p_{2}}}\right\rfloor -\sum _{p_{1}<p_{2}<p_{3}<z}\left\lfloor {\frac {X}{p_{1}p_{2}p_{3}}}\right\rfloor +\cdots

{\ displaystyle = [X] - \ sum _ {p_ {1} <z} \ left \ lfloor {\ frac {X} {p_ {1}}} \ right \ rfloor + \ sum _ {p_ {1} < p_ {2} <z} \ left \ lfloor {\ frac {X} {p_ {1} p_ {2}}} \ right \ rfloor - \ sum _ {p_ {1} <p_ {2} <p_ {3 } <z} \ left \ lfloor {\ frac {X} {p_ {1} p_ {2} p_ {3}}} \ right \ rfloor + \ cdots}

{\ displaystyle = [X] - \ sum _ {p_ {1} <z} \ left \ lfloor {\ frac {X} {p_ {1}}} \ right \ rfloor + \ sum _ {p_ {1} < p_ {2} <z} \ left \ lfloor {\ frac {X} {p_ {1} p_ {2}}} \ right \ rfloor - \ sum _ {p_ {1} <p_ {2} <p_ {3 } <z} \ left \ lfloor {\ frac {X} {p_ {1} p_ {2} p_ {3}}} \ right \ rfloor + \ cdots}

(unde este $\lfloor x\rfloor$ ${\ displaystyle \ lfloor x \ rfloor}$ $\ lfloor x \ rfloor$ denotă partea întreagă a $X$ ${\ displaystyle x}$ $X$ ). În acest exemplu, faptul că identitatea lui Legendre este derivată din sita lui Eratostene este clar: primul termen este numărul de numere întregi mai mic decât $X$ ${\ displaystyle X}$ $X$ , al doilea elimină multiplii tuturor primelor, al treilea recuperează produsele celor două prime (care au fost aruncate din greșeală) și așa mai departe până când toate $2^{\pi (z)}$ ${\ displaystyle 2 ^ {\ pi (z)}}$ ${\ displaystyle 2 ^ {\ pi (z)}}$ (unde este $\pi (z)$ ${\ displaystyle \ pi (z)}$ ${\ displaystyle \ pi (z)}$ denotă numărul primilor mai mic decât $z$ ${\ displaystyle z}$ $z$ ) au fost acoperite combinații de primii.

O singura data $S(A,P)$ ${\ displaystyle S (A, P)}$ ${\ displaystyle S (A, P)}$ a fost calculat pentru acest caz particular, poate fi folosit pentru a obține o limită superioară pentru $\pi (X)$ ${\ displaystyle \ pi (X)}$ ${\ displaystyle \ pi (X)}$ folosind expresia

S(A,P)\geq \pi (X)-\pi (z)-1,

{\ displaystyle S (A, P) \ geq \ pi (X) - \ pi (z) -1,}

{\ displaystyle S (A, P) \ geq \ pi (X) - \ pi (z) -1,}

care rezultă imediat din definiția lui $S(A,P)$ ${\ displaystyle S (A, P)}$ ${\ displaystyle S (A, P)}$ .

Probleme

Sita lui Legendre nu se ocupă foarte eficient de părțile fracționare ale termenilor, care se acumulează formând o eroare destul de mare; aceasta implică faptul că site-ul stabilește limite foarte slabe în majoritatea cazurilor. Din acest motiv, a fost înlocuit acum cu alte tehnici precum sita Brun și sita Selberg și nu este folosită aproape niciodată în practică. Cu toate acestea, chiar și cele mai puternice site sunt întotdeauna bazate pe aceeași idee, deci este util să înțelegem cum funcționează sita Legendre înainte de a studia celelalte.

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică