Menu Close

La conjetura de Levy

Hyman Levy observó que

    7 = 3 + 2 x 2
    9 = 3 + 2 x 3 =  5 + 2 x 2
   11 = 5 + 2 x 3 =  7 + 2 x 2
   13 = 3 + 2 x 5 =  7 + 2 x 3
   15 = 3 + 2 x 5 = 11 + 2 x 2
   17 = 3 + 2 x 7 =  7 + 2 x 5 = 11 + 2 x 3 = 13 + 2 x 2
   19 = 5 + 2 x 7 = 13 + 2 x 3

y conjeturó que todos los número impares mayores o iguales que 7 se pueden escribir como la suma de un primo y el doble de un primo. El objetivo de los siguientes ejercicios es comprobar la conjetura de Levy.

Definir las siguientes funciones

   descomposicionesLevy :: Integer -> [(Integer,Integer)]
   graficaLevy          :: Integer -> IO ()

tales que

  • (descomposicionesLevy x) es la lista de pares de primos (p,q) tales que x = p + 2q. Por ejemplo,
     descomposicionesLevy  7  ==  [(3,2)]
     descomposicionesLevy  9  ==  [(3,3),(5,2)]
     descomposicionesLevy 17  ==  [(3,7),(7,5),(11,3),(13,2)]
  • (graficaLevy n) dibuja los puntos (x,y) tales que x pertenece a [7,9..7+2x(n-1)] e y es el número de descomposiciones de Levy de x. Por ejemplo, (graficaLevy 200) dibuja
    La_conjetura_de_Levy-200

Comprobar con QuickCheck la conjetura de Levy.

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck
import Graphics.Gnuplot.Simple
 
descomposicionesLevy :: Integer -> [(Integer,Integer)]
descomposicionesLevy x =
  [(p,q) | p <- takeWhile (< x) (tail primes)
         , let q = (x - p) `div` 2
         , isPrime q]
 
-- graficaLevy 300
graficaLevy :: Integer -> IO ()
graficaLevy n =
  plotList [ Key Nothing
           , XRange (7,fromIntegral (7+2*(n-1)))
           , PNG ("La_conjetura_de_Levy-" ++ show n ++ ".png")
           ]
           [(x, length (descomposicionesLevy x)) | x <- [7,9..7+2*(n-1)]] 
 
-- La propiedad es
prop_Levy :: Integer -> Bool
prop_Levy x =
  not (null (descomposicionesLevy (7 + 2 * abs x)))
 
-- La comprobación es
--    λ> quickCheck prop_Levy
--    +++ OK, passed 100 tests.
Inicial

6 soluciones de “La conjetura de Levy

  1. angruicam1
    import Test.QuickCheck
    import Data.Numbers.Primes     (primes, isPrime)
    import Graphics.Gnuplot.Simple (plotList, Attribute (Key))
     
    descomposicionesLevy :: Integer -> [(Integer,Integer)]
    descomposicionesLevy x =
      [(y,z`div`2)
      | y <- takeWhile (< x) primes,
        let z = x-y,
            even z && isPrime (z`div`2)]
     
    -- Gráfica
    -- =======
     
    graficaLevy :: Integer -> IO ()
    graficaLevy n =
      plotList
      [Key Nothing]
      [(x,length (descomposicionesLevy x)) | x <- [7,9..7+2*(n-1)]]
     
    -- Propiedad
    -- =========
     
    -- La propiedad es
    propLevy :: Integer -> Property
    propLevy x = x >= 7 && odd x ==> not (null (descomposicionesLevy x))
     
    -- La comprobación es
    --    λ> quickCheck propLevy
    --    +++ OK, passed 100 tests.
  2. albcarcas1

    Una solución por recursión

    descomposicionesLevy :: Integer -> [(Integer,Integer)]
    descomposicionesLevy n = aux n primes
      where aux n (x:xs)
              | n > x && even (n-x) && isPrime a = [(x, a)] ++ aux n xs
              | x < n && odd (n-x)               = aux n xs
              | x < n && not (isPrime a)         = aux n xs
              | otherwise                        = []
              where a = div (n-x) 2
     
    graficaLevy :: Integer -> IO ()
    graficaLevy n =
      plotList [ Title "Conjetura de Levy"
               , Key Nothing]
               [(x,length(descomposicionesLevy x)) | x <- [7,9..7+2*(n-1)]]
     
    prop_Levy :: Integer -> Property
    prop_Levy x =
      odd x && x >= 7 ==> not (null (descomposicionesLevy x))
  3. alerodrod5
    import Data.Numbers.Primes
    import Graphics.Gnuplot.Simple
    import Test.QuickCheck
     
    descomposicionesLevy :: Integer -> [(Integer,Integer)]
    descomposicionesLevy n =
      [(x,y) | x <- takeWhile (<n) primes
             , let y = (n-x) `div` 2
             , (n-x) `mod` 2 ==0
             , isPrime y]
     
    graficaLevy :: Integer -> IO ()
    graficaLevy n =
      plotList [Key Nothing]
               [(x,length (descomposicionesLevy x)) | x <- [7,9..7+2*(n-1)]]
     
    propLevy :: Integer -> Property
    propLevy x = x >= 7 && odd x ==> not (null (descomposicionesLevy x))
  4. menvealer
    import Data.Numbers.Primes (primes)
     
    descomposicionesLevy :: Integer -> [(Integer,Integer)]
    descomposicionesLevy n = [(a,b) | a <- takeWhile (< n) primes
                                    , b <- takeWhile  (<= c) primes
                                    , n == a + 2*b]
      where c =  div n 2
  5. carbremor
    -- Conjetura de Levy
     
    -- Librerías usadas
     
    import Data.Numbers.Primes
    import Graphics.Gnuplot.Simple
    import Data.List
    import Test.QuickCheck
     
    descomposicionesLevy :: Integer -> [(Integer,Integer)]
    descomposicionesLevy n =
      [(x,y) | x <- [0..n]
             , y <- [0..n]
             , isPrime x
             , isPrime y
             , x+2*y == n]
     
    -- Eficiencia
     
    -- λ> descomposicionesLevy 17
    -- [(3,7),(7,5),(11,3),(13,2)]
    -- (0.01 secs, 1,332,512 bytes)
     
    -- λ> descomposicionesLevy 487
    -- [(5,241),(29,229),(41,223),(89,199),(101,193),(173,157),(233,127),(269,109),(281,103),(293,97),(353,67),(401,43),(449,19),(461,13)]
    -- (0.91 secs, 1,489,047,344 bytes)
     
    -- Gráfica
     
    graficaLevy :: Integer -> IO ()
    graficaLevy n =
      plotList [Key Nothing]
               [(x,length (descomposicionesLevy x)) | x <- [7,9..7+2*(n-1)]]
     
    -- Propiedad
     
    propLevy :: Integer -> Property
    propLevy x = x >= 7 && odd x ==> not (null (descomposicionesLevy x))
     
    -- λ> quickCheck propLevy
    -- +++ OK, passed 100 tests.
    -- (0.12 secs, 69,287,392 bytes)
  6. goncarlop
    import Graphics.Gnuplot.Simple
    import Test.QuickCheck
     
    descomposicionesLevy :: Integer -> [(Integer, Integer)]
    descomposicionesLevy x =
      [(p,q)| p <- ys
            , q <- ys
            , p + 2*q == x]
      where ys = take (fromIntegral x) primos
     
    primos :: [Integer]
    primos = [p | p <- [2..], numDiv p == 2] 
     
    numDiv :: Integer -> Int
    numDiv n = length[x | x <- [1..n], n `mod` x == 0]
     
    graficaLevy :: Integer -> IO ()
    graficaLevy n =
      plotList [Key Nothing]
               [(x,length (descomposicionesLevy x)) | x <- [7,9..7+2*(n-1)]]
     
    propiedadLevy :: Integer -> Property
    propiedadLevy n =
      n >= 7 && not (even n) ==> not (length (descomposicionesLevy n) == 0)

Escribe tu solución

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