repeat

Índices de valores verdaderos

PorJosé A. Alonso 12-abril-202211-abril-2022

Definir la función

   indicesVerdaderos :: [Int] -> [Bool]

1	indicesVerdaderos :: [Int] -> [Bool]

tal que (indicesVerdaderos xs) es la lista infinita de booleanos tal que sólo son verdaderos los elementos cuyos índices pertenecen a la lista estrictamente creciente xs. Por ejemplo,

   λ> take 6 (indicesVerdaderos [1,4])
   [False,True,False,False,True,False]
   λ> take 6 (indicesVerdaderos [0,2..])
   [True,False,True,False,True,False]
   λ> take 3 (indicesVerdaderos [])
   [False,False,False]
   λ> take 6 (indicesVerdaderos [1..])
   [False,True,True,True,True,True]
   λ> last (take (8*10^7) (indicesVerdaderos [0,5..]))
   False

λ> take 6 (indicesVerdaderos [1,4])

[False,True,False,False,True,False]

λ> take 6 (indicesVerdaderos [0,2..])

[True,False,True,False,True,False]

λ> take 3 (indicesVerdaderos [])

[False,False,False]

λ> take 6 (indicesVerdaderos [1..])

[False,True,True,True,True,True]

λ> last (take (8*10^7) (indicesVerdaderos [0,5..]))

False

Soluciones

[schedule expon=’2022-04-19′ expat=»06:00″]

Las soluciones se pueden escribir en los comentarios.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

[/schedule]

[schedule on=’2022-04-19′ at=»06:00″]

import Data.List.Ordered (member)
import Test.QuickCheck

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

indicesVerdaderos1 :: [Int] -> [Bool]
indicesVerdaderos1 []     = repeat False
indicesVerdaderos1 (x:ys) =
  replicate x False ++ [True] ++ indicesVerdaderos1 [y-x-1 | y <- ys]

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

indicesVerdaderos2 :: [Int] -> [Bool]
indicesVerdaderos2 = aux 0
  where aux _ []     = repeat False
        aux n (x:xs) | x == n    = True  : aux (n+1) xs
                     | otherwise = False : aux (n+1) (x:xs)

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

indicesVerdaderos3 :: [Int] -> [Bool]
indicesVerdaderos3 = aux [0..]
  where aux _      []                 = repeat False
        aux (i:is) (x:xs) | i == x    = True  : aux is xs
                          | otherwise = False : aux is (x:xs)

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

indicesVerdaderos4 :: [Int] -> [Bool]
indicesVerdaderos4 xs = [pertenece x xs | x <- [0..]]

-- (pertenece x ys) se verifica si x pertenece a la lista estrictamente
-- creciente (posiblemente infinita) ys. Por ejemplo,
--    pertenece 9 [1,3..]  ==  True
--    pertenece 6 [1,3..]  ==  False
pertenece :: Int -> [Int] -> Bool
pertenece x ys = x `elem` takeWhile (<=x) ys

-- 5ª solución
-- ===========

indicesVerdaderos5 :: [Int] -> [Bool]
indicesVerdaderos5 xs = map (`pertenece2` xs) [0..]

pertenece2 :: Int -> [Int] -> Bool
pertenece2 x = aux
  where aux [] = False
        aux (y:ys) = case compare x y of
                       LT -> False
                       EQ -> True
                       GT -> aux ys

-- 6ª solución
-- ===========

indicesVerdaderos6 :: [Int] -> [Bool]
indicesVerdaderos6 xs = map (`member` xs) [0..]

-- Comprobación de equivalencia
-- ============================

-- ListaCreciente es un tipo de dato para generar lista de enteros
-- crecientes arbitrarias.
newtype ListaCreciente = LC [Int]
  deriving Show

-- listaCrecienteArbitraria es un generador de lista de enteros
-- crecientes arbitrarias. Por ejemplo,
--    λ> sample listaCrecienteArbitraria
--    LC []
--    LC [2,5]
--    LC [4,8]
--    LC [6,13]
--    LC [7,15,20,28,33]
--    LC [11,15,20,29,35,40]
--    LC [5,17,25,36,42,50,52,64]
--    LC [9,16,31,33,46,59,74,83,85,89,104,113,118]
--    LC [9,22,29,35,37,49,53,62,68,77,83,100]
--    LC []
--    LC [3,22,25,34,36,51,72,75,89]
listaCrecienteArbitraria :: Gen ListaCreciente
listaCrecienteArbitraria = do
  xs <- arbitrary
  return (LC (listaCreciente xs))

-- (listaCreciente xs) es la lista creciente correspondiente a xs. Por ejemplo,
--    listaCreciente [-1,3,-4,3,0]   ==  [2,6,11,15,16]
listaCreciente :: [Int] -> [Int]
listaCreciente xs =
  scanl1 (+) (map (succ . abs) xs)

-- ListaCreciente está contenida en Arbitrary
instance Arbitrary ListaCreciente where
  arbitrary = listaCrecienteArbitraria

-- La propiedad es
prop_indicesVerdaderos :: ListaCreciente -> Bool
prop_indicesVerdaderos (LC xs) =
  all (== take n (indicesVerdaderos1 xs))
      [take n (f xs) | f <-[indicesVerdaderos2,
                            indicesVerdaderos3,
                            indicesVerdaderos4,
                            indicesVerdaderos5,
                            indicesVerdaderos6]]
  where n = length xs

-- La comprobación es
--    λ> quickCheck prop_indicesVerdaderos
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> last (take (2*10^4) (indicesVerdaderos1 [0,5..]))
--    False
--    (2.69 secs, 2,611,031,544 bytes)
--    λ> last (take (2*10^4) (indicesVerdaderos2 [0,5..]))
--    False
--    (0.03 secs, 10,228,880 bytes)
--
--    λ> last (take (4*10^6) (indicesVerdaderos2 [0,5..]))
--    False
--    (2.37 secs, 1,946,100,856 bytes)
--    λ> last (take (4*10^6) (indicesVerdaderos3 [0,5..]))
--    False
--    (1.54 secs, 1,434,100,984 bytes)
--
--    λ> last (take (6*10^6) (indicesVerdaderos3 [0,5..]))
--    False
--    (2.30 secs, 2,150,900,984 bytes)
--    λ> last (take (6*10^6) (indicesVerdaderos4 [0,5..]))
--    False
--    (1.55 secs, 1,651,701,184 bytes)
--    λ> last (take (6*10^6) (indicesVerdaderos5 [0,5..]))
--    False
--    (0.58 secs, 1,584,514,304 bytes)
--
--    λ> last (take (3*10^7) (indicesVerdaderos5 [0,5..]))
--    False
--    (2.74 secs, 7,920,514,360 bytes)
--    λ> last (take (3*10^7) (indicesVerdaderos6 [0,5..]))
--    False
--    (0.82 secs, 6,960,514,136 bytes)

--    λ> last (take (2*10^4) (indicesVerdaderos1 [0,5..]))
--    False
--    (2.69 secs, 2,611,031,544 bytes)
--    λ> last (take (2*10^4) (indicesVerdaderos6 [0,5..]))
--    False
--    (0.01 secs, 5,154,040 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

import Data.List.Ordered (member)

import Test.QuickCheck

-- 1ª solución

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

indicesVerdaderos1 :: [Int] -> [Bool]

indicesVerdaderos1 [] = repeat False

indicesVerdaderos1 (x:ys) =

replicate x False ++ [True] ++ indicesVerdaderos1 [y-x-1 | y <- ys]

-- 2ª solución

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

indicesVerdaderos2 :: [Int] -> [Bool]

indicesVerdaderos2 = aux 0

where aux _ [] = repeat False

aux n (x:xs) | x == n = True : aux (n+1) xs

| otherwise = False : aux (n+1) (x:xs)

-- 3ª solución

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

indicesVerdaderos3 :: [Int] -> [Bool]

indicesVerdaderos3 = aux [0..]

where aux _ [] = repeat False

aux (i:is) (x:xs) | i == x = True : aux is xs

| otherwise = False : aux is (x:xs)

-- 4ª solución

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

indicesVerdaderos4 :: [Int] -> [Bool]

indicesVerdaderos4 xs = [pertenece x xs | x <- [0..]]

-- (pertenece x ys) se verifica si x pertenece a la lista estrictamente

-- creciente (posiblemente infinita) ys. Por ejemplo,

-- pertenece 9 [1,3..] == True

-- pertenece 6 [1,3..] == False

pertenece :: Int -> [Int] -> Bool

pertenece x ys = x `elem` takeWhile (<=x) ys

-- 5ª solución

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

indicesVerdaderos5 :: [Int] -> [Bool]

indicesVerdaderos5 xs = map (`pertenece2` xs) [0..]

pertenece2 :: Int -> [Int] -> Bool

pertenece2 x = aux

where aux [] = False

aux (y:ys) = case compare x y of

LT -> False

EQ -> True

GT -> aux ys

-- 6ª solución

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

indicesVerdaderos6 :: [Int] -> [Bool]

indicesVerdaderos6 xs = map (`member` xs) [0..]

-- Comprobación de equivalencia

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

-- ListaCreciente es un tipo de dato para generar lista de enteros

-- crecientes arbitrarias.

newtype ListaCreciente = LC [Int]

deriving Show

-- listaCrecienteArbitraria es un generador de lista de enteros

-- crecientes arbitrarias. Por ejemplo,

-- λ> sample listaCrecienteArbitraria

-- LC []

-- LC [2,5]

-- LC [4,8]

-- LC [6,13]

-- LC [7,15,20,28,33]

-- LC [11,15,20,29,35,40]

-- LC [5,17,25,36,42,50,52,64]

-- LC [9,16,31,33,46,59,74,83,85,89,104,113,118]

-- LC [9,22,29,35,37,49,53,62,68,77,83,100]

-- LC []

-- LC [3,22,25,34,36,51,72,75,89]

listaCrecienteArbitraria :: Gen ListaCreciente

listaCrecienteArbitraria = do

xs <- arbitrary

return (LC (listaCreciente xs))

-- (listaCreciente xs) es la lista creciente correspondiente a xs. Por ejemplo,

-- listaCreciente [-1,3,-4,3,0] == [2,6,11,15,16]

listaCreciente :: [Int] -> [Int]

listaCreciente xs =

scanl1 (+) (map (succ . abs) xs)

-- ListaCreciente está contenida en Arbitrary

instance Arbitrary ListaCreciente where

arbitrary = listaCrecienteArbitraria

-- La propiedad es

prop_indicesVerdaderos :: ListaCreciente -> Bool

prop_indicesVerdaderos (LC xs) =

all (== take n (indicesVerdaderos1 xs))

[take n (f xs) | f <-[indicesVerdaderos2,

indicesVerdaderos3,

indicesVerdaderos4,

indicesVerdaderos5,

indicesVerdaderos6]]

where n = length xs

-- La comprobación es

-- λ> quickCheck prop_indicesVerdaderos

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> last (take (2*10^4) (indicesVerdaderos1 [0,5..]))

-- False

-- (2.69 secs, 2,611,031,544 bytes)

-- λ> last (take (2*10^4) (indicesVerdaderos2 [0,5..]))

-- False

-- (0.03 secs, 10,228,880 bytes)

-- λ> last (take (4*10^6) (indicesVerdaderos2 [0,5..]))

-- False

-- (2.37 secs, 1,946,100,856 bytes)

-- λ> last (take (4*10^6) (indicesVerdaderos3 [0,5..]))

-- False

-- (1.54 secs, 1,434,100,984 bytes)

-- λ> last (take (6*10^6) (indicesVerdaderos3 [0,5..]))

-- False

-- (2.30 secs, 2,150,900,984 bytes)

-- λ> last (take (6*10^6) (indicesVerdaderos4 [0,5..]))

-- False

-- (1.55 secs, 1,651,701,184 bytes)

-- λ> last (take (6*10^6) (indicesVerdaderos5 [0,5..]))

-- False

-- (0.58 secs, 1,584,514,304 bytes)

-- λ> last (take (3*10^7) (indicesVerdaderos5 [0,5..]))

-- False

-- (2.74 secs, 7,920,514,360 bytes)

-- λ> last (take (3*10^7) (indicesVerdaderos6 [0,5..]))

-- False

-- (0.82 secs, 6,960,514,136 bytes)

-- λ> last (take (2*10^4) (indicesVerdaderos1 [0,5..]))

-- False

-- (2.69 secs, 2,611,031,544 bytes)

-- λ> last (take (2*10^4) (indicesVerdaderos6 [0,5..]))

-- False

-- (0.01 secs, 5,154,040 bytes)

El código se encuentra en [GitHub](https://github.com/jaalonso/Exercitium/blob/main/src/Indices_verdaderos.hs).

La elaboración de las soluciones se describe en el siguiente vídeo

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>

[/schedule]

Distribución de diferencias de dígitos consecutivos de pi

PorJosé A. Alonso 4-abril-201911-abril-2019

Usando la librería Data.Number.CReal, que se instala con

   cabal install number

1	cabal install number

se pueden calcular el número pi con la precisión que se desee. Por ejemplo,

   λ> import Data.Number.CReal
   λ> showCReal 60 pi
   "3.141592653589793238462643383279502884197169399375105820974945"

λ> import Data.Number.CReal

λ> showCReal 60 pi

"3.141592653589793238462643383279502884197169399375105820974945"

importa la librería y calcula el número pi con 60 decimales.

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros n dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

   3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

1	3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

Las diferencias de sus elementos consecutivos es

   2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

1	2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

y la distribución de sus frecuencias en el intervalo [-9,9] es

   0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

1	0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

   distribucionDDCpi :: Int -> [Int]
   graficas :: [Int] -> FilePath -> IO ()

1 2	distribucionDDCpi :: Int -> [Int] graficas :: [Int] -> FilePath -> IO ()

tales que

(distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,

     λ> distribucionDDCpi 18
     [0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]
     λ> distribucionDDCpi 100
     [1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]
     λ> distribucionDDCpi 200
     [3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]
     λ> distribucionDDCpi 1000
     [16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]
     λ> distribucionDDCpi 5000
     [67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

λ> distribucionDDCpi 18

[0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]

λ> distribucionDDCpi 100

[1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]

λ> distribucionDDCpi 200

[3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]

λ> distribucionDDCpi 1000

[16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]

λ> distribucionDDCpi 5000

[67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

(graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] «distribucionDDCpi.png» se escribe en el fichero «distribucionDDCpi.png» la siguiente gráfica

Soluciones

import Data.Number.CReal
import Graphics.Gnuplot.Simple
import Data.Array

--    λ> digitosPi 18
--    [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3]
digitosPi :: Int -> [Int]
digitosPi n = init [read [c] | c <- (x:xs)]
  where (x:_:xs) = showCReal n pi

--    λ> diferenciasConsecutivos (digitosPi 18)
--    [2,-3,3,-4,-4,7,-4,1,2,-2,-3,-1,2,-2,6,1,-1]
diferenciasConsecutivos :: Num a => [a] -> [a]
diferenciasConsecutivos xs =
  zipWith (-) xs (tail xs)

distribucionDDCpi :: Int -> [Int]
distribucionDDCpi =
  distribucion . diferenciasConsecutivos . digitosPi
  where distribucion xs =
          elems (accumArray (+) 0 (-9,9) (zip xs (repeat 1)))

graficas :: [Int] -> FilePath -> IO ()
graficas ns f = 
  plotLists [Key Nothing, PNG f]
            [puntos n | n <- ns]
  where puntos :: Int -> [(Int,Int)]
        puntos n = zip [-9..9] (distribucionDDCpi n)

import Data.Number.CReal

import Graphics.Gnuplot.Simple

import Data.Array

-- λ> digitosPi 18

-- [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3]

digitosPi :: Int -> [Int]

digitosPi n = init [read [c] | c <- (x:xs)]

where (x:_:xs) = showCReal n pi

-- λ> diferenciasConsecutivos (digitosPi 18)

-- [2,-3,3,-4,-4,7,-4,1,2,-2,-3,-1,2,-2,6,1,-1]

diferenciasConsecutivos :: Num a => [a] -> [a]

diferenciasConsecutivos xs =

zipWith (-) xs (tail xs)

distribucionDDCpi :: Int -> [Int]

distribucionDDCpi =

distribucion . diferenciasConsecutivos . digitosPi

where distribucion xs =

elems (accumArray (+) 0 (-9,9) (zip xs (repeat 1)))

graficas :: [Int] -> FilePath -> IO ()

graficas ns f =

plotLists [Key Nothing, PNG f]

[puntos n | n <- ns]

where puntos :: Int -> [(Int,Int)]

puntos n = zip [-9..9] (distribucionDDCpi n)

Pensamiento

Doy consejo, a fuer de viejo:
nunca sigas mi consejo.

Antonio Machado

Sucesión de Recamán

PorJosé A. Alonso 11-mayo-201826-marzo-2022

La sucesión de Recamán está definida como sigue:

   a(0) = 0
   a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión
   a(n) = a(n-1) + n, en caso contrario.

a(0) = 0

a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión

a(n) = a(n-1) + n, en caso contrario.

Definir las funciones

   sucRecaman :: [Int]
   invRecaman :: Int -> Int
   graficaSucRecaman :: Int -> IO ()
   graficaInvRecaman :: Int -> IO ()

sucRecaman :: [Int]

invRecaman :: Int -> Int

graficaSucRecaman :: Int -> IO ()

graficaInvRecaman :: Int -> IO ()

tales que

sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,

      λ> take 25 sucRecaman3
      [0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]
      λ> sucRecaman !! 1000
      3686
      λ> sucRecaman !! 1000001
      1057163

λ> take 25 sucRecaman3

[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]

λ> sucRecaman !! 1000

3686

λ> sucRecaman !! 1000001

1057163

(invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,

      invRecaman 10       ==  12
      invRecaman 3686     ==  1000
      invRecaman 1057163  ==  1000001

invRecaman 10 == 12

invRecaman 3686 == 1000

invRecaman 1057163 == 1000001

(graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja
(graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja

y (graficaInvRecaman 100) dibuja

Soluciones

import qualified Data.Set as S

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

sucRecaman1 :: [Int]
sucRecaman1 = map suc1 [0..]

suc1 :: Int -> Int
suc1 0 = 0
suc1 n | y > n && y - n `notElem` ys = y - n
       | otherwise                   = y + n
  where y  = suc1 (n - 1)
        ys = [suc1 k | k <- [0..n - 1]]

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

sucRecaman2 :: [Int]
sucRecaman2 = 0:zipWith3 f sucRecaman2 [1..] (repeat sucRecaman2)
  where f y n ys | y > n && y - n `notElem` take n ys = y - n
                 | otherwise                          = y + n

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

sucRecaman3 :: [Int]
sucRecaman3 = 0 : recaman (S.singleton 0) 1 0

recaman :: S.Set Int -> Int -> Int -> [Int]
recaman s n x
  | x > n && (x-n) `S.notMember` s =
    (x-n) : recaman (S.insert (x-n) s) (n+1) (x-n)
  | otherwise =
    (x+n):recaman (S.insert (x+n) s) (n+1) (x+n) 

-- Comparación de eficiencia:
--    λ> sucRecaman1 !! 25
--    17
--    (3.76 secs, 2,394,593,952 bytes)
--    λ> sucRecaman2 !! 25
--    17
--    (0.00 secs, 0 bytes)
--    λ> sucRecaman3 !! 25
--    17
--    (0.00 secs, 0 bytes)
--
--    λ> sucRecaman2 !! (2*10^4)
--    14358
--    (2.69 secs, 6,927,559,784 bytes)
--    λ> sucRecaman3 !! (2*10^4)
--    14358
--    (0.04 secs, 0 bytes)

-- Definición de invRecaman
invRecaman :: Int -> Int
invRecaman n =
  length (takeWhile (/=n) sucRecaman3)

graficaSucRecaman :: Int -> IO ()
graficaSucRecaman n =
  plotList [Key Nothing]
           (take n sucRecaman3)

graficaInvRecaman :: Int -> IO ()
graficaInvRecaman n =
  plotList [Key Nothing]
           [invRecaman k | k <- [0..n]]

import qualified Data.Set as S

-- 1ª solución

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

sucRecaman1 :: [Int]

sucRecaman1 = map suc1 [0..]

suc1 :: Int -> Int

suc1 0 = 0

suc1 n | y > n && y - n `notElem` ys = y - n

| otherwise = y + n

where y = suc1 (n - 1)

ys = [suc1 k | k <- [0..n - 1]]

-- 2ª solución

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

sucRecaman2 :: [Int]

sucRecaman2 = 0:zipWith3 f sucRecaman2 [1..] (repeat sucRecaman2)

where f y n ys | y > n && y - n `notElem` take n ys = y - n

| otherwise = y + n

-- 3ª solución

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

sucRecaman3 :: [Int]

sucRecaman3 = 0 : recaman (S.singleton 0) 1 0

recaman :: S.Set Int -> Int -> Int -> [Int]

recaman s n x

| x > n && (x-n) `S.notMember` s =

(x-n) : recaman (S.insert (x-n) s) (n+1) (x-n)

| otherwise =

(x+n):recaman (S.insert (x+n) s) (n+1) (x+n)

-- Comparación de eficiencia:

-- λ> sucRecaman1 !! 25

-- 17

-- (3.76 secs, 2,394,593,952 bytes)

-- λ> sucRecaman2 !! 25

-- 17

-- (0.00 secs, 0 bytes)

-- λ> sucRecaman3 !! 25

-- 17

-- (0.00 secs, 0 bytes)

-- λ> sucRecaman2 !! (2*10^4)

-- 14358

-- (2.69 secs, 6,927,559,784 bytes)

-- λ> sucRecaman3 !! (2*10^4)

-- 14358

-- (0.04 secs, 0 bytes)

-- Definición de invRecaman

invRecaman :: Int -> Int

invRecaman n =

length (takeWhile (/=n) sucRecaman3)

graficaSucRecaman :: Int -> IO ()

graficaSucRecaman n =

plotList [Key Nothing]

(take n sucRecaman3)

graficaInvRecaman :: Int -> IO ()

graficaInvRecaman n =

plotList [Key Nothing]

[invRecaman k | k <- [0..n]]

Matrices de Pascal

PorJosé A. Alonso 9-marzo-201816-marzo-2018

El triángulo de Pascal es un triángulo de números

         1
        1 1
       1 2 1
     1  3 3  1
    1 4  6  4 1
   1 5 10 10 5 1
  ...............

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

...............

construido de la siguiente forma

la primera fila está formada por el número 1;
las filas siguientes se construyen sumando los números adyacentes de la fila superior y añadiendo un 1 al principio y al final de la fila.

La matriz de Pascal es la matriz cuyas filas son los elementos de la
correspondiente fila del triángulo de Pascal completadas con ceros. Por ejemplo, la matriz de Pascal de orden 6 es

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

|1 0 0 0 0 0|

|1 1 0 0 0 0|

|1 2 1 0 0 0|

|1 3 3 1 0 0|

|1 4 6 4 1 0|

|1 5 10 10 5 1|

Definir la función

   matrizPascal :: Int -> Matrix Integer

1	matrizPascal :: Int -> Matrix Integer

tal que (matrizPascal n) es la matriz de Pascal de orden n. Por ejemplo,

   λ> matrizPascal 6
   (  1  0  0  0  0  0 )
   (  1  1  0  0  0  0 )
   (  1  2  1  0  0  0 )
   (  1  3  3  1  0  0 )
   (  1  4  6  4  1  0 )
   (  1  5 10 10  5  1 )

λ> matrizPascal 6

( 1 0 0 0 0 0 )

( 1 1 0 0 0 0 )

( 1 2 1 0 0 0 )

( 1 3 3 1 0 0 )

( 1 4 6 4 1 0 )

( 1 5 10 10 5 1 )

Soluciones

import Data.Matrix

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

matrizPascal :: Int -> Matrix Integer 
matrizPascal 1 = fromList 1 1 [1]
matrizPascal n = matrix n n f 
  where f (i,j) | i < n && j <  n  = p!(i,j)
                | i < n && j == n  = 0
                | j == 1 || j == n = 1
                | otherwise        = p!(i-1,j-1) + p!(i-1,j)
        p = matrizPascal (n-1)

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

matrizPascal2 :: Int -> Matrix Integer
matrizPascal2 n = fromLists xss
  where yss = take n pascal
        xss = map (take n) (map (++ repeat 0) yss)
        
pascal :: [[Integer]]
pascal = [1] : map f pascal
    where f xs = zipWith (+) (0:xs) (xs ++ [0])

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

matrizPascal3 :: Int -> Matrix Integer
matrizPascal3 n =  matrix n n f
  where f (i,j) | i >=  j   = comb (i-1) (j-1)
                | otherwise = 0

-- (comb n k) es el número de combinaciones (o coeficiente binomial) de
-- n sobre k. Por ejemplo,
comb :: Int -> Int -> Integer
comb n k = product [n',n'-1..n'-k'+1] `div` product [1..k']
  where n' = fromIntegral n
        k' = fromIntegral k

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

matrizPascal4 :: Int -> Matrix Integer
matrizPascal4 n = p
  where p = matrix n n (\(i,j) -> f i j)
        f i 1 = 1
        f i j
          | j >  i    = 0
          | i == j    = 1
          | otherwise = p!(i-1,j) + p!(i-1,j-1)

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

--    λ> maximum (matrizPascal 150)
--    46413034868354394849492907436302560970058760
--    (2.58 secs, 394,030,504 bytes)
--    λ> maximum (matrizPascal2 150)
--    46413034868354394849492907436302560970058760
--    (0.03 secs, 8,326,784 bytes)
--    λ> maximum (matrizPascal3 150)
--    46413034868354394849492907436302560970058760
--    (0.38 secs, 250,072,360 bytes)
--    λ> maximum (matrizPascal4 150)
--    46413034868354394849492907436302560970058760
--    (0.10 secs, 13,356,360 bytes)
--    
--    λ> length (show (maximum (matrizPascal2 300)))
--    89
--    (0.06 secs, 27,286,296 bytes)
--    λ> length (show (maximum (matrizPascal3 300)))
--    89
--    (2.74 secs, 2,367,037,536 bytes)
--    λ> length (show (maximum (matrizPascal4 300)))
--    89
--    (0.36 secs, 53,934,792 bytes)
--    
--    λ> length (show (maximum (matrizPascal2 700)))
--    209
--    (0.83 secs, 207,241,080 bytes)
--    λ> length (show (maximum (matrizPascal4 700)))
--    209
--    (2.22 secs, 311,413,008 bytes)

import Data.Matrix

-- 1ª solución

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

matrizPascal :: Int -> Matrix Integer

matrizPascal 1 = fromList 1 1 [1]

matrizPascal n = matrix n n f

where f (i,j) | i < n && j < n = p!(i,j)

| i < n && j == n = 0

| j == 1 || j == n = 1

| otherwise = p!(i-1,j-1) + p!(i-1,j)

p = matrizPascal (n-1)

-- 2ª solución

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

matrizPascal2 :: Int -> Matrix Integer

matrizPascal2 n = fromLists xss

where yss = take n pascal

xss = map (take n) (map (++ repeat 0) yss)

pascal :: [[Integer]]

pascal = [1] : map f pascal

where f xs = zipWith (+) (0:xs) (xs ++ [0])

-- 3ª solución

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

matrizPascal3 :: Int -> Matrix Integer

matrizPascal3 n = matrix n n f

where f (i,j) | i >= j = comb (i-1) (j-1)

| otherwise = 0

-- (comb n k) es el número de combinaciones (o coeficiente binomial) de

-- n sobre k. Por ejemplo,

comb :: Int -> Int -> Integer

comb n k = product [n',n'-1..n'-k'+1] `div` product [1..k']

where n' = fromIntegral n

k' = fromIntegral k

-- 4ª solución

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

matrizPascal4 :: Int -> Matrix Integer

matrizPascal4 n = p

where p = matrix n n (\(i,j) -> f i j)

f i 1 = 1

f i j

| j > i = 0

| i == j = 1

| otherwise = p!(i-1,j) + p!(i-1,j-1)

-- Comparación de eficiencia

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

-- λ> maximum (matrizPascal 150)

-- 46413034868354394849492907436302560970058760

-- (2.58 secs, 394,030,504 bytes)

-- λ> maximum (matrizPascal2 150)

-- 46413034868354394849492907436302560970058760

-- (0.03 secs, 8,326,784 bytes)

-- λ> maximum (matrizPascal3 150)

-- 46413034868354394849492907436302560970058760

-- (0.38 secs, 250,072,360 bytes)

-- λ> maximum (matrizPascal4 150)

-- 46413034868354394849492907436302560970058760

-- (0.10 secs, 13,356,360 bytes)

-- λ> length (show (maximum (matrizPascal2 300)))

-- 89

-- (0.06 secs, 27,286,296 bytes)

-- λ> length (show (maximum (matrizPascal3 300)))

-- 89

-- (2.74 secs, 2,367,037,536 bytes)

-- λ> length (show (maximum (matrizPascal4 300)))

-- 89

-- (0.36 secs, 53,934,792 bytes)

-- λ> length (show (maximum (matrizPascal2 700)))

-- 209

-- (0.83 secs, 207,241,080 bytes)

-- λ> length (show (maximum (matrizPascal4 700)))

-- 209

-- (2.22 secs, 311,413,008 bytes)

Sucesión de Recamán

PorJosé A. Alonso 24-abril-201726-marzo-2022

La sucesión de Recamán está definida como sigue:

   a(0) = 0
   a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión
   a(n) = a(n-1) + n, en caso contrario.

a(0) = 0

a(n) = a(n-1) - n, si a(n-1) > n y no figura ya en la sucesión

a(n) = a(n-1) + n, en caso contrario.

Definir las funciones

   sucRecaman :: [Int]
   invRecaman :: Int -> Int
   graficaSucRecaman :: Int -> IO ()
   graficaInvRecaman :: Int -> IO ()

sucRecaman :: [Int]

invRecaman :: Int -> Int

graficaSucRecaman :: Int -> IO ()

graficaInvRecaman :: Int -> IO ()

tales que

sucRecaman es la lista de los términos de la sucesión de Recamám. Por ejemplo,

      λ> take 25 sucRecaman3
      [0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]
      λ> sucRecaman !! 1000
      3686
      λ> sucRecaman !! 1000001
      1057163

λ> take 25 sucRecaman3

[0,1,3,6,2,7,13,20,12,21,11,22,10,23,9,24,8,25,43,62,42,63,41,18,42]

λ> sucRecaman !! 1000

3686

λ> sucRecaman !! 1000001

1057163

(invRecaman n) es la primera posición de n en la sucesión de Recamán. Por ejemplo,

      invRecaman 10       ==  12
      invRecaman 3686     ==  1000
      invRecaman 1057163  ==  1000001

invRecaman 10 == 12

invRecaman 3686 == 1000

invRecaman 1057163 == 1000001

(graficaSucRecaman n) dibuja los n primeros términos de la sucesión de Recamán. Por ejemplo, (graficaSucRecaman 300) dibuja
(graficaInvRecaman n) dibuja los valores de (invRecaman k) para k entre 0 y n. Por ejemplo, (graficaInvRecaman 17) dibuja

y (graficaInvRecaman 100) dibuja

Soluciones

import qualified Data.Set as S

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

sucRecaman1 :: [Int]
sucRecaman1 = map suc1 [0..]

suc1 :: Int -> Int
suc1 0 = 0
suc1 n | y > n && y - n `notElem` ys = y - n
       | otherwise                   = y + n
  where y  = suc1 (n - 1)
        ys = [suc1 k | k <- [0..n - 1]]

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

sucRecaman2 :: [Int]
sucRecaman2 = 0:zipWith3 f sucRecaman2 [1..] (repeat sucRecaman2)
  where f y n ys | y > n && y - n `notElem` take n ys = y - n
                 | otherwise                          = y + n

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

sucRecaman3 :: [Int]
sucRecaman3 = 0 : recaman (S.singleton 0) 1 0

recaman :: S.Set Int -> Int -> Int -> [Int]
recaman s n x
  | x > n && (x-n) `S.notMember` s =
    (x-n) : recaman (S.insert (x-n) s) (n+1) (x-n)
  | otherwise =
    (x+n):recaman (S.insert (x+n) s) (n+1) (x+n) 

-- Comparación de eficiencia:
--    λ> sucRecaman1 !! 25
--    17
--    (3.76 secs, 2,394,593,952 bytes)
--    λ> sucRecaman2 !! 25
--    17
--    (0.00 secs, 0 bytes)
--    λ> sucRecaman3 !! 25
--    17
--    (0.00 secs, 0 bytes)
--
--    λ> sucRecaman2 !! (2*10^4)
--    14358
--    (2.69 secs, 6,927,559,784 bytes)
--    λ> sucRecaman3 !! (2*10^4)
--    14358
--    (0.04 secs, 0 bytes)

-- Definición de invRecaman
invRecaman :: Int -> Int
invRecaman n =
  length (takeWhile (/=n) sucRecaman3)

graficaSucRecaman :: Int -> IO ()
graficaSucRecaman n =
  plotList [Key Nothing]
           (take n sucRecaman3)

graficaInvRecaman :: Int -> IO ()
graficaInvRecaman n =
  plotList [Key Nothing]
           [invRecaman k | k <- [0..n]]

import qualified Data.Set as S

-- 1ª solución

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

sucRecaman1 :: [Int]

sucRecaman1 = map suc1 [0..]

suc1 :: Int -> Int

suc1 0 = 0

suc1 n | y > n && y - n `notElem` ys = y - n

| otherwise = y + n

where y = suc1 (n - 1)

ys = [suc1 k | k <- [0..n - 1]]

-- 2ª solución

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

sucRecaman2 :: [Int]

sucRecaman2 = 0:zipWith3 f sucRecaman2 [1..] (repeat sucRecaman2)

where f y n ys | y > n && y - n `notElem` take n ys = y - n

| otherwise = y + n

-- 3ª solución

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

sucRecaman3 :: [Int]

sucRecaman3 = 0 : recaman (S.singleton 0) 1 0

recaman :: S.Set Int -> Int -> Int -> [Int]

recaman s n x

| x > n && (x-n) `S.notMember` s =

(x-n) : recaman (S.insert (x-n) s) (n+1) (x-n)

| otherwise =

(x+n):recaman (S.insert (x+n) s) (n+1) (x+n)

-- Comparación de eficiencia:

-- λ> sucRecaman1 !! 25

-- 17

-- (3.76 secs, 2,394,593,952 bytes)

-- λ> sucRecaman2 !! 25

-- 17

-- (0.00 secs, 0 bytes)

-- λ> sucRecaman3 !! 25

-- 17

-- (0.00 secs, 0 bytes)

-- λ> sucRecaman2 !! (2*10^4)

-- 14358

-- (2.69 secs, 6,927,559,784 bytes)

-- λ> sucRecaman3 !! (2*10^4)

-- 14358

-- (0.04 secs, 0 bytes)

-- Definición de invRecaman

invRecaman :: Int -> Int

invRecaman n =

length (takeWhile (/=n) sucRecaman3)

graficaSucRecaman :: Int -> IO ()

graficaSucRecaman n =

plotList [Key Nothing]

(take n sucRecaman3)

graficaInvRecaman :: Int -> IO ()

graficaInvRecaman n =

plotList [Key Nothing]

[invRecaman k | k <- [0..n]]

Distancias entre primos consecutivos

PorJosé A. Alonso 4-abril-201711-abril-2017

Los 15 primeros números primos son

   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

1	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Las distancias entre los elementos consecutivos son

   1, 2, 2, 4, 2,  4,  2,  4,  6,  2,  6,  4,  2,  4

1	1, 2, 2, 4, 2, 4, 2, 4, 6, 2, 6, 4, 2, 4

La distribución de las distancias es

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

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

(es decir, el 1 aparece una vez, el 2 aparece 6 veces, etc.) La frecuencia de las distancias es

   (1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

1	(1,7.142857), (2,42.857143), (4,35.714287), (6,14.285714)

(es decir, el 1 aparece el 7.142857%, el 2 el 42.857143% etc.)

Definir las funciones

  cuentaDistancias        :: Int -> [(Int,Int)]
  frecuenciasDistancias   :: Int -> [(Int,Float)]
  graficas                :: [Int] -> IO ()
  distanciasMasFrecuentes :: Int -> [Int]

cuentaDistancias :: Int -> [(Int,Int)]

frecuenciasDistancias :: Int -> [(Int,Float)]

graficas :: [Int] -> IO ()

distanciasMasFrecuentes :: Int -> [Int]

tales que

(cuentaDistancias n) es la distribución de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> cuentaDistancias 15
     [(1,1),(2,6),(4,5),(6,2)]
     λ> cuentaDistancias 100
     [(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

λ> cuentaDistancias 15

[(1,1),(2,6),(4,5),(6,2)]

λ> cuentaDistancias 100

[(1,1),(2,25),(4,26),(6,25),(8,7),(10,7),(12,4),(14,3),(18,1)]

(frecuenciasDistancias n) es la frecuencia de distancias entre los n primeros primos consecutivos. Por ejemplo,

     λ> frecuenciasDistancias 15
     [(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]
     λ> frecuenciasDistancias 30
     [(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

λ> frecuenciasDistancias 15

[(1,7.142857),(2,42.857143),(4,35.714287),(6,14.285714)]

λ> frecuenciasDistancias 30

[(1,3.4482758),(2,34.482758),(4,34.482758),(6,24.137932),(8,3.4482758)]

(graficas ns) dibuja las gráficas de (frecuenciasDistancias k) para k en ns. Por ejemplo, (graficas [10,20,30]) dibuja

(graficas [1000,2000,3000]) dibuja

y (graficas [100000,200000,300000]) dibuja
(distanciasMasFrecuentes n) es la lista de las distancias más frecuentes entre los elementos consecutivos de la lista de los n primeros primos. Por ejemplo,

     distanciasMasFrecuentes 15     ==  [2]
     distanciasMasFrecuentes 26     ==  [2,4]
     distanciasMasFrecuentes 32     ==  [4]
     distanciasMasFrecuentes 41     ==  [2,4,6]
     distanciasMasFrecuentes 77     ==  [6]
     distanciasMasFrecuentes 160    ==  [4,6]
     distanciasMasFrecuentes (10^6) == [6]

distanciasMasFrecuentes 15 == [2]

distanciasMasFrecuentes 26 == [2,4]

distanciasMasFrecuentes 32 == [4]

distanciasMasFrecuentes 41 == [2,4,6]

distanciasMasFrecuentes 77 == [6]

distanciasMasFrecuentes 160 == [4,6]

distanciasMasFrecuentes (10^6) == [6]

Comprobar con QuickCheck si para todo n > 160 se verifica que (distanciasMasFrecuentes n) es [6].

Soluciones

import Data.Numbers.Primes
import qualified Data.Map as M 
import Graphics.Gnuplot.Simple
import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]
cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int
dicDistancias n =
  M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]
distancias n =
  zipWith (-) (tail xs) xs
  where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]
frecuenciasDistancias n =
  [(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]
  where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()
graficas ns =
  plotLists [Key Nothing]
            (map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]
distanciasMasFrecuentes n =
  M.keys (M.filter (==m) d)
  where d = dicDistancias n
        m = maximum (M.elems d)

-- La propiedad es
prop_distanciasMasFrecuentes :: Int -> Bool
prop_distanciasMasFrecuentes n =
  distanciasMasFrecuentes (161 + abs n) == [6]

import Data.Numbers.Primes

import qualified Data.Map as M

import Graphics.Gnuplot.Simple

import Test.QuickCheck

cuentaDistancias :: Int -> [(Int,Int)]

cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int

dicDistancias n =

M.fromListWith (+) (zip (distancias n) (repeat 1))

distancias :: Int -> [Int]

distancias n =

zipWith (-) (tail xs) xs

where xs = take n primes

frecuenciasDistancias :: Int -> [(Int,Float)]

frecuenciasDistancias n =

[(k,(100 * fromIntegral x) / n1) | (k,x) <- cuentaDistancias n]

where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()

graficas ns =

plotLists [Key Nothing]

(map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]

distanciasMasFrecuentes n =

M.keys (M.filter (==m) d)

where d = dicDistancias n

m = maximum (M.elems d)

-- La propiedad es

prop_distanciasMasFrecuentes :: Int -> Bool

prop_distanciasMasFrecuentes n =

distanciasMasFrecuentes (161 + abs n) == [6]

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)

Distribución de diferencias de dígitos consecutivos de pi

PorJosé A. Alonso 14-marzo-201725-abril-2021

La distribución de las diferencias de los dígitos consecutivos para los 18 primeros dígitos de pi se calcula como sigue: los primeros 18 dígitos de pi son

   3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

1	3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3

Las diferencias de sus elementos consecutivos es

   2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

1	2, -3, 3, -4, -4, 7, -4, 1, 2, -2, -3, -1, 2, -2, 6, 1, -1

y la distribución de sus frecuencias en el intervalo [-9,9] es

   0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

1	0, 0, 0, 0, 0, 3, 2, 2, 2, 0, 2, 3, 1, 0, 0, 1, 1, 0, 0

es decir, el desde el -9 a -5 no aparecen, el -4 aparece 3 veces, el -2 aparece 2 veces y así sucesivamente.

Definir las funciones

   distribucionDDCpi :: Int -> [Int]
   graficas :: [Int] -> FilePath -> IO ()

1 2	distribucionDDCpi :: Int -> [Int] graficas :: [Int] -> FilePath -> IO ()

tales que

(distribucionDDCpi n) es la distribución de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi. Por ejemplo,

   λ> distribucionDDCpi 18
   [0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]
   λ> distribucionDDCpi 100
   [1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]
   λ> distribucionDDCpi 200
   [3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]
   λ> distribucionDDCpi 1000
   [16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]
   λ> distribucionDDCpi 5000
   [67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

λ> distribucionDDCpi 18

[0,0,0,0,0,3,2,2,2,0,2,3,1,0,0,1,1,0,0]

λ> distribucionDDCpi 100

[1,2,1,7,7,7,6,5,8,6,7,14,4,9,3,6,4,1,0]

λ> distribucionDDCpi 200

[3,6,2,13,14,12,11,12,15,17,15,19,11,17,8,13,9,2,0]

λ> distribucionDDCpi 1000

[16,25,23,44,57,61,55,75,92,98,80,88,64,65,42,54,39,14,8]

λ> distribucionDDCpi 5000

[67,99,130,196,245,314,361,391,453,468,447,407,377,304,242,221,134,97,47]

(graficas ns f) dibuja en el fichero f las gráficas de las distribuciones de las diferencias de los dígitos consecutivos para los primeros n dígitos de pi, para n en ns. Por ejemplo, al evaluar (graficas [100,250..4000] «distribucionDDCpi.png» se escribe en el fichero «distribucionDDCpi.png» la siguiente gráfica

Nota: Se puede usar la librería Data.Number.CReal.

Soluciones

import Data.Number.CReal
import Graphics.Gnuplot.Simple
import Data.Array

--    λ> digitosPi 18
--    [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3]
digitosPi :: Int -> [Int]
digitosPi n = init [read [c] | c <- (x:xs)]
  where (x:_:xs) = showCReal n pi

--    λ> diferenciasConsecutivos (digitosPi 18)
--    [2,-3,3,-4,-4,7,-4,1,2,-2,-3,-1,2,-2,6,1,-1]
diferenciasConsecutivos :: Num a => [a] -> [a]
diferenciasConsecutivos xs =
  zipWith (-) xs (tail xs)

distribucionDDCpi :: Int -> [Int]
distribucionDDCpi =
  distribucion . diferenciasConsecutivos . digitosPi
  where distribucion xs =
          elems (accumArray (+) 0 (-9,9) (zip xs (repeat 1)))

graficas :: [Int] -> FilePath -> IO ()
graficas ns f = 
  plotLists [Key Nothing, PNG f]
            [puntos n | n <- ns]
  where puntos :: Int -> [(Int,Int)]
        puntos n = zip [-9..9] (distribucionDDCpi n)

import Data.Number.CReal

import Graphics.Gnuplot.Simple

import Data.Array

-- λ> digitosPi 18

-- [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3]

digitosPi :: Int -> [Int]

digitosPi n = init [read [c] | c <- (x:xs)]

where (x:_:xs) = showCReal n pi

-- λ> diferenciasConsecutivos (digitosPi 18)

-- [2,-3,3,-4,-4,7,-4,1,2,-2,-3,-1,2,-2,6,1,-1]

diferenciasConsecutivos :: Num a => [a] -> [a]

diferenciasConsecutivos xs =

zipWith (-) xs (tail xs)

distribucionDDCpi :: Int -> [Int]

distribucionDDCpi =

distribucion . diferenciasConsecutivos . digitosPi

where distribucion xs =

elems (accumArray (+) 0 (-9,9) (zip xs (repeat 1)))

graficas :: [Int] -> FilePath -> IO ()

graficas ns f =

plotLists [Key Nothing, PNG f]

[puntos n | n <- ns]

where puntos :: Int -> [(Int,Int)]

puntos n = zip [-9..9] (distribucionDDCpi n)

Suma con redondeos

PorJosé A. Alonso 1-enero-20167-enero-2016

Definir las funciones

   sumaRedondeos       :: Integer -> [Integer]
   limiteSumaRedondeos :: Integer -> Integer

1 2	sumaRedondeos :: Integer -> [Integer] limiteSumaRedondeos :: Integer -> Integer

tales que

(sumaRedondeos n) es la sucesión cuyo k-ésimo término es

     redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k)

1	redondeo (n/2) + redondeo (n/4) + ... + redondeo (n/2^k)

Por ejemplo,

     take 5 (sumaRedondeos 1000)  ==  [500,750,875,937,968]

1	take 5 (sumaRedondeos 1000) == [500,750,875,937,968]

(limiteSumaRedondeos n) es la suma de la serie

     redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ...

1	redondeo (n/2) + redondeo (n/4) + redondeo (n/8) + ...

Por ejemplo,

     limiteSumaRedondeos 2000                    ==  1999
     limiteSumaRedondeos 2016                    ==  2016
     limiteSumaRedondeos (10^308) `mod` (10^10)  ==  123839487

limiteSumaRedondeos 2000 == 1999

limiteSumaRedondeos 2016 == 2016

limiteSumaRedondeos (10^308) `mod` (10^10) == 123839487

Soluciones

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

sumaRedondeos1 :: Integer -> [Integer]
sumaRedondeos1 n =
    [sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]] | m <- [1..]]
    where n' = fromIntegral n

limiteSumaRedondeos1 :: Integer -> Integer
limiteSumaRedondeos1 = limite . sumaRedondeos1

limite :: [Integer] -> Integer
limite xs = head [x | (x,y) <- zip xs (tail xs), x == y]

-- 2ª definición
sumaRedondeos2 :: Integer -> [Integer]
sumaRedondeos2 n =
    scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..]]
    where n' = fromIntegral n

limiteSumaRedondeos2 :: Integer -> Integer
limiteSumaRedondeos2 = limite . sumaRedondeos2

-- 3ª definición
sumaRedondeos3 :: Integer -> [Integer]
sumaRedondeos3 n = map fst (iterate f (round (n'/2),4))
    where f (s,d) = (s + round (n'/(fromIntegral d)), 2*d)
          n'      = fromIntegral n

limiteSumaRedondeos3 :: Integer -> Integer
limiteSumaRedondeos3 = limite . sumaRedondeos3

-- 4ª definición
sumaRedondeos4 :: Integer -> [Integer]
sumaRedondeos4 n = xs ++ repeat x
    where n' = fromIntegral n
          m  = round (logBase 2 n')
          xs = scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..m]]
          x  = last xs

limiteSumaRedondeos4 :: Integer -> Integer
limiteSumaRedondeos4 = limite . sumaRedondeos4

-- Comparación de eficiencia
--    λ> (sumaRedondeos1 4) !! 20000
--    3
--    (0.92 secs, 197,782,232 bytes)
--    λ> (sumaRedondeos1 4) !! 30000
--    3
--    (2.20 secs, 351,084,816 bytes)
--    λ> (sumaRedondeos3 4) !! 20000
--    3
--    (0.30 secs, 53,472,392 bytes)
--    λ> (sumaRedondeos4 4) !! 20000
--    3
--    (0.01 secs, 0 bytes)

-- En lo que sigue, usaremos la 3ª definición
sumaRedondeos :: Integer -> [Integer]
sumaRedondeos = sumaRedondeos3

-- 5ª definición
-- =============

limiteSumaRedondeos5 :: Integer -> Integer
limiteSumaRedondeos5 n = 
    sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]]
    where n' = fromIntegral n
          m  = round (logBase 2 n')

-- 1ª definición

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

sumaRedondeos1 :: Integer -> [Integer]

sumaRedondeos1 n =

[sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]] | m <- [1..]]

where n' = fromIntegral n

limiteSumaRedondeos1 :: Integer -> Integer

limiteSumaRedondeos1 = limite . sumaRedondeos1

limite :: [Integer] -> Integer

limite xs = head [x | (x,y) <- zip xs (tail xs), x == y]

-- 2ª definición

sumaRedondeos2 :: Integer -> [Integer]

sumaRedondeos2 n =

scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..]]

where n' = fromIntegral n

limiteSumaRedondeos2 :: Integer -> Integer

limiteSumaRedondeos2 = limite . sumaRedondeos2

-- 3ª definición

sumaRedondeos3 :: Integer -> [Integer]

sumaRedondeos3 n = map fst (iterate f (round (n'/2),4))

where f (s,d) = (s + round (n'/(fromIntegral d)), 2*d)

n' = fromIntegral n

limiteSumaRedondeos3 :: Integer -> Integer

limiteSumaRedondeos3 = limite . sumaRedondeos3

-- 4ª definición

sumaRedondeos4 :: Integer -> [Integer]

sumaRedondeos4 n = xs ++ repeat x

where n' = fromIntegral n

m = round (logBase 2 n')

xs = scanl1 (+) [round (n'/(fromIntegral (2^k))) | k <- [1..m]]

x = last xs

limiteSumaRedondeos4 :: Integer -> Integer

limiteSumaRedondeos4 = limite . sumaRedondeos4

-- Comparación de eficiencia

-- λ> (sumaRedondeos1 4) !! 20000

-- 3

-- (0.92 secs, 197,782,232 bytes)

-- λ> (sumaRedondeos1 4) !! 30000

-- 3

-- (2.20 secs, 351,084,816 bytes)

-- λ> (sumaRedondeos3 4) !! 20000

-- 3

-- (0.30 secs, 53,472,392 bytes)

-- λ> (sumaRedondeos4 4) !! 20000

-- 3

-- (0.01 secs, 0 bytes)

-- En lo que sigue, usaremos la 3ª definición

sumaRedondeos :: Integer -> [Integer]

sumaRedondeos = sumaRedondeos3

-- 5ª definición

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

limiteSumaRedondeos5 :: Integer -> Integer

limiteSumaRedondeos5 n =

sum [round (n'/(fromIntegral (2^k))) | k <- [1..m]]

where n' = fromIntegral n

m = round (logBase 2 n')

Siembra de listas

PorJosé A. Alonso 23-diciembre-201525-marzo-2022

Definir la función

   siembra :: [Int] -> [Int]

1	siembra :: [Int] -> [Int]

tal que (siembra xs) es la lista ys obtenida al repartir cada elemento x de la lista xs poniendo un 1 en las x siguientes posiciones de la lista ys. Por ejemplo,

   siembra [4]      ==  [0,1,1,1,1] 
   siembra [0,2]    ==  [0,0,1,1]
   siembra [4,2]    ==  [0,1,2,2,1]

siembra [4] == [0,1,1,1,1]

siembra [0,2] == [0,0,1,1]

siembra [4,2] == [0,1,2,2,1]

El tercer ejemplo se obtiene sumando la siembra de 4 en la posición 0 (como el ejemplo 1) y el 2 en la posición 1 (como el ejemplo 2). Otros ejemplos son

   siembra [0,4,2]          ==  [0,0,1,2,2,1]
   siembra [3]              ==  [0,1,1,1]
   siembra [3,4,2]          ==  [0,1,2,3,2,1]
   siembra [3,2,1]          ==  [0,1,2,3]
   sum $ siembra [1..2500]  ==  3126250

siembra [0,4,2] == [0,0,1,2,2,1]

siembra [3] == [0,1,1,1]

siembra [3,4,2] == [0,1,2,3,2,1]

siembra [3,2,1] == [0,1,2,3]

sum $ siembra [1..2500] == 3126250

Comprobar con QuickCheck que la suma de los elementos de (siembra xs) es igual que la suma de los de xs.

Nota 1: Se supone que el argumento es una lista de números no negativos y que se puede ampliar tanto como sea necesario para repartir los elementos.

Nota 2: Este ejercicio es parte del examen del grupo 3 del 2 de diciembre.

Soluciones

import Test.QuickCheck

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

siembra1 :: [Int] -> [Int]
siembra1 = suma . brotes

-- (brotes xs) es la lista de los brotes obtenido sembrando los
-- elementos de xs. Por ejemplo,
--    brotes [3,4,2]  ==  [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]]
brotes :: [Int] -> [[Int]]
brotes xs = aux xs 1
    where aux (x:xs) n = (replicate n 0 ++ replicate x 1) : aux xs (n+1)
          aux _ _      = []

-- (suma xss) es la suma de los elementos de xss (suponiendo que al
-- final de cada elemento se continua con ceros). Por ejemplo,
--    suma [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]]  ==  [0,1,2,3,2,1]
suma :: [[Int]] -> [Int]
suma = foldr1 aux
    where aux [] ys = ys
          aux xs [] = xs
          aux (x:xs) (y:ys) = (x+y) : aux xs ys

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

siembra2 :: [Int] -> [Int]
siembra2 [] = []
siembra2 (x:xs) = mezcla (siembraElemento x) (0 : siembra2 xs)

siembraElemento :: Int -> [Int]
siembraElemento x = 0 : replicate x 1

mezcla :: [Int] -> [Int] -> [Int]
mezcla xs ys =
    take (max (length xs) (length ys))
         (zipWith (+) (xs ++ repeat 0) (ys ++ repeat 0))

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

siembra3 :: [Int] -> [Int]
siembra3 [] = []
siembra3 xs = aux xs 0 (repeat 0) where
    aux []     _ ys = cosecha ys
    aux (x:xs) n ys = aux xs (n+1) (zipWith (+) brotes ys) 
        where brotes = replicate (n+1) 0 ++ replicate x 1 ++ repeat 0

-- (cosecha xs) es la lista formada por los ceros iniciales de xs y los
-- elementos siguientes hasta que vuelve a aparecer el 0. Por ejemplo,
--    cosecha [0,0,3,5,2,0,9]            ==  [0,0,3,5,2]
--    cosecha ([0,0,3,5,2] ++ repeat 0)  ==  [0,0,3,5,2]
cosecha :: [Int] -> [Int]              
cosecha xs = ys ++ takeWhile (>0) zs
    where (ys,zs) = span (==0) xs

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

siembra4 :: [Int] -> [Int]
siembra4 [] = []
siembra4 xs = aux xs [] (repeat 0) where
    aux []     ys zs     = reverse ys ++ takeWhile (>0) zs
    aux (x:xs) ys (z:zs) = aux xs (z:ys) (zipWith (+) brotes zs) 
        where brotes = replicate x 1 ++ repeat 0

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

--    λ> sum $ siembra1 [1..2000]
--    2001000
--    (9.44 secs, 1,894,065,928 bytes)
--    ghci> sum $ siembra2 [1..2000]
--    2001000
--    (5.92 secs, 936900576 bytes)
--    ghci> sum $ siembra3 [1..2000]
--    2001000
--    (1.59 secs, 836847072 bytes)
--    ghci> sum $ siembra4 [1..2000]
--    2001000
--    (1.68 secs, 570492392 bytes)

-- En lo que sigue usaremos la 2ª definición
siembra :: [Int] -> [Int]
siembra = siembra2

-- Verificación
-- ============

-- La propiedad es
prop_siembra :: [Int] -> Bool
prop_siembra xs =
    sum (siembra1 ys) == sum ys
    where ys = map (\x -> 1 + abs x) xs

-- La comprobación es
--    λ> quickCheck prop_siembra
--    +++ OK, passed 100 tests.

100

import Test.QuickCheck

-- 1ª solución

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

siembra1 :: [Int] -> [Int]

siembra1 = suma . brotes

-- (brotes xs) es la lista de los brotes obtenido sembrando los

-- elementos de xs. Por ejemplo,

-- brotes [3,4,2] == [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]]

brotes :: [Int] -> [[Int]]

brotes xs = aux xs 1

where aux (x:xs) n = (replicate n 0 ++ replicate x 1) : aux xs (n+1)

aux _ _ = []

-- (suma xss) es la suma de los elementos de xss (suponiendo que al

-- final de cada elemento se continua con ceros). Por ejemplo,

-- suma [[0,1,1,1],[0,0,1,1,1,1],[0,0,0,1,1]] == [0,1,2,3,2,1]

suma :: [[Int]] -> [Int]

suma = foldr1 aux

where aux [] ys = ys

aux xs [] = xs

aux (x:xs) (y:ys) = (x+y) : aux xs ys

-- 2ª solución

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

siembra2 :: [Int] -> [Int]

siembra2 [] = []

siembra2 (x:xs) = mezcla (siembraElemento x) (0 : siembra2 xs)

siembraElemento :: Int -> [Int]

siembraElemento x = 0 : replicate x 1

mezcla :: [Int] -> [Int] -> [Int]

mezcla xs ys =

take (max (length xs) (length ys))

(zipWith (+) (xs ++ repeat 0) (ys ++ repeat 0))

-- 3ª solución

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

siembra3 :: [Int] -> [Int]

siembra3 [] = []

siembra3 xs = aux xs 0 (repeat 0) where

aux [] _ ys = cosecha ys

aux (x:xs) n ys = aux xs (n+1) (zipWith (+) brotes ys)

where brotes = replicate (n+1) 0 ++ replicate x 1 ++ repeat 0

-- (cosecha xs) es la lista formada por los ceros iniciales de xs y los

-- elementos siguientes hasta que vuelve a aparecer el 0. Por ejemplo,

-- cosecha [0,0,3,5,2,0,9] == [0,0,3,5,2]

-- cosecha ([0,0,3,5,2] ++ repeat 0) == [0,0,3,5,2]

cosecha :: [Int] -> [Int]

cosecha xs = ys ++ takeWhile (>0) zs

where (ys,zs) = span (==0) xs

-- 4ª solución

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

siembra4 :: [Int] -> [Int]

siembra4 [] = []

siembra4 xs = aux xs [] (repeat 0) where

aux [] ys zs = reverse ys ++ takeWhile (>0) zs

aux (x:xs) ys (z:zs) = aux xs (z:ys) (zipWith (+) brotes zs)

where brotes = replicate x 1 ++ repeat 0

-- Comparación de eficiencia

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

-- λ> sum $ siembra1 [1..2000]

-- 2001000

-- (9.44 secs, 1,894,065,928 bytes)

-- ghci> sum $ siembra2 [1..2000]

-- 2001000

-- (5.92 secs, 936900576 bytes)

-- ghci> sum $ siembra3 [1..2000]

-- 2001000

-- (1.59 secs, 836847072 bytes)

-- ghci> sum $ siembra4 [1..2000]

-- 2001000

-- (1.68 secs, 570492392 bytes)

-- En lo que sigue usaremos la 2ª definición

siembra :: [Int] -> [Int]

siembra = siembra2

-- Verificación

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

-- La propiedad es

prop_siembra :: [Int] -> Bool

prop_siembra xs =

sum (siembra1 ys) == sum ys

where ys = map (\x -> 1 + abs x) xs

-- La comprobación es

-- λ> quickCheck prop_siembra

-- +++ OK, passed 100 tests.

Índices de valores verdaderos

Soluciones

Nuevas soluciones

Distribución de diferencias de dígitos consecutivos de pi

Soluciones

Pensamiento

Sucesión de Recamán

Soluciones

Matrices de Pascal

Soluciones

Sucesión de Recamán

Soluciones

Distancias entre primos consecutivos

Soluciones

Codificación matricial

Soluciones

Distribución de diferencias de dígitos consecutivos de pi

Soluciones

Suma con redondeos

Soluciones

Siembra de listas

Soluciones

Entradas recientes

Buscar

Correo electrónico