Menu Close

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>

2 soluciones de “Cuadrado más primo

  1. Rubén Muñoz Mkrtchian
    -- Definición:
    -- ==========
     
    noSonCuadradoMasPrimo :: [Integer]
    noSonCuadradoMasPrimo = filter (not . esCuadradoMasPrimo) [1..]
      where esCuadradoMasPrimo n = any isPrime [x | x <- map (n-) potenciasMenores]
              where potenciasMenores = takeWhile (< n) (map (^2) [0..n])
     
    -- Demostración con quickCheck:
    -- ===========================
     
    prop1 :: Integer -> Bool
    prop1 n = not (null (filter (> m) noSonCuadradoMasPrimo))
      where m = abs n
     
    -- La comprobación es:
    -- λ> quickCheck prop1
    -- +++ OK, passed 100 tests.
     
    -- Observación:
    -- ===========
     
    -- Se observa en el siguiente cálculo que si un número n es de la forma
    -- n = 3*k + 2, con k >= 1, entonces n no es suma de cuadrado y primo.
    --    λ> take 30 noSonCuadradoMasPrimo
    --    [1,10,25,34,58,64,85,91,121,130,169,196,214,226,289,324,370,400,526,529,
    --     625,676,706,730,771,784,841,1024,1089,1225]
    --    λ> map (^2) [5,8..35]
    --    [25,64,121,196,289,400,529,676,841,1024,1225]
     
    prop2 :: Integer -> Bool
    prop2 n = any isPrime [x | x <- map (m-) potenciasMenores]
      where m = 3 * abs n + 5
            potenciasMenores = takeWhile (< m) (map (^2) [0..m])
     
    -- La comprobación es:
    -- λ> quickCheck prop2
    -- +++ OK, passed 100 tests.
     
    -- Demostración rigurosa:
    -- =====================
    --
    -- Vamos a demostrar que la lista es infinita a partir de la observación
    -- anterior. Supongamos que x = m^2, donde m = 3k + 2, con k >= 1. Entonces
    -- tenemos lo siguiente:
    --     m^2 - n^2 = (m + n)(m - n) = p
    --
    -- Pero p es primo, luego debe escribirse de la forma p = p*1, obteniendo por
    -- lo tanto un sistema de ecuaciones.
    --     m + n = p 
    --     m - n = 1
    --
    -- Sumando las ecuaciones se obtiene lo siguiente:
    --     p = 2m - 1 = 2(3k + 2) - 1 = 6k + 3 = 3(2k + 1)
    --
    -- Acabamos de llegar a que p es múltiplo de 3. Dado que k >= 1, el número p
    -- obtenido jamás será un número primo. De esta forma queda demostrada la
    -- infinitud del conjunto.
  2. Amalia Linares Serrano
     
    import Data.Numbers.Primes
    import Data.List
    import Test.QuickCheck
     
    noSonCuadradoMasPrimo :: [Integer]
    noSonCuadradoMasPrimo = [n | n <- [1..] , all (x -> notElem n (takeWhile (<=n) x)) (takeWhile (x -> head x <= n)sonCuadradoMasPrimo)]
     
    sonCuadradoMasPrimo :: [[Integer]]
    sonCuadradoMasPrimo = [sonCuadradoMasPrimo1 n | n <- [0..]]
    sonCuadradoMasPrimo1 n = nub [n^2+p | p <- primes]
     
    propiedad :: Integer -> Bool
    propiedad n = dropWhile (<m) noSonCuadradoMasPrimo /= []
                  where m = abs n + 1

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.