array

La sucesión de Sylvester

PorJosé A. Alonso 19-marzo-201825-abril-2021

La sucesión de Sylvester es la sucesión que comienza en 2 y sus restantes términos se obtienen multiplicando los anteriores y sumándole 1.

Definir las funciones

   sylvester        :: Integer -> Integer
   graficaSylvester :: Integer -> Integer -> IO ()

1 2	sylvester :: Integer -> Integer graficaSylvester :: Integer -> Integer -> IO ()

tales que

(sylvester n) es el n-ésimo término de la sucesión de Sylvester. Por ejemplo,

     λ> [sylvester n | n <- [0..7]]
     [2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]
     λ> length (show (sylvester 25))
     6830085

λ> [sylvester n | n <- [0..7]]

[2,3,7,43,1807,3263443,10650056950807,113423713055421844361000443]

λ> length (show (sylvester 25))

6830085

(graficaSylvester d n) dibuja la gráfica de los d últimos dígitos de los n primeros términos de la sucesión de Sylvester. Por ejemplo,
- (graficaSylvester 3 30) dibuja
- (graficaSylvester 4 30) dibuja
- (graficaSylvester 5 30) dibuja

Soluciones

import Data.List               (genericIndex)
import Data.Array              ((!), array)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG))

-- 1ª solución (por recursión)
-- ===========================

sylvester1 :: Integer -> Integer
sylvester1 0 = 2
sylvester1 n = 1 + product [sylvester1 k | k <- [0..n-1]]

-- 2ª solución (con programación dinámica)
-- =======================================

sylvester2 :: Integer -> Integer
sylvester2 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + product [v!k | k <- [0..m-1]]

-- 3ª solución
-- ===========

sylvester3 :: Integer -> Integer
sylvester3 0 = 2
sylvester3 n = 1 + x^2 - x
  where x = sylvester3 (n-1)

-- 4ª solución
-- ===========

sylvester4 :: Integer -> Integer
sylvester4 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 2
  f m = 1 + x^2 - x
    where x = v ! (m-1)

-- 4ª solución
-- ===========

sylvester5 :: Integer -> Integer
sylvester5 0 = 2
sylvester5 n = 1 + (productosSylvester `genericIndex` (n-1))

sucSylvester5 :: [Integer]
sucSylvester5 = map sylvester5 [0..]

productosSylvester :: [Integer]
productosSylvester = scanl1 (*) sucSylvester5

-- Comparación de eficiencia
-- =========================

--    λ> length (show (sylvester1 20))
--    213441
--    (3.40 secs, 519,249,840 bytes)
--    λ> length (show (sylvester2 20))
--    213441
--    (0.10 secs, 13,716,024 bytes)
--    λ> length (show (sylvester3 20))
--    213441
--    (0.16 secs, 13,646,472 bytes)
--    λ> length (show (sylvester4 20))
--    213441
--    (0.18 secs, 13,654,064 bytes)
--    λ> length (show (sylvester5 20))
--    213441
--    (0.12 secs, 13,497,192 bytes)

graficaSylvester :: Integer -> Integer -> IO ()
graficaSylvester d n =
  plotList [ Key Nothing
           , PNG ("La_sucesion_de_Sylvester_" ++ show (d,n) ++ ".png")
           ]
           [sylvester5 k `mod` (10^d) | k <- [0..n]]

import Data.List (genericIndex)

import Data.Array ((!), array)

import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG))

-- 1ª solución (por recursión)

-- ===========================

sylvester1 :: Integer -> Integer

sylvester1 0 = 2

sylvester1 n = 1 + product [sylvester1 k | k <- [0..n-1]]

-- 2ª solución (con programación dinámica)

-- =======================================

sylvester2 :: Integer -> Integer

sylvester2 n = v ! n where

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 2

f m = 1 + product [v!k | k <- [0..m-1]]

-- 3ª solución

-- ===========

sylvester3 :: Integer -> Integer

sylvester3 0 = 2

sylvester3 n = 1 + x^2 - x

where x = sylvester3 (n-1)

-- 4ª solución

-- ===========

sylvester4 :: Integer -> Integer

sylvester4 n = v ! n where

v = array (0,n) [(i,f i) | i <- [0..n]]

f 0 = 2

f m = 1 + x^2 - x

where x = v ! (m-1)

-- 4ª solución

-- ===========

sylvester5 :: Integer -> Integer

sylvester5 0 = 2

sylvester5 n = 1 + (productosSylvester `genericIndex` (n-1))

sucSylvester5 :: [Integer]

sucSylvester5 = map sylvester5 [0..]

productosSylvester :: [Integer]

productosSylvester = scanl1 (*) sucSylvester5

-- Comparación de eficiencia

-- =========================

-- λ> length (show (sylvester1 20))

-- 213441

-- (3.40 secs, 519,249,840 bytes)

-- λ> length (show (sylvester2 20))

-- 213441

-- (0.10 secs, 13,716,024 bytes)

-- λ> length (show (sylvester3 20))

-- 213441

-- (0.16 secs, 13,646,472 bytes)

-- λ> length (show (sylvester4 20))

-- 213441

-- (0.18 secs, 13,654,064 bytes)

-- λ> length (show (sylvester5 20))

-- 213441

-- (0.12 secs, 13,497,192 bytes)

graficaSylvester :: Integer -> Integer -> IO ()

graficaSylvester d n =

plotList [ Key Nothing

, PNG ("La_sucesion_de_Sylvester_" ++ show (d,n) ++ ".png")

]

[sylvester5 k `mod` (10^d) | k <- [0..n]]

Codificación matricial

PorJosé A. Alonso 21-marzo-201729-marzo-2017

El procedimiento de codificación matricial se puede entender siguiendo la codificación del mensaje "todoparanada" como se muestra a continuación:

Se calcula la longitud L del mensaje. En el ejemplo es L es 12.
Se calcula el menor entero positivo N cuyo cuadrado es mayor o igual que L. En el ejemplo N es 4.
Se extiende el mensaje con N²-L asteriscos. En el ejemplo, el mensaje extendido es "todoparanada****"
Con el mensaje extendido se forma una matriz cuadrada NxN. En el ejemplo la matriz es

     | t o d o |
     | p a r a |
     | n a d a |
     | * * * * |

| t o d o |

| p a r a |

| n a d a |

| * * * * |

Se rota 90º la matriz del mensaje extendido. En el ejemplo, la matriz rotada es

     | * n p t |
     | * a a o |
     | * d r d |
     | * a a o |

| * n p t |

| * a a o |

| * d r d |

| * a a o |

Se calculan los elementos de la matriz rotada. En el ejemplo, los elementos son "*npt*aap*drd*aao"
El mensaje codificado se obtiene eliminando los asteriscos de los elementos de la matriz rotada. En el ejemplo, "nptaapdrdaao".

Definir la función

   codificado :: String -> String

1	codificado :: String -> String

tal que (codificado cs) es el mensaje obtenido aplicando la codificación matricial al mensaje cs. Por ejemplo,

   codificado "todoparanada"    ==  "nptaaodrdaao"
   codificado "nptaaodrdaao"    ==  "danaopadtora"
   codificado "danaopadtora"    ==  "todoparanada"
   codificado "entodolamedida"  ==  "dmdeaeondltiao"

codificado "todoparanada" == "nptaaodrdaao"

codificado "nptaaodrdaao" == "danaopadtora"

codificado "danaopadtora" == "todoparanada"

codificado "entodolamedida" == "dmdeaeondltiao"

Nota: Este ejercicio está basado en el problema Secret Message de Kattis.

Soluciones

import Data.List (genericLength)
import Data.Array

codificado :: String -> String
codificado cs =
  filter (/='*') (elems (rota p))
  where n = ceiling (sqrt (genericLength cs))
        p = listArray ((1,1),(n,n)) (cs ++ repeat '*')

rota :: Array (Int,Int) Char -> Array (Int,Int) Char
rota p = array d [((i,j),p!(n+1-j,i)) | (i,j) <- indices p]
  where d = bounds p
        n = fst (snd d)

import Data.List (genericLength)

import Data.Array

codificado :: String -> String

codificado cs =

filter (/='*') (elems (rota p))

where n = ceiling (sqrt (genericLength cs))

p = listArray ((1,1),(n,n)) (cs ++ repeat '*')

rota :: Array (Int,Int) Char -> Array (Int,Int) Char

rota p = array d [((i,j),p!(n+1-j,i)) | (i,j) <- indices p]

where d = bounds p

n = fst (snd d)

Relleno de matrices

PorJosé A. Alonso 19-enero-201626-enero-2016

Dada una matriz cuyos elementos son 0 ó 1, su relleno es la matriz obtenida haciendo iguales a 1 los elementos de las filas y de las columna que contienen algún uno. Por ejemplo, el relleno de la matriz de la izquierda es la de la derecha:

   0 0 0 0 0    1 0 0 1 0
   0 0 0 0 0    1 0 0 1 0
   0 0 0 1 0    1 1 1 1 1
   1 0 0 0 0    1 1 1 1 1
   0 0 0 0 0    1 0 0 1 0

0 0 0 0 0 1 0 0 1 0

0 0 0 1 0 1 1 1 1 1

1 0 0 0 0 1 1 1 1 1

0 0 0 0 0 1 0 0 1 0

Las matrices se pueden representar mediante tablas cuyos índices son pares de enteros

   type Matriz = Array (Int,Int) Int

1	type Matriz = Array (Int,Int) Int

por ejemplo, la matriz de la izquierda de la figura anterior se define por

   ej :: Matriz                  
   ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                                 0, 0, 0, 0, 0,
                                 0, 0, 0, 1, 0,
                                 1, 0, 0, 0, 0,
                                 0, 0, 0, 0, 0]

ej :: Matriz

ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,

0, 0, 0, 0, 0,

0, 0, 0, 1, 0,

1, 0, 0, 0, 0,

0, 0, 0, 0, 0]

Definir la función

   relleno :: Matriz -> Matriz

1	relleno :: Matriz -> Matriz

tal que (relleno p) es el relleno de la matriz p. Por ejemplo,

   λ> elems (relleno ej)
   [1,0,0,1,0,
    1,0,0,1,0,
    1,1,1,1,1,
    1,1,1,1,1,
    1,0,0,1,0]

λ> elems (relleno ej)

[1,0,0,1,0,

1,0,0,1,0,

1,1,1,1,1,

1,0,0,1,0]

Soluciones

import Data.Array

type Matriz = Array (Int,Int) Int

ej :: Matriz                  
ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,
                              0, 0, 0, 0, 0,
                              0, 0, 0, 1, 0,
                              1, 0, 0, 0, 0,
                              0, 0, 0, 0, 0]

-- 1ª solución
-- ===========

relleno1 :: Matriz -> Matriz
relleno1 p = 
    array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
    where (_,(m,n)) = bounds p
          f i j | 1 `elem` [p!(i,k) | k <- [1..n]] = 1
                | 1 `elem` [p!(k,j) | k <- [1..m]] = 1
                | otherwise                        = 0

-- 2ª solución
-- ===========

relleno2 :: Matriz -> Matriz
relleno2 p = 
    array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]
    where (_,(m,n)) = bounds p
          filas     = filasConUno p
          columnas  = columnasConUno p
          f i j | i `elem` filas    = 1
                | j `elem` columnas = 1
                | otherwise         = 0

-- (filasConUno p) es la lista de las filas de p que tienen algún
-- uno. Por ejemplo,
--    filasConUno ej  ==  [3,4]
filasConUno :: Matriz -> [Int]
filasConUno p = [i | i <- [1..m], filaConUno p i]
    where (_,(m,n)) = bounds p

-- (filaConUno p i) se verifica si p tiene algún uno en la fila i. Por
-- ejemplo, 
--    filaConUno ej 3  ==  True
--    filaConUno ej 2  ==  False
filaConUno :: Matriz -> Int -> Bool
filaConUno p i = any (==1) [p!(i,j) | j <- [1..n]]
    where (_,(_,n)) = bounds p

-- (columnasConUno p) es la lista de las columnas de p que tienen algún
-- uno. Por ejemplo,
--    columnasConUno ej  ==  [1,4]
columnasConUno :: Matriz -> [Int]
columnasConUno p = [j | j <- [1..n], columnaConUno p j]
    where (_,(m,n)) = bounds p

-- (columnaConUno p i) se verifica si p tiene algún uno en la columna i. Por
-- ejemplo, 
--    columnaConUno ej 1  ==  True
--    columnaConUno ej 2  ==  False
columnaConUno :: Matriz -> Int -> Bool
columnaConUno p j = any (==1) [p!(i,j) | i <- [1..m]]
    where (_,(m,_)) = bounds p

-- 3ª solución
-- ===========

relleno3 :: Matriz -> Matriz
relleno3 p = p // ([((i,j),1) | i <- filas,  j <- [1..n]] ++ 
                   [((i,j),1) | i <- [1..m], j <- columnas])
  where (_,(m,n)) = bounds p
        filas     = filasConUno p
        columnas  = columnasConUno p


-- Comparación de eficiencia
-- =========================

--    λ> let f i j = if i == j then 1 else 0 
--    λ> let q n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]
--    
--    λ> sum (elems (relleno1 (q 200)))
--    40000
--    (6.90 secs, 1,877,369,544 bytes)
--    
--    λ> sum (elems (relleno2 (q 200)))
--    40000
--    (0.46 secs, 57,354,168 bytes)
--    
--    λ> sum (elems (relleno3 (q 200)))
--    40000
--    (0.34 secs, 80,465,144 bytes)
--    
--    λ> sum (elems (relleno2 (q 500)))
--    250000
--    (4.33 secs, 353,117,640 bytes)
--    
--    λ> sum (elems (relleno3 (q 500)))
--    250000
--    (2.40 secs, 489,630,048 bytes)

100

101

import Data.Array

type Matriz = Array (Int,Int) Int

ej :: Matriz

ej = listArray ((1,1),(5,5)) [0, 0, 0, 0, 0,

0, 0, 0, 0, 0,

0, 0, 0, 1, 0,

1, 0, 0, 0, 0,

0, 0, 0, 0, 0]

-- 1ª solución

-- ===========

relleno1 :: Matriz -> Matriz

relleno1 p =

array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]

where (_,(m,n)) = bounds p

f i j | 1 `elem` [p!(i,k) | k <- [1..n]] = 1

| 1 `elem` [p!(k,j) | k <- [1..m]] = 1

| otherwise = 0

-- 2ª solución

-- ===========

relleno2 :: Matriz -> Matriz

relleno2 p =

array ((1,1),(m,n)) [((i,j),f i j) | i <- [1..m], j <- [1..n]]

where (_,(m,n)) = bounds p

filas = filasConUno p

columnas = columnasConUno p

f i j | i `elem` filas = 1

| j `elem` columnas = 1

| otherwise = 0

-- (filasConUno p) es la lista de las filas de p que tienen algún

-- uno. Por ejemplo,

-- filasConUno ej == [3,4]

filasConUno :: Matriz -> [Int]

filasConUno p = [i | i <- [1..m], filaConUno p i]

where (_,(m,n)) = bounds p

-- (filaConUno p i) se verifica si p tiene algún uno en la fila i. Por

-- ejemplo,

-- filaConUno ej 3 == True

-- filaConUno ej 2 == False

filaConUno :: Matriz -> Int -> Bool

filaConUno p i = any (==1) [p!(i,j) | j <- [1..n]]

where (_,(_,n)) = bounds p

-- (columnasConUno p) es la lista de las columnas de p que tienen algún

-- uno. Por ejemplo,

-- columnasConUno ej == [1,4]

columnasConUno :: Matriz -> [Int]

columnasConUno p = [j | j <- [1..n], columnaConUno p j]

where (_,(m,n)) = bounds p

-- (columnaConUno p i) se verifica si p tiene algún uno en la columna i. Por

-- ejemplo,

-- columnaConUno ej 1 == True

-- columnaConUno ej 2 == False

columnaConUno :: Matriz -> Int -> Bool

columnaConUno p j = any (==1) [p!(i,j) | i <- [1..m]]

where (_,(m,_)) = bounds p

-- 3ª solución

-- ===========

relleno3 :: Matriz -> Matriz

relleno3 p = p // ([((i,j),1) | i <- filas, j <- [1..n]] ++

[((i,j),1) | i <- [1..m], j <- columnas])

where (_,(m,n)) = bounds p

filas = filasConUno p

columnas = columnasConUno p

-- Comparación de eficiencia

-- =========================

-- λ> let f i j = if i == j then 1 else 0

-- λ> let q n = array ((1,1),(n,n)) [((i,j),f i j) | i <- [1..n], j <- [1..n]]

-- λ> sum (elems (relleno1 (q 200)))

-- 40000

-- (6.90 secs, 1,877,369,544 bytes)

-- λ> sum (elems (relleno2 (q 200)))

-- 40000

-- (0.46 secs, 57,354,168 bytes)

-- λ> sum (elems (relleno3 (q 200)))

-- 40000

-- (0.34 secs, 80,465,144 bytes)

-- λ> sum (elems (relleno2 (q 500)))

-- 250000

-- (4.33 secs, 353,117,640 bytes)

-- λ> sum (elems (relleno3 (q 500)))

-- 250000

-- (2.40 secs, 489,630,048 bytes)

Referencias

Basado en Matrix Fill-In del blog Programming Praxis.

Ampliación de una matriz sumando sus filas

PorJosé A. Alonso 2-abril-20151-mayo-2015

Representamos las matrices mediante el tipo de dato

   type Matriz a = Array (Int,Int) a

1	type Matriz a = Array (Int,Int) a

Por ejemplo,

   ejM :: Matriz Int
   ejM = listArray ((1,1),(2,4)) [1,2,3,0,4,5,6,7]

1 2	ejM :: Matriz Int ejM = listArray ((1,1),(2,4)) [1,2,3,0,4,5,6,7]

representa la matriz

   |1 2 3 0|
   |4 5 6 7|

1 2	\|1 2 3 0\| \|4 5 6 7\|

Definir la función

   ampliada :: Num a => Matriz a -> Matriz a

1	ampliada :: Num a => Matriz a -> Matriz a

tal que (ampliada p) es la matriz obtenida al añadir una nueva fila a p cuyo elemento i-ésimo es la suma de la columna i-ésima de p. Por ejemplo,

   |1 2 3 0|        |1 2 3 0|
   |4 5 6 7| ==>    |4 5 6 7| 
                    |5 7 9 7|

|1 2 3 0| |1 2 3 0|

|4 5 6 7| ==> |4 5 6 7|

|5 7 9 7|

En Haskell,

   ghci> ampliada ejM
   array ((1,1),(3,4)) [((1,1),1),((1,2),2),((1,3),3),((1,4),0),
                        ((2,1),4),((2,2),5),((2,3),6),((2,4),7),
                        ((3,1),5),((3,2),7),((3,3),9),((3,4),7)]

ghci> ampliada ejM

array ((1,1),(3,4)) [((1,1),1),((1,2),2),((1,3),3),((1,4),0),

((2,1),4),((2,2),5),((2,3),6),((2,4),7),

((3,1),5),((3,2),7),((3,3),9),((3,4),7)]

Soluciones

import Data.Array

type Matriz a = Array (Int,Int) a

ejM :: Matriz Int
ejM = listArray ((1,1),(2,4)) [1,2,3,0,4,5,6,7]

ampliada :: Num a => Matriz a -> Matriz a
ampliada p = 
    array ((1,1),(m+1,n)) [((i,j),f i j) | i <- [1..m+1], j <- [1..n]]
    where (_,(m,n)) = bounds p
          f i j | i <= m    = p!(i,j)
                | otherwise = sum [p!(i,j) | i <- [1..m]]

import Data.Array

type Matriz a = Array (Int,Int) a

ejM :: Matriz Int

ejM = listArray ((1,1),(2,4)) [1,2,3,0,4,5,6,7]

ampliada :: Num a => Matriz a -> Matriz a

ampliada p =

array ((1,1),(m+1,n)) [((i,j),f i j) | i <- [1..m+1], j <- [1..n]]

where (_,(m,n)) = bounds p

f i j | i <= m = p!(i,j)

| otherwise = sum [p!(i,j) | i <- [1..m]]

Números de suma prima hereditarios por la derecha

PorJosé A. Alonso 27-marzo-20151-mayo-2015

Decimos que un número es de suma prima si la suma de todos sus dígitos es un número primo. Por ejemplo el número 562 es de suma prima pues la suma de sus dígitos es el número primo 13; sin embargo, el número 514 no es de suma prima pues la suma de sus dígitos es 10, que no es primo.

Decimos que un número es de suma prima hereditario por la derecha si es de suma prima y los números que se obtienen eliminando sus últimas cifras también son de suma prima. Por ejemplo 7426 es de suma prima hereditario por la derecha pues 7426, 742, 74 y 7 son todos números de suma prima.

Definir la constante

   listaSumaPrimaHD :: [Integer]

1	listaSumaPrimaHD :: [Integer]

cuyo valor es la lista infinita de los números de suma prima hereditarios por la derecha. Por ejemplo,

   take 10 listaSumaPrimaHD     ==  [2,3,5,7,20,21,23,25,29,30]
   listaSumaPrimaHD !! 2000000  ==  3800024668046

1 2	take 10 listaSumaPrimaHD == [2,3,5,7,20,21,23,25,29,30] listaSumaPrimaHD !! 2000000 == 3800024668046

Soluciones

import Data.Char (digitToInt)
import Data.Array
import Data.Numbers.Primes (isPrime)

-- 1ª definición
-- =============

listaSumaPrimaHD1 :: [Integer]
listaSumaPrimaHD1 = filter sumaPrimaHD [1..]

-- (sumaPrimaHD n) se verifica si n es de suma prima hereditario por la
-- derecha. Por ejemplo,
--    sumaPrimaHD 7426  ==  True
--    sumaPrimaHD 7427  ==  False
sumaPrimaHD n
    | n < 10    = isPrime n
    | otherwise = sumaPrima n && sumaPrimaHD (n `div` 10)

-- (sumaPrima n) se verifica si n es un número de suma prima. Por
-- ejemplo, 
--    sumaPrima 562  ==  True
--    sumaPrima 514  ==  False
sumaPrima :: Integer -> Bool
sumaPrima = isPrime . sum . digitos

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos = map (fromIntegral . digitToInt) . show


-- 2ª definición
-- =============

listaSumaPrimaHD2 :: [Integer]
listaSumaPrimaHD2 = map fst paresSumaPrimaHDDigitos

paresSumaPrimaHDDigitos :: [(Integer, Integer)]
paresSumaPrimaHDDigitos =
    paresSumaPrimaHDDigitosAux 1 [(2,2),(3,3),(5,5),(7,7)]

paresSumaPrimaHDDigitosAux :: Integer -> [(Integer,Integer)] -> 
                              [(Integer,Integer)]
paresSumaPrimaHDDigitosAux n ac =
    ac ++ paresSumaPrimaHDDigitosAux (n+1) 
                                     (concatMap extiendeSumaPrimaHD ac)

extiendeSumaPrimaHD :: (Integer,Integer) -> [(Integer,Integer)]
extiendeSumaPrimaHD (n,s) = [(n*10+k,s+k) | k <- [0..9], isPrime (s+k)]

-- 3ª definición
-- =============

listaSumaPrimaHD3 :: [Integer]
listaSumaPrimaHD3 = 
    map fst (concat (iterate (concatMap extiendeSumaPrimaHD3) 
                             [(2,2),(3,3),(5,5),(7,7)]))

extiendeSumaPrimaHD3 :: (Integer,Integer) -> [(Integer,Integer)]
extiendeSumaPrimaHD3 (n,s) = [(n*10+k,s+k) | k <- extensiones ! s]

extensiones :: Array Integer [Integer]
extensiones = array (1,1000) 
              [(n,[k | k <- [0..9], isPrime (n+k)]) | n <- [1..1000]]

-- Comparación de eficiencia
-- =========================

--    ghci> listaSumaPrimaHD1 !! 600
--    34004
--    (2.47 secs, 1565301720 bytes)
--    ghci> listaSumaPrimaHD2 !! 600
--    34004
--    (0.02 secs, 7209000 bytes)
--    ghci> listaSumaPrimaHD3 !! 600
--    34004
--    (0.01 secs, 1579920 bytes)
-- 
--    ghci> listaSumaPrimaHD2 !! 2000000
--    3800024668046
--    (45.41 secs, 29056613824 bytes)
--    ghci> listaSumaPrimaHD3 !! 2000000
--    3800024668046
--    (4.29 secs, 973265400 bytes)

import Data.Char (digitToInt)

import Data.Array

import Data.Numbers.Primes (isPrime)

-- 1ª definición

-- =============

listaSumaPrimaHD1 :: [Integer]

listaSumaPrimaHD1 = filter sumaPrimaHD [1..]

-- (sumaPrimaHD n) se verifica si n es de suma prima hereditario por la

-- derecha. Por ejemplo,

-- sumaPrimaHD 7426 == True

-- sumaPrimaHD 7427 == False

sumaPrimaHD n

| n < 10 = isPrime n

| otherwise = sumaPrima n && sumaPrimaHD (n `div` 10)

-- (sumaPrima n) se verifica si n es un número de suma prima. Por

-- ejemplo,

-- sumaPrima 562 == True

-- sumaPrima 514 == False

sumaPrima :: Integer -> Bool

sumaPrima = isPrime . sum . digitos

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 325 == [3,2,5]

digitos :: Integer -> [Integer]

digitos = map (fromIntegral . digitToInt) . show

-- 2ª definición

-- =============

listaSumaPrimaHD2 :: [Integer]

listaSumaPrimaHD2 = map fst paresSumaPrimaHDDigitos

paresSumaPrimaHDDigitos :: [(Integer, Integer)]

paresSumaPrimaHDDigitos =

paresSumaPrimaHDDigitosAux 1 [(2,2),(3,3),(5,5),(7,7)]

paresSumaPrimaHDDigitosAux :: Integer -> [(Integer,Integer)] ->

[(Integer,Integer)]

paresSumaPrimaHDDigitosAux n ac =

ac ++ paresSumaPrimaHDDigitosAux (n+1)

(concatMap extiendeSumaPrimaHD ac)

extiendeSumaPrimaHD :: (Integer,Integer) -> [(Integer,Integer)]

extiendeSumaPrimaHD (n,s) = [(n*10+k,s+k) | k <- [0..9], isPrime (s+k)]

-- 3ª definición

-- =============

listaSumaPrimaHD3 :: [Integer]

listaSumaPrimaHD3 =

map fst (concat (iterate (concatMap extiendeSumaPrimaHD3)

[(2,2),(3,3),(5,5),(7,7)]))

extiendeSumaPrimaHD3 :: (Integer,Integer) -> [(Integer,Integer)]

extiendeSumaPrimaHD3 (n,s) = [(n*10+k,s+k) | k <- extensiones ! s]

extensiones :: Array Integer [Integer]

extensiones = array (1,1000)

[(n,[k | k <- [0..9], isPrime (n+k)]) | n <- [1..1000]]

-- Comparación de eficiencia

-- =========================

-- ghci> listaSumaPrimaHD1 !! 600

-- 34004

-- (2.47 secs, 1565301720 bytes)

-- ghci> listaSumaPrimaHD2 !! 600

-- 34004

-- (0.02 secs, 7209000 bytes)

-- ghci> listaSumaPrimaHD3 !! 600

-- 34004

-- (0.01 secs, 1579920 bytes)

-- ghci> listaSumaPrimaHD2 !! 2000000

-- 3800024668046

-- (45.41 secs, 29056613824 bytes)

-- ghci> listaSumaPrimaHD3 !! 2000000

-- 3800024668046

-- (4.29 secs, 973265400 bytes)

La sucesión de Sylvester

Soluciones

Codificación matricial

Soluciones

Relleno de matrices

Soluciones

Referencias

Ampliación de una matriz sumando sus filas

Soluciones

Números de suma prima hereditarios por la derecha

Soluciones

Entradas recientes

Buscar

Correo electrónico