Números primos de Hilbert
Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, …
Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, …
Definir la sucesión
|
1 |
primosH :: [Integer] |
tal que sus elementos son los primos de Hilbert. Por ejemplo,
|
1 2 |
take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! 20000 == 203221 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
-- 1ª definición -- ============= -- numerosH es la sucesión de los números de Hilbert. Por ejemplo, -- take 15 numerosH == [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57] numerosH :: [Integer] numerosH = [1,5..] -- (divisoresH n) es la lista de los números de Hilbert que dividen a -- n. Por ejemplo, -- divisoresH 117 == [1,9,13,117] -- divisoresH 21 == [1,21] divisoresH :: Integer -> [Integer] divisoresH n = [x | x <- takeWhile (<=n) numerosH, n `mod` x == 0] primosH1 :: [Integer] primosH1 = [n | n <- tail numerosH, divisoresH n == [1,n]] -- 2ª definición -- ============= primosH2 :: [Integer] primosH2 = filter esPrimoH (tail numerosH) where esPrimoH n = all noDivideAn [5,9..m] where noDivideAn x = n `mod` x /= 0 m = ceiling (sqrt (fromIntegral n)) -- Comparación de eficiencia -- ========================= -- λ> primosH1 !! 2000 -- 16957 -- (6.93 secs, 750,291,352 bytes) -- λ> primosH2 !! 2000 -- 16957 -- (0.13 secs, 18,066,288 bytes) |