take

Menor contenedor de primos

PorJosé A. Alonso 10-diciembre-201817-enero-2019

El n-ésimo menor contenenedor de primos es el menor número que contiene como subcadenas los primeros n primos. Por ejemplo, el 6º menor contenedor de primos es 113257 ya que es el menor que contiene como subcadenas los 6 primeros primos (2, 3, 5, 7, 11 y 13).

Definir la función

   menorContenedor :: Int -> Int

1	menorContenedor :: Int -> Int

tal que (menorContenedor n) es el n-ésimo menor contenenedor de primos. Por ejemplo,

   menorContenedor 1  ==  2
   menorContenedor 2  ==  23
   menorContenedor 3  ==  235
   menorContenedor 4  ==  2357
   menorContenedor 5  ==  112357
   menorContenedor 6  ==  113257

menorContenedor 1 == 2

menorContenedor 2 == 23

menorContenedor 3 == 235

menorContenedor 4 == 2357

menorContenedor 5 == 112357

menorContenedor 6 == 113257

Soluciones

import Data.List           (isInfixOf)
import Data.Numbers.Primes (primes)

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

menorContenedor :: Int -> Int
menorContenedor n =
  head [x | x <- [2..]
          , and [contenido y x | y <- take n primes]]

contenido :: Int -> Int -> Bool
contenido x y =
  show x `isInfixOf` show y

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

menorContenedor2 :: Int -> Int
menorContenedor2 n =
  head [x | x <- [2..]
          , all (`contenido` x) (take n primes)]

import Data.List (isInfixOf)

import Data.Numbers.Primes (primes)

-- 1ª solución

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

menorContenedor :: Int -> Int

menorContenedor n =

head [x | x <- [2..]

, and [contenido y x | y <- take n primes]]

contenido :: Int -> Int -> Bool

contenido x y =

show x `isInfixOf` show y

-- 2ª solución

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

menorContenedor2 :: Int -> Int

menorContenedor2 n =

head [x | x <- [2..]

, all (`contenido` x) (take n primes)]

Pensamiento

¡Ya hay hombres activos!
Soñaba la charca
con sus mosquitos.

Antonio Machado

Distancia de Hamming

PorJosé A. Alonso 12-noviembre-201817-enero-2019

La distancia de Hamming entre dos listas es el número de posiciones en que los correspondientes elementos son distintos. Por ejemplo, la distancia de Hamming entre «roma» y «loba» es 2 (porque hay 2 posiciones en las que los elementos correspondientes son distintos: la 1ª y la 3ª).

Definir la función

   distancia :: Eq a => [a] -> [a] -> Int

1	distancia :: Eq a => [a] -> [a] -> Int

tal que (distancia xs ys) es la distancia de Hamming entre xs e ys. Por ejemplo,

   distancia "romano" "comino"  ==  2
   distancia "romano" "camino"  ==  3
   distancia "roma"   "comino"  ==  2
   distancia "roma"   "camino"  ==  3
   distancia "romano" "ron"     ==  1
   distancia "romano" "cama"    ==  2
   distancia "romano" "rama"    ==  1

distancia "romano" "comino" == 2

distancia "romano" "camino" == 3

distancia "roma" "comino" == 2

distancia "roma" "camino" == 3

distancia "romano" "ron" == 1

distancia "romano" "cama" == 2

distancia "romano" "rama" == 1

Comprobar con QuickCheck si la distancia de Hamming tiene la siguiente propiedad

   distancia(xs,ys) = 0 si, y sólo si, xs = ys

1	distancia(xs,ys) = 0 si, y sólo si, xs = ys

y, en el caso de que no se verifique, modificar ligeramente la propiedad para obtener una condición necesaria y suficiente de distancia(xs,ys) = 0.

Soluciones

import Test.QuickCheck

-- 1ª definición:
distancia :: Eq a => [a] -> [a] -> Int
distancia xs ys = length [(x,y) | (x,y) <- zip xs ys, x /= y] 

-- 2ª definición:
distancia2 :: Eq a => [a] -> [a] -> Int
distancia2 [] ys = 0
distancia2 xs [] = 0
distancia2 (x:xs) (y:ys) | x /= y    = 1 + distancia2 xs ys
                         | otherwise = distancia2 xs ys

-- La propiedad es
prop_distancia1 :: [Int] -> [Int] -> Bool
prop_distancia1 xs ys =
    (distancia xs ys == 0) == (xs == ys)

-- La comprobación es
--    ghci> quickCheck prop_distancia1
--    *** Failed! Falsifiable (after 2 tests and 1 shrink): 
--    []
--    [1]
-- 
-- En efecto,
--    ghci> distancia [] [1] == 0
--    True
--    ghci> [] == [1]
--    False
-- 
-- La primera modificación es restringir la propiedad a lista de igual
-- longitud: 
prop_distancia2 :: [Int] -> [Int] -> Property
prop_distancia2 xs ys =
    length xs == length ys ==> 
    (distancia xs ys == 0) == (xs == ys)

-- La comprobación es
--    ghci> quickCheck prop_distancia2
--    *** Gave up! Passed only 33 tests.

-- Nota. La propiedad se verifica, pero al ser la condición demasiado
-- restringida sólo 33 de los casos la cumple.

-- La segunda restricción es limitar las listas a la longitud de la más
-- corta: 
prop_distancia3 :: [Int] -> [Int] -> Bool
prop_distancia3 xs ys =
    (distancia xs ys == 0) == (take n xs == take n ys)
    where n = min (length xs) (length ys)

-- La comprobación es
--    ghci> quickCheck prop_distancia3
--    +++ OK, passed 100 tests.

import Test.QuickCheck

-- 1ª definición:

distancia :: Eq a => [a] -> [a] -> Int

distancia xs ys = length [(x,y) | (x,y) <- zip xs ys, x /= y]

-- 2ª definición:

distancia2 :: Eq a => [a] -> [a] -> Int

distancia2 [] ys = 0

distancia2 xs [] = 0

distancia2 (x:xs) (y:ys) | x /= y = 1 + distancia2 xs ys

| otherwise = distancia2 xs ys

-- La propiedad es

prop_distancia1 :: [Int] -> [Int] -> Bool

prop_distancia1 xs ys =

(distancia xs ys == 0) == (xs == ys)

-- La comprobación es

-- ghci> quickCheck prop_distancia1

-- *** Failed! Falsifiable (after 2 tests and 1 shrink):

-- []

-- [1]

-- En efecto,

-- ghci> distancia [] [1] == 0

-- True

-- ghci> [] == [1]

-- False

-- La primera modificación es restringir la propiedad a lista de igual

-- longitud:

prop_distancia2 :: [Int] -> [Int] -> Property

prop_distancia2 xs ys =

length xs == length ys ==>

(distancia xs ys == 0) == (xs == ys)

-- La comprobación es

-- ghci> quickCheck prop_distancia2

-- *** Gave up! Passed only 33 tests.

-- Nota. La propiedad se verifica, pero al ser la condición demasiado

-- restringida sólo 33 de los casos la cumple.

-- La segunda restricción es limitar las listas a la longitud de la más

-- corta:

prop_distancia3 :: [Int] -> [Int] -> Bool

prop_distancia3 xs ys =

(distancia xs ys == 0) == (take n xs == take n ys)

where n = min (length xs) (length ys)

-- La comprobación es

-- ghci> quickCheck prop_distancia3

-- +++ OK, passed 100 tests.

Pensamiento

En mi soledad/
he visto cosas muy claras,
que no son verdad.

Antonio Machado

Número medio

PorJosé A. Alonso 24-julio-201826-marzo-2022

Un número medio es número natural que es igual a la media aritmética de las permutaciones de sus dígitos. Por ejemplo, 370 es un número medio ya que las permutaciones de sus dígitos es 073, 037, 307, 370, 703 y 730 cuya media es 2220/6 que es igual a 370.

Definir las siguientes funciones

   numeroMedio                :: Integer -> Bool
   densidadesNumeroMedio      :: [Double]
   graficaDensidadNumeroMedio :: Int -> IO ()

numeroMedio :: Integer -> Bool

densidadesNumeroMedio :: [Double]

graficaDensidadNumeroMedio :: Int -> IO ()

tales que

(numeroMedio n) se verifica si n es un número medio. Por ejemplo,

      λ> numeroMedio 370
      True
      λ> numeroMedio 371
      False
      λ> numeroMedio 485596707818930041152263374
      True
      λ> filter numeroMedio [100..600]
      [111,222,333,370,407,444,481,518,555,592]
      λ> filter numeroMedio [3*10^5..6*10^5]
      [333333,370370,407407,444444,481481,518518,555555,592592]

λ> numeroMedio 370

True

λ> numeroMedio 371

False

λ> numeroMedio 485596707818930041152263374

True

λ> filter numeroMedio [100..600]

[111,222,333,370,407,444,481,518,555,592]

λ> filter numeroMedio [3*10^5..6*10^5]

[333333,370370,407407,444444,481481,518518,555555,592592]

densidades es la lista cuyo elemento n-ésimo (empezando a contar en 1) es la densidad de números medios en el intervalo [1,n]; es decir, la cantidad de números medios menores o iguales que n dividida por n. Por ejemplo,

      λ> mapM_ print (take 30 densidades)
      1.0
      1.0
      1.0
      1.0
      1.0
      1.0
      1.0
      1.0
      1.0
      0.9
      0.9090909090909091
      0.8333333333333334
      0.7692307692307693
      0.7142857142857143
      0.6666666666666666
      0.625
      0.5882352941176471
      0.5555555555555556
      0.5263157894736842
      0.5
      0.47619047619047616
      0.5
      0.4782608695652174
      0.4583333333333333
      0.44
      0.4230769230769231
      0.4074074074074074
      0.39285714285714285
      0.3793103448275862
      0.36666666666666664

λ> mapM_ print (take 30 densidades)

1.0

0.9

0.9090909090909091

0.8333333333333334

0.7692307692307693

0.7142857142857143

0.6666666666666666

0.625

0.5882352941176471

0.5555555555555556

0.5263157894736842

0.5

0.47619047619047616

0.5

0.4782608695652174

0.4583333333333333

0.44

0.4230769230769231

0.4074074074074074

0.39285714285714285

0.3793103448275862

0.36666666666666664

(graficaDensidadNumeroMedio n) dibuja la gráfica de las densidades de
los intervalos [1,k] para k desde 1 hasta n. Por ejemplo, (graficaDensidadNumeroMedio 100) dibuja

y (graficaDensidadNumeroMedio 1000) dibuja

Soluciones

Puedes escribir tus soluciones en los comentarios o ver las soluciones propuestas pulsando [expand title=»aquí»]

import Data.List (genericLength, permutations, foldl')
import Test.QuickCheck
import Graphics.Gnuplot.Simple 

-- 1ª definición de numeroMedio
-- ============================

numeroMedio :: Integer -> Bool
numeroMedio n =
  n == media (map digitosAnumero (permutations (digitos n)))

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 425  ==  [4,2,5]
digitos :: Integer -> [Integer]
digitos n =
  [read [c] | c <- show n]

-- (digitosAnumero xs) es el número cuya lista de dígitos es xs. Por
-- ejemplo, 
--    digitosAnumero [4,2,5]  ==  425

-- 1ª definición de digitosAnumero
digitosAnumero1 :: [Integer] -> Integer
digitosAnumero1 = aux . reverse
  where aux [] = 0
        aux (x:xs) = x + 10 * aux xs

-- 1ª definición de digitosAnumero
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 = foldl' (\x y -> 10*x+y) 0

-- Comparación de eficiencia de definiciones de digitosAnumero
--    λ> length (show (digitosAnumero1 (replicate (10^5) 5)))
--    100000
--    (5.07 secs, 4,317,349,968 bytes)
--    λ> length (show (digitosAnumero2 (replicate (10^5) 5)))
--    100000
--    (0.67 secs, 4,288,054,592 bytes)

-- Se usará la 2ª definición de digitosAnumero
digitosAnumero :: [Integer] -> Integer
digitosAnumero = digitosAnumero2

-- (media xs) es la media aritmética de la lista xs (se supone que su
-- valor es entero). Por ejemplo,
--    media [370,730,73,703,37,307]  ==  370
media :: [Integer] -> Integer
media xs = sum xs `div` genericLength xs

-- 2ª definición de numeroMedio
-- ============================

numeroMedio2 :: Integer -> Bool
numeroMedio2 n =
  (10^k-1)*s == 9*k*n
  where xs = digitos n
        k  = genericLength xs
        s  = sum xs

-- Equivalencia de las definiciones de numeroMedio
-- ===============================================

-- La propiedad es
prop_numeroMedio :: Positive Integer -> Bool
prop_numeroMedio (Positive n) =
  numeroMedio n == numeroMedio2 n

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

-- Comparación de eficiencia de las definiciones de numeroMedio
-- ============================================================

--    λ> filter numeroMedio [10000..20000]
--    [11111]
--    (1.74 secs, 1,500,858,904 bytes)
--    λ> filter numeroMedio2 [10000..20000]
--    [11111]
--    (0.11 secs, 213,060,784 bytes)

-- Definición de densidadesNumeroMedio
-- ===================================

densidadesNumeroMedio :: [Double]
densidadesNumeroMedio = 
  [genericLength (filter numeroMedio2 [1..n]) / fromIntegral n | n <- [1..]]

-- Definición de graficaDensidadNumeroMedio
-- ========================================

graficaDensidadNumeroMedio :: Int -> IO ()
graficaDensidadNumeroMedio n =
  plotList [ Title ("graficaDensidadNumeroMedio")
           , Key Nothing
           -- , PNG ("Numero_medio_" ++ show n ++ ".png" )
           , XRange (1, fromIntegral n)]
           (take n densidadesNumeroMedio)

import Data.List (genericLength, permutations, foldl')

import Test.QuickCheck

import Graphics.Gnuplot.Simple

-- 1ª definición de numeroMedio

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

numeroMedio :: Integer -> Bool

numeroMedio n =

n == media (map digitosAnumero (permutations (digitos n)))

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

-- digitos 425 == [4,2,5]

digitos :: Integer -> [Integer]

digitos n =

[read [c] | c <- show n]

-- (digitosAnumero xs) es el número cuya lista de dígitos es xs. Por

-- ejemplo,

-- digitosAnumero [4,2,5] == 425

-- 1ª definición de digitosAnumero

digitosAnumero1 :: [Integer] -> Integer

digitosAnumero1 = aux . reverse

where aux [] = 0

aux (x:xs) = x + 10 * aux xs

-- 1ª definición de digitosAnumero

digitosAnumero2 :: [Integer] -> Integer

digitosAnumero2 = foldl' (\x y -> 10*x+y) 0

-- Comparación de eficiencia de definiciones de digitosAnumero

-- λ> length (show (digitosAnumero1 (replicate (10^5) 5)))

-- 100000

-- (5.07 secs, 4,317,349,968 bytes)

-- λ> length (show (digitosAnumero2 (replicate (10^5) 5)))

-- 100000

-- (0.67 secs, 4,288,054,592 bytes)

-- Se usará la 2ª definición de digitosAnumero

digitosAnumero :: [Integer] -> Integer

digitosAnumero = digitosAnumero2

-- (media xs) es la media aritmética de la lista xs (se supone que su

-- valor es entero). Por ejemplo,

-- media [370,730,73,703,37,307] == 370

media :: [Integer] -> Integer

media xs = sum xs `div` genericLength xs

-- 2ª definición de numeroMedio

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

numeroMedio2 :: Integer -> Bool

numeroMedio2 n =

(10^k-1)*s == 9*k*n

where xs = digitos n

k = genericLength xs

s = sum xs

-- Equivalencia de las definiciones de numeroMedio

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

-- La propiedad es

prop_numeroMedio :: Positive Integer -> Bool

prop_numeroMedio (Positive n) =

numeroMedio n == numeroMedio2 n

-- La comprobación es

-- λ> quickCheck prop_numeroMedio

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de las definiciones de numeroMedio

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

-- λ> filter numeroMedio [10000..20000]

-- [11111]

-- (1.74 secs, 1,500,858,904 bytes)

-- λ> filter numeroMedio2 [10000..20000]

-- [11111]

-- (0.11 secs, 213,060,784 bytes)

-- Definición de densidadesNumeroMedio

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

densidadesNumeroMedio :: [Double]

densidadesNumeroMedio =

[genericLength (filter numeroMedio2 [1..n]) / fromIntegral n | n <- [1..]]

-- Definición de graficaDensidadNumeroMedio

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

graficaDensidadNumeroMedio :: Int -> IO ()

graficaDensidadNumeroMedio n =

plotList [ Title ("graficaDensidadNumeroMedio")

, Key Nothing

-- , PNG ("Numero_medio_" ++ show n ++ ".png" )

, XRange (1, fromIntegral n)]

(take n densidadesNumeroMedio)

[/expand]

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]]

Números tetranacci

PorJosé A. Alonso 27-marzo-201826-marzo-2022

Los números tetranacci son una generalización de los números de Fibonacci definidos por

   T(0) = 0,
   T(1) = 1,
   T(2) = 1,
   T(3) = 2, 
   T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4), para n > 3.

T(0) = 0,

T(1) = 1,

T(2) = 1,

T(3) = 2,

T(n) = T(n-1) + T(n-2) + T(n-3) + T(n-4), para n > 3.

Los primeros números tetranacci son

   0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208

1	0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208

Definir las funciones

   tetranacci        :: Int -> Integer
   graficaTetranacci :: Int -> IO ()

1 2	tetranacci :: Int -> Integer graficaTetranacci :: Int -> IO ()

tales que

(tetranacci n) es el n-ésimo número tetranacci. Por ejemplo,

     λ> tetranacci 10
     208
     λ> map tetranacci [0..10]
     [0,1,1,2,4,8,15,29,56,108,208]
     λ> length (show (tetranacci5 (10^5)))
     28501

λ> tetranacci 10

208

λ> map tetranacci [0..10]

[0,1,1,2,4,8,15,29,56,108,208]

λ> length (show (tetranacci5 (10^5)))

28501

(graficaTetranacci n) dibuja la gráfica de los cocientes de n primeros pares de número tetranacci. Por ejemplo, (graficaTetranacci 300) dibuja

Soluciones

import Data.List (zipWith4)
import Data.Array
import Graphics.Gnuplot.Simple

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

tetranacci :: Int -> Integer
tetranacci 0 = 0
tetranacci 1 = 1
tetranacci 2 = 1
tetranacci 3 = 2
tetranacci n =
  tetranacci (n-1) + tetranacci (n-2) + tetranacci (n-3) + tetranacci (n-4) 

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

tetranacci2 :: Int -> Integer
tetranacci2 n = tetranaccis2 !! n

tetranaccis2 :: [Integer]
tetranaccis2 = 
    0 : 1 : 1 : 2 : zipWith4 f (r 0) (r 1) (r 2) (r 3)
    where f a b c d = a+b+c+d
          r n       = drop n tetranaccis2

-- 3ª solución (con acumuladores)
-- ==============================

tetranacci3 :: Int -> Integer
tetranacci3 n = tetranaccis3 !! n

tetranaccis3 :: [Integer]
tetranaccis3 = p (0, 1, 1, 2)
    where p (a, b, c, d) = a : p (b, c, d, a + b + c + d)

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

tetranacci4 :: Int -> Integer
tetranacci4 n = tetranaccis4 !! n

tetranaccis4 :: [Integer]
tetranaccis4 = 0 : 1 : 1 : 2 : p tetranaccis4
   where p (a:b:c:d:xs) = (a+b+c+d): p (b:c:d:xs)

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

tetranacci5 :: Int -> Integer
tetranacci5 n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 0
  f 1 = 1
  f 2 = 1
  f 3 = 2
  f k = v!(k-1) + v!(k-2) + v!(k-3) + v!(k-4) 

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

--    λ> tetranacci 26
--    7555935
--    (3.04 secs, 1,649,520,064 bytes)
--    λ> tetranacci2 26
--    7555935
--    (0.00 secs, 148,064 bytes)
-- 
--    λ> length (show (tetranacci2 (10^5)))
--    28501
--    (1.22 secs, 1,844,457,288 bytes)
--    λ> length (show (tetranacci3 (10^5)))
--    28501
--    (0.88 secs, 1,860,453,968 bytes)
--    λ> length (show (tetranacci4 (10^5)))
--    28501
--    (0.77 secs, 1,882,852,168 bytes)
--    λ> length (show (tetranacci5 (10^5)))
--    28501
--    (0.72 secs, 1,905,707,408 bytes)

-- Gráfica
-- =======

graficaTetranacci :: Int -> IO ()
graficaTetranacci n =
  plotList [ Key Nothing
           , Title "Tasa de crecimiento de los numeros tetranacci"
           , PNG ("Numeros_tetranacci_" ++ show n ++ ".png")
           ]
           (take n (zipWith (/) (tail xs) xs))
  where xs = (map fromIntegral tetranaccis4) :: [Double]

import Data.List (zipWith4)

import Data.Array

import Graphics.Gnuplot.Simple

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

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

tetranacci :: Int -> Integer

tetranacci 0 = 0

tetranacci 1 = 1

tetranacci 2 = 1

tetranacci 3 = 2

tetranacci n =

tetranacci (n-1) + tetranacci (n-2) + tetranacci (n-3) + tetranacci (n-4)

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

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

tetranacci2 :: Int -> Integer

tetranacci2 n = tetranaccis2 !! n

tetranaccis2 :: [Integer]

tetranaccis2 =

0 : 1 : 1 : 2 : zipWith4 f (r 0) (r 1) (r 2) (r 3)

where f a b c d = a+b+c+d

r n = drop n tetranaccis2

-- 3ª solución (con acumuladores)

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

tetranacci3 :: Int -> Integer

tetranacci3 n = tetranaccis3 !! n

tetranaccis3 :: [Integer]

tetranaccis3 = p (0, 1, 1, 2)

where p (a, b, c, d) = a : p (b, c, d, a + b + c + d)

-- 4ª solución

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

tetranacci4 :: Int -> Integer

tetranacci4 n = tetranaccis4 !! n

tetranaccis4 :: [Integer]

tetranaccis4 = 0 : 1 : 1 : 2 : p tetranaccis4

where p (a:b:c:d:xs) = (a+b+c+d): p (b:c:d:xs)

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

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

tetranacci5 :: Int -> Integer

tetranacci5 n = v ! n where

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

f 0 = 0

f 1 = 1

f 2 = 1

f 3 = 2

f k = v!(k-1) + v!(k-2) + v!(k-3) + v!(k-4)

-- Comparación de eficiencia

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

-- λ> tetranacci 26

-- 7555935

-- (3.04 secs, 1,649,520,064 bytes)

-- λ> tetranacci2 26

-- 7555935

-- (0.00 secs, 148,064 bytes)

-- λ> length (show (tetranacci2 (10^5)))

-- 28501

-- (1.22 secs, 1,844,457,288 bytes)

-- λ> length (show (tetranacci3 (10^5)))

-- 28501

-- (0.88 secs, 1,860,453,968 bytes)

-- λ> length (show (tetranacci4 (10^5)))

-- 28501

-- (0.77 secs, 1,882,852,168 bytes)

-- λ> length (show (tetranacci5 (10^5)))

-- 28501

-- (0.72 secs, 1,905,707,408 bytes)

-- Gráfica

-- =======

graficaTetranacci :: Int -> IO ()

graficaTetranacci n =

plotList [ Key Nothing

, Title "Tasa de crecimiento de los numeros tetranacci"

, PNG ("Numeros_tetranacci_" ++ show n ++ ".png")

]

(take n (zipWith (/) (tail xs) xs))

where xs = (map fromIntegral tetranaccis4) :: [Double]

Menor contenedor de primos

Soluciones

Pensamiento

Distancia de Hamming

Soluciones

Pensamiento

Número medio

Soluciones

Sucesión de Recamán

Soluciones

Números tetranacci

Soluciones

Entradas recientes

Buscar

Correo electrónico