Menu Close

Números que sumados a su siguiente primo dan primos

Introducción

La Enciclopedia electrónica de sucesiones de enteros (OEIS por sus siglas en inglés, de On-Line Encyclopedia of Integer Sequences) es una base de datos que registra sucesiones de números enteros. Está disponible libremente en Internet, en la dirección http://oeis.org.

La semana pasada Antonio Roldán añadió una nueva sucesión a la OEIS, la A249624 que sirve de base para el problema de hoy.

Enunciado

-- Definir la sucesión
--     a249624 :: [Integer]
-- tal que sus elementos son los números x tales que la suma de x y el
-- primo que le sigue es un número primo. Por ejemplo, 
--    ghci> take 20 a249624
--    [0,1,2,6,8,14,18,20,24,30,34,36,38,48,50,54,64,68,78,80]
-- 
-- El número 8 está en la sucesión porque su siguiente primo es 11 y
-- 8+11=19 es primo. El 12 no está en la sucesión porque su siguiente
-- primo es 13 y 12+13=25 no es primo.

Soluciones

import Data.Numbers.Primes (primes, isPrime)
import Data.List (genericReplicate)
 
-- 1ª definición
-- =============
 
a249624 :: [Integer]
a249624 = 0: 1: [x | x <- [2,4..], primo (x + siguientePrimo x)]
 
primo :: Integer -> Bool
primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x]
 
siguientePrimo :: Integer -> Integer
siguientePrimo x = head [y | y <- [x+1..], primo y]
 
-- 2ª definición (por recursión)
-- =============================
 
a249624b :: [Integer]
a249624b = 0 : 1 : 2: aux [2,4..] primos where
    aux (x:xs) (y:ys) 
        | y < x                = aux (x:xs) ys
        | (x+y) `pertenece` ys = x : aux xs (y:ys)
        | otherwise            = aux xs (y:ys)
    pertenece x ys = x == head (dropWhile (<x) ys)
 
primos :: [Integer]
primos = 2 : [x | x <- [3,5..], primo x]
 
-- 3ª definición (con la librería de primos)
-- =========================================
 
a249624c :: [Integer]
a249624c = 0: 1: [x | x <- [2,4..], isPrime (x + siguientePrimo3 x)]
 
siguientePrimo3 x = head [y | y <- [x+1..], isPrime y]
 
-- 4ª definición (por recursión con la librería de primos)
-- =======================================================
 
a249624d :: [Integer]
a249624d = 0 : 1 : 2: aux [2,4..] primes where
    aux (x:xs) (y:ys) 
        | y < x                = aux (x:xs) ys
        | (x+y) `pertenece` ys = x : aux xs (y:ys)
        | otherwise            = aux xs (y:ys)
    pertenece x ys = x == head (dropWhile (<x) ys)
 
-- 5ª definición
-- =============
 
a249624e :: [Integer]
a249624e = [a | q <- primes, 
                let p = siguientePrimo3 (q `div` 2),
                let a = q-p,
                siguientePrimo3 a == p]
 
-- 6ª definición
-- =============
 
a249624f :: [Integer]
a249624f = [x | (x,y) <- zip [0..] ps, isPrime (x+y)]
    where ps = 2:2:concat (zipWith f primes (tail primes))
          f p q = genericReplicate (q-p) q
 
-- 7ª definición
-- =============
 
a249624g :: [Integer]
a249624g = 0:1:(aux primes (tail primes) primes)
    where aux (x:xs) (y:ys) zs
              | null rs   = aux xs ys zs2
              | otherwise = [r-y | r <- rs] ++ (aux xs ys zs2)
              where a = x+y
                    b = 2*y-1
                    zs1 = takeWhile (<=b) zs
                    rs = [r | r <- [a..b], r `elem` zs1]
                    zs2 = dropWhile (<=b) zs
 
-- ---------------------------------------------------------------------
-- § Comparación de eficiencia                                        --
-- ---------------------------------------------------------------------
 
-- La comparación es
--    ghci> :set +s
--    
--    ghci> a249624 !! 700
--    5670
--    (12.72 secs, 1245938184 bytes)
--    
--    ghci> a249624b !! 700
--    5670
--    (8.01 secs, 764775268 bytes)
-- 
--    ghci> a249624c !! 700
--    5670
--    (0.22 secs, 108982640 bytes)
--    
--    ghci> a249624d !! 700
--    5670
--    (0.20 secs, 4707384 bytes)
--    
--    ghci> a249624e !! 700
--    5670
--    (0.17 secs, 77283064 bytes)
--    
--    ghci> a249624f !! 700
--    5670
--    (0.08 secs, 31684408 bytes)
--    
--    ghci> a249624g !! 700
--    5670
--    (0.03 secs, 4651576 bytes)
Inicial

3 soluciones de “Números que sumados a su siguiente primo dan primos

  1. Jesús Navas Orozco
    a249624 :: [Integer]
    a249624 = [x | x <- [0..], primo (x + siguientePrimo x)]
        where siguientePrimo x = head [y | y <- [x+1..], primo y]
              primo x          = divisores x == [1,x]
              divisores n      = [x | x <- [1..n], n `mod` x == 0]
    • Jesús Navas Orozco

      Más eficiente:

      a249624 :: [Integer]
      a249624 = 0 : 1 : [x | x <- [2,4..], primo (x + siguientePrimo x)]
          where siguientePrimo x = head [y| y <- [x+1..], primo y]
                primo n          = head (dropWhile (<n) primos) == n
                primos           = criba [2..]
                criba []         = []
                criba (n:ns)     = n : criba (elimina n ns)
                elimina n xs     = [x | x <- xs, x `mod` n /= 0]
  2. José María Verde López
    a249624 = [a | a <- [0..], esPrimo (a + primoquesigue a)]
     
    primos = criba  [2..]
     
    criba (n:xs) = n : (criba [x | x <- xs, mod x n /= 0])
     
    divisores x = [a | a <- [1..x], mod x a == 0]
     
    esPrimo x = length (divisores x) == 2
     
    primoquesigue x = head (dropWhile (<=x) primos)

Escribe tu solución

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