Menu Close

Día: 15 abril, 2021

Enlaces primos

Un enlace primo de longitud n es una permutación de 1, 2, …, n comienza con 1 y termina con n, tal que la suma de cada par de términos adyacentes es primo. Por ejemplo, para n = 6 la lista [1,4,3,2,5,6] es un enlace primo ua que las sumas de los pares de términos adyacentes son los números primos 5, 7, 5, 7, 11.

Definir la función

   enlacesPrimos :: Int -> [[Int]]

tal que (enlacesPrimos n) es la lista de los enlaces primos de longitud n. Por ejemplo,

   λ> enlacesPrimos 6
   [[1,4,3,2,5,6]]
   λ> enlacesPrimos 7
   [[1,4,3,2,5,6,7],[1,6,5,2,3,4,7]]
   λ> enlacesPrimos 8
   [[1,2,5,6,7,4,3,8],[1,4,7,6,5,2,3,8],[1,2,3,4,7,6,5,8],[1,6,7,4,3,2,5,8]]
   λ> length (enlacesPrimos 10)
   24
   λ> length (head (enlacesPrimos (5*10^4)))
   50000

Soluciones

import Data.List (permutations, delete)
import Data.Numbers.Primes (isPrime)
 
-- 1ª solución
-- ===========
 
enlacesPrimos :: Int -> [[Int]]
enlacesPrimos 1 = [[1]]
enlacesPrimos n =
  [ys | xs <- permutations [2..n-1],
       let ys = (1:xs)++[n],
       conEnlacesPrimos ys]
 
-- (conEnlacesPrimos xs) se verifica si las sumas de los elementos
-- adyacentes de xs son primos. Por ejemplo,
--    conEnlacesPrimos [1,4,3,2,5,6]  ==  True
--    conEnlacesPrimos [1,3,4,2,5,6]  ==  False
conEnlacesPrimos :: [Int] -> Bool
conEnlacesPrimos xs =
  all isPrime (enlaces xs)
 
-- (enlaces xs) es la lista de las sumas de los elementos adyacentes de
-- xs. Por ejemplo,
--    enlaces [1,4,3,2,5,6]  ==  [5,7,5,7,11]
--    enlaces [1,3,4,2,5,6]  ==  [4,7,6,7,11]
enlaces :: [Int] -> [Int]
enlaces xs =
  zipWith (+) xs (tail xs)
 
-- 2ª solución
-- ===========
 
enlacesPrimos2 :: Int -> [[Int]]
enlacesPrimos2 1 = [[1]]
enlacesPrimos2 n = aux [(n-1,[n],[n-1,n-2..2])]
  where
    aux [] = []
    aux ((1,x:xs,_):ts) =
      [1:x:xs | isPrime (1+x)] ++ aux ts
    aux ((k,x:xs,ys):ts) =
      aux ([(k-1,y:x:xs,delete y ys) | y <-ys, isPrime (y+x)] ++ ts)
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> length (enlacesPrimos 12)
--    216
--    (6.04 secs, 22,266,444,408 bytes)
--    λ> length (enlacesPrimos2 12)
--    216
--    (0.03 secs, 18,102,192 bytes)
--
--    λ> length (enlacesPrimos2 17)
--    59448
--    (2.69 secs, 8,514,104,800 bytes)

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>