Legendrové síto - Legendre sieve
![]() | tento článek potřebuje další citace pro ověření.Prosince 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
v matematika, Legendrové síto, pojmenoval podle Adrien-Marie Legendre, je nejjednodušší metoda v moderní teorie sít. Aplikuje koncept Síto Eratosthenes najít horní nebo dolní meze na počtu připraví v dané sadě celých čísel. Protože se jedná o jednoduché rozšíření Eratosthenes „Myšlenka, někdy se tomu říká Síto Legendre – Eratosthenes.[1]
Legendrova identita
Ústřední myšlenka metody je vyjádřena následující identitou, někdy nazývanou Legendární identita:
kde A je sada celých čísel, P je produktem různých prvočísel, je Möbiova funkce, a je množina celých čísel v A dělitelné d, a S (A, P) je definován jako:
tj. S(A, P) je počet čísel v A bez společných faktorů P.
Všimněte si, že v nejtypičtějším případě A je všechna celá čísla menší nebo rovna nějakému reálnému číslu X, P je součin všech prvočísel menších nebo rovných nějakému celému číslu z < X, a poté se identita Legendre stává:
(kde označuje funkce podlahy ). V tomto příkladu je skutečnost, že identita Legendre je odvozena od Eratosthenova síta, jasná: první člen je počet celých čísel níže X, druhý člen odstraní násobky všech prvočísel, třetí člen přidá zpět násobky dvou prvočísel (které byly chybně spočítány tím, že byly „dvakrát přeškrtnuty“) atd. (kde označuje počet prvočísel nížez) byly pokryty kombinace prvočísel.
Jednou S(A, P) byl vypočítán pro tento speciální případ, lze jej použít k vázání pomocí výrazu
který bezprostředně vyplývá z definiceS(A, P).
Omezení
Síto Legendre má problém s hromaděním dílčích částí výrazů do velké chyby, což znamená, že síto ve většině případů dává jen velmi slabé hranice. Z tohoto důvodu se v praxi téměř nikdy nepoužívá, protože byl nahrazen jinými technikami, jako je Brun síto a Selbergovo síto. Jelikož však tato silnější síta jsou rozšířením základních myšlenek síta Legendre, je užitečné nejprve pochopit, jak toto síto funguje.
Reference
- ^ Iwaniec, Henryk. Síto Eratosthenes – Legendre. Annali della Scuola Normale Superiore di Pisa - Classe di Scienze, Sér. 4, 4 č. 2 (1977), s. 257–268 MR 453676