Menu Close

Día: 17 mayo, 2021

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

   noSonCuadradoMasPrimo :: [Integer]

cuyos elementos son los números que no se pueden escribir como un cuadrado más un primo. Por ejemplo,

   λ> 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

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>