En matemáticas , el tamiz de Sundaram es un algoritmo determinista simple para encontrar todos los números primos hasta un número entero especificado. Fue descubierto por el matemático indio SP Sundaram en 1934. [1] [2]
Algoritmo
Comience con una lista de los números enteros del 1 al n . De esta lista, elimine todos los números de la forma i + j + 2 ij donde:
Los números restantes se duplican y se incrementan en uno, dando una lista de los números primos impares (es decir, todos los primos excepto 2) por debajo de 2 n + 1 .
El tamiz de Sundaram tamiza los números compuestos tal como lo hace el tamiz de Eratóstenes , pero los números pares no se consideran; el trabajo de "tachar" los múltiplos de 2 se realiza mediante el paso final de doble e incremento. Siempre que el método de Eratóstenes tachara k diferentes múltiplos de un primo, El método de Sundaram tacha por .
Exactitud
Si empezamos con números enteros de 1 a N , la lista final contiene sólo números enteros impares de 3 a. De esta lista final, se han excluido algunos enteros impares; debemos mostrar que estos son precisamente los enteros impares compuestos menores que.
Sea q un número entero impar de la forma. Entonces, q se excluye si y solo si k tiene la forma, es decir . Entonces nosotros tenemos:
Entonces, un entero impar se excluye de la lista final si y solo si tiene una factorización de la forma - es decir, si tiene un factor impar no trivial. Por lo tanto, la lista debe estar compuesta exactamente por el conjunto de números primos impares menores o iguales que.
def sieve_of_Sundaram ( n ): "" "El tamiz de Sundaram es un algoritmo determinista simple para encontrar todos los números primos hasta un entero especificado." "" k = ( n - 2 ) // 2 integers_list = [ True ] * ( k + 1 ) para i en el rango ( 1 , k + 1 ): j = i while i + j + 2 * i * j <= k : integers_list [ i + j + 2 * i * j ] = False j + = 1 si n > 2 : print ( 2 , end = '' ) para i en el rango ( 1 , k + 1 ): if integers_list [ i ]: print ( 2 * i + 1 , end = '' )
Complejidad asintótica
La oscura pero comúnmente implementada versión Python del Sieve of Sundaram oculta la verdadera complejidad del algoritmo debido a las siguientes razones:
- El rango para la variable de bucle externo i es demasiado grande, lo que da como resultado un bucle redundante que no puede realizar ninguna selección de representación de números compuestos; el rango adecuado es para el índice de la matriz representar números impares menores que la raíz cuadrada del rango.
- El código no tiene en cuenta correctamente la indexación de las matrices de Python, que se basan en un índice cero, por lo que ignora los valores en la parte inferior y superior de la matriz; este es un problema menor, pero sirve para mostrar que el algoritmo detrás del código no se ha entendido claramente.
- El ciclo de selección interno (el ciclo j ) refleja exactamente la forma en que se formula el algoritmo, pero aparentemente sin darse cuenta de que la selección indexada comienza exactamente en el índice que representa el cuadrado del número impar base y que la indexación mediante la multiplicación se puede realizar con mucha más facilidad. expresado como una simple adición repetida del número base impar en todo el rango; de hecho, este método de agregar un valor constante en todo el rango de sacrificio es exactamente la forma en que generalmente se implementa el sacrificio del Tamiz de Eratóstenes.
El siguiente código de Python en el mismo estilo resuelve los tres problemas anteriores, además de convertir el código en una función de conteo principal que también muestra el número total de operaciones de selección de representación de selección selectiva compuesta:
importar matemáticas def sieve_of_Sundaram ( n ): "" "El tamiz de Sundaram es un algoritmo determinista simple para encontrar todos los números primos hasta un entero especificado." "" if n < 3 : if n < 2 : return 0 else : return 1 k = ( n - 3 ) // 2 + 1 ; integers_list = [ Verdadero ] * k ; ops = 0 for i in range ( 0 , ( int ( math . sqrt ( n )) - 3 ) // 2 + 1 ): # if integers_list [i]: # agregar esta condición la convierte en un SoE! p = 2 * i + 3 ; s = ( p * p - 3 ) // 2 # calcular el inicio de selección para j en el rango ( s , k , p ): integers_list [ j ] = False ; ops + = 1 print ( "Total de operaciones:" , ops , ";" , sep = '' ) count = 1 for i in range ( 0 , k ): if integers_list [ i ]: count + = 1 print ( "Encontrado " , count , " primos to " , n , ". " , sep = '' )
Tenga en cuenta la línea comentada que es todo lo que se necesita para convertir el Tamiz de Sundaram en el Tamiz de solo probabilidades (rueda factorizada por el único primo par de dos) Tamiz de Eratóstenes; Esto aclara que la única diferencia entre estos dos algoritmos es que el Sieve of Sundaram elimina números compuestos usando todos los números impares como valores base, mientras que el Sieve-Only Odds de Eratosthenes usa solo los primos impares como valores base, con ambos rangos de base. valores acotados a la raíz cuadrada del rango.
Cuando se ejecuta para varios rangos, queda inmediatamente claro que si bien, por supuesto, el recuento de primos resultante para un rango dado es idéntico entre los dos algoritmos, el número de operaciones de selección es mucho mayor para el Sieve of Sundaram y también crece mucho más. rápidamente con rango creciente.
De la implementación anterior, queda claro que la cantidad de trabajo realizado es de acuerdo a lo siguiente:
o dónde:
- n es el rango a tamizar y
- el rango de a a b son los números impares entre 3 y la raíz cuadrada de n
- la una a b gama realmente comienza en el cuadrado de los valores de base impares, pero esta diferencia es insignificante para grandes gamas.
Como la integral del recíproco de x es exactamente, y como el valor más bajo de a es relativamente muy pequeño (cercano a uno que tiene un valor logarítmico de cero), se trata de lo siguiente:
o o .
Ignorando el factor constante de un octavo, la complejidad asintótica en la notación Big O es claramente.
Ver también
Referencias
- ^ V. Ramaswami Aiyar (1934). "Tamiz de Sundaram para números primos". El estudiante de matemáticas . 2 (2): 73. ISSN 0025-5742 .
- ^ G. (1941). "Curiosa 81. Un nuevo tamiz para números primos". Scripta Mathematica . 8 (3): 164.
- Ogilvy, C. Stanley ; John T. Anderson (1988). Excursiones en teoría de números . Publicaciones de Dover , 1988 (reimpresión de Oxford University Press , 1966). págs. 98–100, 158. ISBN 0-486-25778-9.
- Honsberger, Ross (1970). Ingenio en Matemáticas . Nueva biblioteca matemática # 23. Asociación Matemática de América . págs. 75 . ISBN 0-394-70923-3.
- Un nuevo "tamiz" para primos [ enlace muerto permanente ] , un extracto de Kordemski, Boris A. (1974). Köpfchen, Köpfchen! Mathematik zur Unterhaltung . MSB Nr. 78. Urania Verlag. pag. 200. (traducción del libro ruso Кордемский, Борис Анастасьевич (1958). Математическая смекалка . М .: ГИФМЛ.)
- Movshovitz-Hadar, N. (1988). "Presentaciones estimulantes de teoremas seguidos de pruebas receptivas". Para el aprendizaje de las matemáticas . 8 (2): 12-19.
- Ferrando, Elisabetta (2005). Procesos abductivos en conjeturas y demostraciones (PDF) (PhD). Universidad de Purdue. págs. 70–72.
- Baxter, Andrew. "Tamiz de Sundaram" . Temas de la Historia de la Criptografía . Departamento de Matemáticas de MU.