Cuadrado más primo
El enunciado del problema C2 de la Fase Local de la Olimpiada Matemática Española del 2006 es
¿Existe un conjunto infinito de números naturales que NO se pueden representar en la forma n²+p, siendo n natural y p primo? Razónese la contestación.
Definir la lista
1 |
noSonCuadradoMasPrimo :: [Integer] |
cuyos elementos son los números que no se pueden escribir como un cuadrado más un primo. Por ejemplo,
1 2 3 4 |
λ> take 15 noSonCuadradoMasPrimo [1,10,25,34,58,64,85,91,121,130,169,196,214,226,289] λ> noSonCuadradoMasPrimo2 !! 200 78961 |
En la lista no está el 2 (porque 2 = 0²+2), el 3 (porque 3 = 1²+2), el 4 (porque 4 = 0²+4) ni el 11 (porque 11 = 3²+2).
Comprobar con QuickCheck que noSonCuadradoMasPrimo es infinita.
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 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 |
import Data.Numbers.Primes (primes, isPrime) import Test.QuickCheck -- 1ª solución -- =========== noSonCuadradoMasPrimo :: [Integer] noSonCuadradoMasPrimo = filter (not . esCuadradoMasPrimo) [1..] -- (esCuadradoMasPrimo n) se verifica si n se puede escribir como un -- cuadrado más un primo. Por ejemplo, -- esCuadradoMasPrimo 11 == True -- esCuadradoMasPrimo 10 == False esCuadradoMasPrimo :: Integer -> Bool esCuadradoMasPrimo n = or [esCuadrado (n - p) | p <- takeWhile (<= n) primes] -- (esCuadrado x) se verifica si x es un cuadrado perfecto. Por -- ejemplo, -- esCuadrado 16 == True -- esCuadrado 27 == False esCuadrado :: Integer -> Bool esCuadrado x = (raizEntera x)^2 == x -- (raizEntera x) es el mayor entero cuyo cuadrado es menor o igual que -- x. Por ejemplo, -- raizEntera 16 == 4 -- raizEntera 27 == 5 raizEntera :: Integer -> Integer raizEntera x = aux (1,x) where aux (a,b) | d == x = c | c == a = c | d < x = aux (c,b) | otherwise = aux (a,c) where c = (a+b) `div` 2 d = c^2 -- 2ª solución -- =========== noSonCuadradoMasPrimo2 :: [Integer] noSonCuadradoMasPrimo2 = filter (not . esCuadradoMasPrimo2) [1..] -- (esCuadradoMasPrimo2 n) se verifica si n se puede escribir como un -- cuadrado más un primo. Por ejemplo, -- esCuadradoMasPrimo2 11 == True -- esCuadradoMasPrimo2 10 == False esCuadradoMasPrimo2 :: Integer -> Bool esCuadradoMasPrimo2 n = or [isPrime (n - m) | m <- takeWhile (<= n) cuadrados] -- cuadrados es la lista de los cuadrados de los números naturales. Por -- ejemplo, -- take 10 cuadrados == [0,1,4,9,16,25,36,49,64,81] cuadrados :: [Integer] cuadrados = map (^2) [0..] -- Comprobación de equivalencia -- ============================ -- La comprobación es -- λ> take 50 noSonCuadradoMasPrimo == take 50 noSonCuadradoMasPrimo2 -- True -- Comparación de eficiencia -- ========================= -- λ> noSonCuadradoMasPrimo !! 70 -- 8649 -- (12.42 secs, 13,289,896,304 bytes) -- λ> noSonCuadradoMasPrimo2 !! 70 -- 8649 -- (0.23 secs, 650,843,816 bytes) -- Propiedad -- ========= -- La propiedad es prop_infinitud :: Integer -> Bool prop_infinitud n = not (null (dropWhile (<= n) noSonCuadradoMasPrimo2)) -- La comprobación es -- λ> quickCheck prop_infinitud -- +++ OK, passed 100 tests. |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>