Primo suma de dos cuadrados
Definir la sucesión
|
1 |
primosSumaDe2Cuadrados :: [Integer] |
cuyos elementos son los números primos que se pueden escribir como sumas de dos cuadrados. Por ejemplo,
|
1 2 3 4 |
λ> take 20 primosSumaDe2Cuadrados [2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181] λ> primosSumaDe2Cuadrados !! (2*10^5) 5803241 |
En el ejemplo anterior,
- 13 está en la sucesión porque es primo y 13 = 2²+3².
- 11 no está en la sucesión porque no se puede escribir como suma de dos cuadrados (en efecto, 11-1=10, 11-2²=7 y 11-3²=2 no son cuadrados).
- 20 no está en la sucesión porque, aunque es suma de dos cuadrados (20=4²+2²), no es primo.
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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
import Data.Numbers.Primes (primes) -- 1ª solución -- =========== primosSumaDe2Cuadrados1 :: [Integer] primosSumaDe2Cuadrados1 = [n | n <- primes, esSumaDe2Cuadrados n] esSumaDe2Cuadrados :: Integer -> Bool esSumaDe2Cuadrados n = not (null (sumas2cuadrados n)) sumas2cuadrados :: Integer -> [(Integer,Integer)] sumas2cuadrados n = [(x,y) | x <- [1..ceiling (sqrt (fromIntegral n))], let z = n - x^2, esCuadrado z, let y = raiz z, x <= y] -- (esCuadrado x) se verifica si x es un número al cuadrado. Por -- ejemplo, -- esCuadrado 25 == True -- esCuadrado 26 == False esCuadrado :: Integer -> Bool esCuadrado x = x == y * y where y = raiz x -- (raiz x) es la raíz cuadrada entera de x. Por ejemplo, -- raiz 25 == 5 -- raiz 24 == 4 -- raiz 26 == 5 raiz :: Integer -> Integer raiz x = floor (sqrt (fromIntegral x)) -- 2ª solución -- =========== primosSumaDe2Cuadrados2 :: [Integer] primosSumaDe2Cuadrados2 = 2 : [n | n <- primes, n `mod` 4 == 1] -- Comparación de eficiencia -- ========================= -- λ> primosSumaDe2Cuadrados1 !! (2*10^3) -- 38153 -- (3.03 secs, 568,239,744 bytes) -- λ> primosSumaDe2Cuadrados2 !! (2*10^3) -- 38153 -- (0.05 secs, 20,017,912 bytes) |
Referencias
- N.J.A. Sloane, Sucesión A002313 de la OEIS.
- M. Bates, Primes of the form x² + ny²–
- G. Xiao, Two squares.