Sundaramovo sito

U matematici, Sundaramovo sito je jednostavan deterministički algoritam za pronalaženje svih prostih brojeve do određenog celog broja. Otkrio ga je indijski matematičar S. P. Sundaram 1934.godine.^[1]^[2]

Algoritam

Sundaramobo sito: koraci algoritma za proste brojeve ispod 202 (optimalno).

Počinje sa listom celih brojeva od 1 do n. Iz ove liste, uklanja sve brojeve u obliku i + j + 2ij gde:

$i,j\in \mathbb {N} ,\ 1\leq i\leq j$
$i+j+2ij\leq n$

Preostali brojevi se udvostručuju, povećavaju se, dajući listu neparnim brojevima (tj prostim, svi prosti brojevi osim 2) ispod 2n + 2.

Sito Sundaram sita od složenih brojeva radi kao Eratostenovo sito, ali čak se brojevi ne smatraju; rad "precrtava" i više 2 vrši poslednji korak dvostrukog-kraja-priraštaja. Kad god bi se Eratostenova metoda mogla precrtati bez k različitih prostih brojeva 2i+1, Sundaramova metoda precrtava i + j(2i+1) for $1\leq j\leq \lfloor k/2\rfloor$ .

Ispravnosti

Ako počnemo sa celim brojevima od 1 do n, konačna lista sadrži samo neparne cele brojeve od 3 do 2n + 1. Iz ovog konačnog spiska, neki neparni celi brojevi su isključeni: moramo pokazati upravo to su složeni neparni celi brojevi manji od 2n + 2.

Pustiti q da bude neparan ceo broj od 2k + 1. Tada, q je isključen ako i samo ako k je od i + j + 2ij, tada je q = 2(i + j + 2ij) + 1. Onda imamo:

q = 2(i + j + 2ij) + 1

= 2i + 2j + 4ij + 1

= (2i + 1)(2j + 1).

Dakle, neparan ceo broj je isključen iz konačne liste ako i samo ako ima razlaganja oblika (2i + 1)(2j + 1) — što će reći, ako ima netrivijalni neparni faktor. Stoga lista mora činiti upravo skup neparnih prostih brojeva manjih ili jednakih od 2n + 2.

Vidi još

Reference

^ V. Ramaswami Aiyar (1934). „Sundaram's Sieve for Prime Numbers”. The Mathematics Student. 2 (2): 73. ISSN 0025-5742.
^ G. (1941). „Curiosa 81. A New Sieve for Prime Numbers”. Scripta Mathematica. 8 (3): 164.

Literatura

Ogilvy, C. Stanley; John T. Anderson (1988). Excursions in Number Theory. Dover Publications, 1988 (reprint from Oxford University Press, 1966). str. 98—100,158. ISBN 978-0-486-25778-5.
Honsberger, Ross (1970). Ingenuity in Mathematics. New Mathematical Library #23. Mathematical Association of America. str. 75. ISBN 978-0-394-70923-9.
Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung. MSB Nr. 78. Urania Verlag. str. 200. (translation of Russian book Kordemskiй, Boris Anastasьevič (1958). Matematičeskaя smekalka. M.: GIFML. Arhivirano iz originala 16. 10. 2019. g. Pristupljeno 14. 11. 2015. )
A new "sieve" for primes^{[mrtva veza]}, an excerpt from
Movshovitz-Hadar, N. (1988). „Stimulating Presentations of Theorems Followed by Responsive Proofs”. For the Learning of Mathematics. 8 (2): 12—19.
Ferrando, Elisabetta (2005). „Abductive processes in conjecturing and proving” (PDF). Ph.D. theses. Purdue University. str. 70—72. Arhivirano iz originala (PDF) 07. 05. 2016. g. Pristupljeno 14. 11. 2015.
Baxter, Andrew. „Sundaram’s Sieve”. Topics from the History of Cryptography. MU Department of Mathematics. Arhivirano iz originala 12. 08. 2011. g. Pristupljeno 14. 11. 2015. External link in |work= (help)

Spoljašnje veze

A C99 implementation of the Sieve of Sundaram using bitarrays

[1] V. Ramaswami Aiyar (1934). „Sundaram's Sieve for Prime Numbers”. The Mathematics Student. 2 (2): 73. ISSN 0025-5742.

[2] G. (1941). „Curiosa 81. A New Sieve for Prime Numbers”. Scripta Mathematica. 8 (3): 164.

[1]

[2]