José A. Alonso

Sucesiones alícuotas

PorJosé A. Alonso 28-febrero-20177-marzo-2017

La sucesión alícuota de un número x es la sucesión cuyo primer término es x y cada otro término es la suma de los divisores propios del término anterior. Por ejemplo, la sucesión alícuota de 10 es [10,8,7,1,0,0,0] ya que

   la suma de los divisores propios de 10 es 5 + 2 + 1 = 8
   la suma de los divisores propios de  8 es 4 + 2 + 1 = 7
   la suma de los divisores propios de  7 es 1
   la suma de los divisores propios de  1 es 0

la suma de los divisores propios de 10 es 5 + 2 + 1 = 8

la suma de los divisores propios de 8 es 4 + 2 + 1 = 7

la suma de los divisores propios de 7 es 1

la suma de los divisores propios de 1 es 0

Definir la función

   sucAlicuota :: Integer -> [Integer]

1	sucAlicuota :: Integer -> [Integer]

tal que (sucAlicuota x) es la sucesión alícuota de x. Por ejemplo,

   take 6 (sucAlicuota 10)       ==  [10,8,7,1,0,0]
   take 6 (sucAlicuota 95)       ==  [95,25,6,6,6,6]
   take 6 (sucAlicuota 220)      ==  [220,284,220,284,220,284]
   sucAlicuota 1184 !! (1+10^7)  ==  1210
   sucAlicuota 276 !! 200        ==  2790456740340877466506

take 6 (sucAlicuota 10) == [10,8,7,1,0,0]

take 6 (sucAlicuota 95) == [95,25,6,6,6,6]

take 6 (sucAlicuota 220) == [220,284,220,284,220,284]

sucAlicuota 1184 !! (1+10^7) == 1210

sucAlicuota 276 !! 200 == 2790456740340877466506

Soluciones

import Math.NumberTheory.ArithmeticFunctions (sigma)

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

sucAlicuota :: Integer -> [Integer]
sucAlicuota x = x : sucAlicuota (sumaDivisoresPropios x)

sumaDivisoresPropios :: Integer -> Integer
sumaDivisoresPropios x =
  sum [y | y <- [1..x-1], x `mod` y == 0]

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

sucAlicuota2 :: Integer -> [Integer]
sucAlicuota2 = iterate (sum . divisoresPropios)

divisoresPropios :: Integer -> [Integer]
divisoresPropios x = [y | y <- [1..x-1], x `mod` y == 0]

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

sucAlicuota3 :: Integer -> [Integer]
sucAlicuota3 x = aux x []
  where aux y ys | y `elem` ys = us ++ cycle zs
                 | otherwise   = aux (sumaDivisoresPropios y) (y:ys)
          where us = reverse ys
                zs = dropWhile (/=y) us

-- 4ª definición
-- =============

sucAlicuota4 :: Integer -> [Integer]
sucAlicuota4 x = x : sucAlicuota4 (sumaDivisoresPropios4 x)

sumaDivisoresPropios4 :: Integer -> Integer
sumaDivisoresPropios4 x =
  sigma 1 x - x

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

--    λ> sucAlicuota 1184 !! (1+10^3)
--    1210
--    (2.02 secs, 261,081,688 bytes)
--    λ> sucAlicuota2 1184 !! (1+10^3)
--    1210
--    (2.02 secs, 245,485,568 bytes)
--    λ> sucAlicuota3 1184 !! (1+10^3)
--    1210
--    (0.02 secs, 0 bytes)
--    λ> sucAlicuota4 1184 !! (1+10^3)
--    1210
--    (0.05 secs, 0 bytes)

import Math.NumberTheory.ArithmeticFunctions (sigma)

-- 1ª definición

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

sucAlicuota :: Integer -> [Integer]

sucAlicuota x = x : sucAlicuota (sumaDivisoresPropios x)

sumaDivisoresPropios :: Integer -> Integer

sumaDivisoresPropios x =

sum [y | y <- [1..x-1], x `mod` y == 0]

-- 2ª definición

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

sucAlicuota2 :: Integer -> [Integer]

sucAlicuota2 = iterate (sum . divisoresPropios)

divisoresPropios :: Integer -> [Integer]

divisoresPropios x = [y | y <- [1..x-1], x `mod` y == 0]

-- 3ª definición

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

sucAlicuota3 :: Integer -> [Integer]

sucAlicuota3 x = aux x []

where aux y ys | y `elem` ys = us ++ cycle zs

| otherwise = aux (sumaDivisoresPropios y) (y:ys)

where us = reverse ys

zs = dropWhile (/=y) us

-- 4ª definición

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

sucAlicuota4 :: Integer -> [Integer]

sucAlicuota4 x = x : sucAlicuota4 (sumaDivisoresPropios4 x)

sumaDivisoresPropios4 :: Integer -> Integer

sumaDivisoresPropios4 x =

sigma 1 x - x

-- Comparación de eficiencia

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

-- λ> sucAlicuota 1184 !! (1+10^3)

-- 1210

-- (2.02 secs, 261,081,688 bytes)

-- λ> sucAlicuota2 1184 !! (1+10^3)

-- 1210

-- (2.02 secs, 245,485,568 bytes)

-- λ> sucAlicuota3 1184 !! (1+10^3)

-- 1210

-- (0.02 secs, 0 bytes)

-- λ> sucAlicuota4 1184 !! (1+10^3)

-- 1210

-- (0.05 secs, 0 bytes)

Precisión de aproximaciones de pi

PorJosé A. Alonso 27-febrero-20176-marzo-2017

La precisión de una aproximación x de pi es el número de dígitos comunes entre el inicio de x y de pi. Por ejemplo, puesto que 355/113 es 3.1415929203539825 y pi es 3.141592653589793, la precisión de 355/113 es 7.

Definir las siguientes funciones

   mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]
   precisionPi       :: Double -> Int
   precisionPiCR     :: CReal -> Int

mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]

precisionPi :: Double -> Int

precisionPiCR :: CReal -> Int

tales que

(mayorPrefijoComun xs ys) es el mayor prefijo común de xs e ys. Por ejemplo,

     mayorPrefijoComun []      [2,3,4,5]  ==  []
     mayorPrefijoComun [2,3,5] []         ==  []
     mayorPrefijoComun [2,3,5] [2,3,4,5]  ==  [2,3]
     mayorPrefijoComun [2,3,5] [2,5,3,4]  ==  [2]
     mayorPrefijoComun [2,3,5] [5,2,3,4]  ==  []

mayorPrefijoComun [] [2,3,4,5] == []

mayorPrefijoComun [2,3,5] [] == []

mayorPrefijoComun [2,3,5] [2,3,4,5] == [2,3]

mayorPrefijoComun [2,3,5] [2,5,3,4] == [2]

mayorPrefijoComun [2,3,5] [5,2,3,4] == []

(precisionPi x) es la precisión de la aproximación de pi x. Por ejemplo,

     precisionPi (25/8)              ==  2
     precisionPi (22/7)              ==  3
     precisionPi (sqrt 2 + sqrt 3)   ==  3
     precisionPi (377/120)           ==  4
     precisionPi (31**(1/3))         ==  4
     precisionPi (7^7/4^9)           ==  5
     precisionPi (355/113)           ==  7
     precisionPi ((2143/22)**(1/4))  ==  9

precisionPi (25/8) == 2

precisionPi (22/7) == 3

precisionPi (sqrt 2 + sqrt 3) == 3

precisionPi (377/120) == 4

precisionPi (31**(1/3)) == 4

precisionPi (7^7/4^9) == 5

precisionPi (355/113) == 7

precisionPi ((2143/22)**(1/4)) == 9

(precisionPiCR x) es la precisión de la aproximación de pi x, como números reales. Por ejemplo,

     precisionPiCR (log (640320^3+744)/(sqrt 163))                        == 31
     precisionPiCR (log (5280^3*(236674+30303*sqrt 61)^3+744)/(sqrt 427)) == 53

1 2	precisionPiCR (log (640320^3+744)/(sqrt 163)) == 31 precisionPiCR (log (5280^3(236674+30303sqrt 61)^3+744)/(sqrt 427)) == 53

Nota: Para la definición precisionPiCR se usa la librería Data.Number.CReal que se instala con

   cabal install numbers

1	cabal install numbers

Soluciones

import Data.Number.CReal

-- mayorPrefijoComún
-- =================

-- 1ª definición
mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun [] _ = []
mayorPrefijoComun _ [] = []
mayorPrefijoComun (x:xs) (y:ys)
  | x == y    = x : mayorPrefijoComun xs ys
  | otherwise = []

-- 2ª definición
mayorPrefijoComun2 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun2 xs ys =
  [x | (x,y) <- takeWhile (\(x,y) -> x == y) (zip xs ys)] 

-- 3ª definición
mayorPrefijoComun3 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun3 xs ys =
  [x | (x,y) <- takeWhile (uncurry (==)) (zip xs ys)] 

-- 4ª definición
mayorPrefijoComun4 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun4 xs =
  map fst . takeWhile (uncurry (==)) . zip xs

-- 5ª definición
mayorPrefijoComun5 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun5 =
  ((map fst . takeWhile (uncurry (==))) .) . zip

-- precisionPi
-- ===========

-- 1ª definición
precisionPi :: Double -> Int
precisionPi x =
  length (mayorPrefijoComun xs ys) - 1
  where xs = show x
        ys = show pi

-- 2ª definición
precisionPi2 :: Double -> Int
precisionPi2 =
  pred . length . mayorPrefijoComun (show pi) . show

-- precisionPiCR
-- =============

precisionPiCR :: CReal -> Int
precisionPiCR = aux 50
  where aux n x | p < n-1   = p
                | otherwise = aux (n+50) x
          where p = precisionPiCRHasta n x

-- (precisionPiCRHasta n x) es la precisión de pi acotada por n. Por
-- ejemplo,
--    precisionPiCRHasta 1 3.14   ==  2
--    precisionPiCRHasta 5 3.14   ==  3
--    precisionPiCRHasta 5 3.142  ==  3
--    precisionPiCRHasta 5 3.141  ==  4
precisionPiCRHasta :: Int -> CReal -> Int
precisionPiCRHasta n x =
  length (mayorPrefijoComun xs ys) - 1
  where xs = showCReal n x
        ys = showCReal n pi

import Data.Number.CReal

-- mayorPrefijoComún

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

-- 1ª definición

mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun [] _ = []

mayorPrefijoComun _ [] = []

mayorPrefijoComun (x:xs) (y:ys)

| x == y = x : mayorPrefijoComun xs ys

| otherwise = []

-- 2ª definición

mayorPrefijoComun2 :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun2 xs ys =

[x | (x,y) <- takeWhile (\(x,y) -> x == y) (zip xs ys)]

-- 3ª definición

mayorPrefijoComun3 :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun3 xs ys =

[x | (x,y) <- takeWhile (uncurry (==)) (zip xs ys)]

-- 4ª definición

mayorPrefijoComun4 :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun4 xs =

map fst . takeWhile (uncurry (==)) . zip xs

-- 5ª definición

mayorPrefijoComun5 :: Eq a => [a] -> [a] -> [a]

mayorPrefijoComun5 =

((map fst . takeWhile (uncurry (==))) .) . zip

-- precisionPi

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

-- 1ª definición

precisionPi :: Double -> Int

precisionPi x =

length (mayorPrefijoComun xs ys) - 1

where xs = show x

ys = show pi

-- 2ª definición

precisionPi2 :: Double -> Int

precisionPi2 =

pred . length . mayorPrefijoComun (show pi) . show

-- precisionPiCR

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

precisionPiCR :: CReal -> Int

precisionPiCR = aux 50

where aux n x | p < n-1 = p

| otherwise = aux (n+50) x

where p = precisionPiCRHasta n x

-- (precisionPiCRHasta n x) es la precisión de pi acotada por n. Por

-- ejemplo,

-- precisionPiCRHasta 1 3.14 == 2

-- precisionPiCRHasta 5 3.14 == 3

-- precisionPiCRHasta 5 3.142 == 3

-- precisionPiCRHasta 5 3.141 == 4

precisionPiCRHasta :: Int -> CReal -> Int

precisionPiCRHasta n x =

length (mayorPrefijoComun xs ys) - 1

where xs = showCReal n x

ys = showCReal n pi

Cálculo de pi mediante el método de Newton

PorJosé A. Alonso 24-febrero-201725-abril-2021

El método de Newton para el cálculo de pi se basa en la relación

y en el desarrollo del arco seno

de donde se obtiene la fórmula

La primeras aproximaciones son

   a(0) = 6*(1/2)                               = 3.0
   a(1) = 6*(1/2+1/(2*3*2^3))                   = 3.125
   a(2) = 6*(1/2+1/(2*3*2^3)+(1*3)/(2*4*5*2^5)) = 3.1390625

a(0) = 6*(1/2) = 3.0

a(1) = 6*(1/2+1/(2*3*2^3)) = 3.125

a(2) = 6*(1/2+1/(2*3*2^3)+(1*3)/(2*4*5*2^5)) = 3.1390625

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

1 2	aproximacionPi :: Int -> Double grafica :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fórmula de Newton. Por ejemplo,

     aproximacionPi 0   ==  3.0
     aproximacionPi 1   ==  3.125
     aproximacionPi 2   ==  3.1390625
     aproximacionPi 10  ==  3.1415926468755613
     aproximacionPi 21  ==  3.141592653589793
     pi                 ==  3.141592653589793

aproximacionPi 0 == 3.0

aproximacionPi 1 == 3.125

aproximacionPi 2 == 3.1390625

aproximacionPi 10 == 3.1415926468755613

aproximacionPi 21 == 3.141592653589793

pi == 3.141592653589793

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..30]) dibuja

Nota: Este ejercicio ha sido propuesto por Manuel Herrera.

Soluciones

import Graphics.Gnuplot.Simple

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

aproximacionPi :: Int -> Double
aproximacionPi n = 6 * arcsinX
  where arcsinX = 0.5 + sum (take n factoresN)

factoresN :: [Double]
factoresN = zipWith (*) (potenciasK 3) fraccionesPI

potenciasK :: Double -> [Double]
potenciasK k = (0.5**k)/k : potenciasK (k+2)

fraccionesPI :: [Double]
fraccionesPI =
  scanl (*) (1/2) (tail (zipWith (/) [1,3..] [2,4..]))

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

aproximacionPi2 :: Int -> Double
aproximacionPi2 n = 6 * (serie !! n)

serie :: [Double]
serie = scanl1 (+) (zipWith (/)
                            (map fromIntegral numeradores)
                            (map fromIntegral denominadores))
  where numeradores    = 1 : scanl1 (*) [1,3..]
        denominadores  = zipWith (*) denominadores1 denominadores2
        denominadores1 = 2 : scanl1 (*) [2,4..]
        denominadores2 = 1 : [n * 2^n | n <- [3,5..]]

grafica :: [Int] -> IO ()
grafica xs = 
    plotList [Key Nothing]
             [(k,aproximacionPi k) | k <- xs]

import Graphics.Gnuplot.Simple

-- 1ª definición

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

aproximacionPi :: Int -> Double

aproximacionPi n = 6 * arcsinX

where arcsinX = 0.5 + sum (take n factoresN)

factoresN :: [Double]

factoresN = zipWith (*) (potenciasK 3) fraccionesPI

potenciasK :: Double -> [Double]

potenciasK k = (0.5**k)/k : potenciasK (k+2)

fraccionesPI :: [Double]

fraccionesPI =

scanl (*) (1/2) (tail (zipWith (/) [1,3..] [2,4..]))

-- 2ª definición

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

aproximacionPi2 :: Int -> Double

aproximacionPi2 n = 6 * (serie !! n)

serie :: [Double]

serie = scanl1 (+) (zipWith (/)

(map fromIntegral numeradores)

(map fromIntegral denominadores))

where numeradores = 1 : scanl1 (*) [1,3..]

denominadores = zipWith (*) denominadores1 denominadores2

denominadores1 = 2 : scanl1 (*) [2,4..]

denominadores2 = 1 : [n * 2^n | n <- [3,5..]]

grafica :: [Int] -> IO ()

grafica xs =

plotList [Key Nothing]

[(k,aproximacionPi k) | k <- xs]

Cálculo de pi mediante los métodos de Gregory-Leibniz y de Beeler

PorJosé A. Alonso 23-febrero-201726-marzo-2022

La fórmula de Gregory-Leibniz para calcular pi es

y la de Beeler es

Definir las funciones

   aproximaPiGL     :: Int -> Double
   aproximaPiBeeler :: Int -> Double
   graficas         :: [Int] -> IO ()

aproximaPiGL :: Int -> Double

aproximaPiBeeler :: Int -> Double

graficas :: [Int] -> IO ()

tales que

(aproximaPiGL n) es la aproximación de pi con los primeros n términos de la fórmula de Gregory-Leibniz. Por ejemplo,

     aproximaPiGL 1       ==  4.0
     aproximaPiGL 2       ==  2.666666666666667
     aproximaPiGL 3       ==  3.466666666666667
     aproximaPiGL 10      ==  3.0418396189294032
     aproximaPiGL 100     ==  3.1315929035585537
     aproximaPiGL 1000    ==  3.140592653839794
     aproximaPiGL 10000   ==  3.1414926535900345
     aproximaPiGL 100000  ==  3.1415826535897198

aproximaPiGL 1 == 4.0

aproximaPiGL 2 == 2.666666666666667

aproximaPiGL 3 == 3.466666666666667

aproximaPiGL 10 == 3.0418396189294032

aproximaPiGL 100 == 3.1315929035585537

aproximaPiGL 1000 == 3.140592653839794

aproximaPiGL 10000 == 3.1414926535900345

aproximaPiGL 100000 == 3.1415826535897198

(aproximaPiBeeler n) es la aproximación de pi con los primeros n términos de la fórmula de Beeler. Por ejemplo,

     aproximaPiBeeler 1   ==  2.0
     aproximaPiBeeler 2   ==  2.6666666666666665
     aproximaPiBeeler 3   ==  2.933333333333333
     aproximaPiBeeler 10  ==  3.140578169680337
     aproximaPiBeeler 60  ==  3.141592653589793
     pi                   ==  3.141592653589793

aproximaPiBeeler 1 == 2.0

aproximaPiBeeler 2 == 2.6666666666666665

aproximaPiBeeler 3 == 2.933333333333333

aproximaPiBeeler 10 == 3.140578169680337

aproximaPiBeeler 60 == 3.141592653589793

pi == 3.141592653589793

(graficas xs) dibuja la gráfica de las k-ésimas aproximaciones de pi, donde k toma los valores de la lista xs, con las fórmulas de Gregory-Leibniz y de Beeler. Por ejemplo, (graficas [1..25]) dibuja

donde la línea morada corresponde a la aproximación de Gregory-Leibniz y la verde a la de Beeler.

Nota: Este ejercicio ha sido propuesto por Enrique Naranjo.

Soluciones

import Graphics.Gnuplot.Simple

-- Definiciones de aproximaPiGL
-- ============================

-- 1ª definición de aproximaPiGL
aproximaPiGL :: Int -> Double
aproximaPiGL n = 4 * (sum . take n . sumaA . zipWith (/) [1,1..]) [1,3..]
  where sumaA (x:y:xs) = x:(-y):sumaA xs

-- 2ª definición de aproximaPiGL
aproximaPiGL2 :: Int -> Double
aproximaPiGL2 n =
  4 * (sum (take n (zipWith (/) (cycle [1,-1]) [1,3..])))

-- 3ª definición de aproximaPiGL
aproximaPiGL3 :: Int -> Double
aproximaPiGL3 n =
  4 * (sum . take n . zipWith (/) (cycle [1,-1])) [1,3..]

-- 4ª definición de aproximaPiGL
aproximaPiGL4 :: Int -> Double
aproximaPiGL4 n = serieGL !! (n-1)

serieGL :: [Double]
serieGL = scanl1 (+) (zipWith (/) numeradores denominadores)
  where numeradores   = cycle [4,-4]
        denominadores = [1,3..]

-- Definición de aproximaPiBeeler
aproximaPiBeeler :: Int -> Double
aproximaPiBeeler n = 2 * aux (fromIntegral n) 1
  where
    aux :: Double -> Double -> Double 
    aux n k | n == k    = 1
            | otherwise = 1 + (k/(2*k+1)) * aux n (1+k)

-- Definición de graficas
graficas :: [Int] -> IO ()
graficas xs = 
    plotLists [Key Nothing]
             [[(k,aproximaPiGL k)     | k <- xs],
              [(k,aproximaPiBeeler k) | k <- xs]]

import Graphics.Gnuplot.Simple

-- Definiciones de aproximaPiGL

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

-- 1ª definición de aproximaPiGL

aproximaPiGL :: Int -> Double

aproximaPiGL n = 4 * (sum . take n . sumaA . zipWith (/) [1,1..]) [1,3..]

where sumaA (x:y:xs) = x:(-y):sumaA xs

-- 2ª definición de aproximaPiGL

aproximaPiGL2 :: Int -> Double

aproximaPiGL2 n =

4 * (sum (take n (zipWith (/) (cycle [1,-1]) [1,3..])))

-- 3ª definición de aproximaPiGL

aproximaPiGL3 :: Int -> Double

aproximaPiGL3 n =

4 * (sum . take n . zipWith (/) (cycle [1,-1])) [1,3..]

-- 4ª definición de aproximaPiGL

aproximaPiGL4 :: Int -> Double

aproximaPiGL4 n = serieGL !! (n-1)

serieGL :: [Double]

serieGL = scanl1 (+) (zipWith (/) numeradores denominadores)

where numeradores = cycle [4,-4]

denominadores = [1,3..]

-- Definición de aproximaPiBeeler

aproximaPiBeeler :: Int -> Double

aproximaPiBeeler n = 2 * aux (fromIntegral n) 1

where

aux :: Double -> Double -> Double

aux n k | n == k = 1

| otherwise = 1 + (k/(2*k+1)) * aux n (1+k)

-- Definición de graficas

graficas :: [Int] -> IO ()

graficas xs =

plotLists [Key Nothing]

[[(k,aproximaPiGL k) | k <- xs],

[(k,aproximaPiBeeler k) | k <- xs]]

Cálculo de pi mediante la fracción continua de Lange

PorJosé A. Alonso 22-febrero-201726-marzo-2022

En 1999, L.J. Lange publicó el artículo An elegant new continued fraction for π.

En el primer teorema del artículo se demuestra la siguiente expresión de π mediante una fracción continua
$Calculo_de_pi_mediante_la_fraccion_continua_de_Lange$

La primeras aproximaciones son

   a(1) = 3+1                = 4.0
   a(2) = 3+(1/(6+9))        = 3.066666666666667
   a(3) = 3+(1/(6+9/(6+25))) = 3.158974358974359

a(1) = 3+1 = 4.0

a(2) = 3+(1/(6+9)) = 3.066666666666667

a(3) = 3+(1/(6+9/(6+25))) = 3.158974358974359

Definir las funciones

   aproximacionPi :: Int -> Double
   grafica        :: [Int] -> IO ()

1 2	aproximacionPi :: Int -> Double grafica :: [Int] -> IO ()

tales que

(aproximacionPi n) es la n-ésima aproximación de pi con la fracción continua de Lange. Por ejemplo,

     aproximacionPi 1     ==  4.0
     aproximacionPi 2     ==  3.066666666666667
     aproximacionPi 3     ==  3.158974358974359
     aproximacionPi 10    ==  3.141287132741557
     aproximacionPi 100   ==  3.141592398533554
     aproximacionPi 1000  ==  3.1415926533392926

aproximacionPi 1 == 4.0

aproximacionPi 2 == 3.066666666666667

aproximacionPi 3 == 3.158974358974359

aproximacionPi 10 == 3.141287132741557

aproximacionPi 100 == 3.141592398533554

aproximacionPi 1000 == 3.1415926533392926

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi donde k toma los valores de la lista xs. Por ejemplo, (grafica [1..10]) dibuja
$Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_2$
(grafica [10..100]) dibuja
$Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_3$
y (grafica [100..200]) dibuja
$Calculo_de_pi_mediante_la_fraccion_continua_de_Lange_4$

Nota: Este ejercicio ha sido propuesto por Antonio Morales.

Soluciones

import Graphics.Gnuplot.Simple
 
-- fraccionPi es la representación de la fracción continua de pi como un
-- par de listas infinitas.
fraccionPi :: [(Integer, Integer)]
fraccionPi = zip (3 : [6,6..]) (map (^2) [1,3..])

-- (aproximacionFC n fc) es la n-ésima aproximación de la fracción
-- continua fc (como un par de listas).  
aproximacionFC :: Int -> [(Integer, Integer)] -> Double
aproximacionFC n =
  foldr (\(a,b) z -> fromIntegral a + fromIntegral b / z) 1 . take n

aproximacionPi :: Int -> Double
aproximacionPi n =
  aproximacionFC n fraccionPi
 
grafica :: [Int] -> IO ()
grafica xs = 
    plotList [Key Nothing]
             [(k,aproximacionPi k) | k <- xs]

import Graphics.Gnuplot.Simple

-- fraccionPi es la representación de la fracción continua de pi como un

-- par de listas infinitas.

fraccionPi :: [(Integer, Integer)]

fraccionPi = zip (3 : [6,6..]) (map (^2) [1,3..])

-- (aproximacionFC n fc) es la n-ésima aproximación de la fracción

-- continua fc (como un par de listas).

aproximacionFC :: Int -> [(Integer, Integer)] -> Double

aproximacionFC n =

foldr (\(a,b) z -> fromIntegral a + fromIntegral b / z) 1 . take n

aproximacionPi :: Int -> Double

aproximacionPi n =

aproximacionFC n fraccionPi

grafica :: [Int] -> IO ()

grafica xs =

plotList [Key Nothing]

[(k,aproximacionPi k) | k <- xs]

Cálculo de pi mediante la variante de Euler de la serie armónica

PorJosé A. Alonso 21-febrero-201726-marzo-2022

En el artículo El desarrollo más bello de Pi como suma infinita, Miguel Ángel Morales comenta el desarrollo de pi publicado por Leonhard Euler en su libro «Introductio in Analysis Infinitorum» (1748).

El desarrollo es el siguiente

y se obtiene a partir de la serie armónica

modificando sólo el signo de algunos términos según el siguiente criterio:

Dejamos un + cuando el denominador de la fracción sea un 2 o un primo de la forma 4m-1.
Cambiamos a – si el denominador de la fracción es un primo de la forma 4m+1.
Si el número es compuesto ponemos el signo que quede al multiplicar los signos correspondientes a cada factor.

Por ejemplo,

la de denominador 3 = 4×1-1 lleva un +,
la de denominador 5 = 4×1+1 lleva un -,
la de denominador 13 = 4×3+1 lleva un -,
la de denominador 6 = 2×3 lleva un + (porque los dos llevan un +),
la de denominador 10 = 2×5 lleva un – (porque el 2 lleva un + y el 5 lleva un -) y
la de denominador 50 = 5x5x2 lleva un + (un – por el primer 5, otro – por el segundo 5 y un + por el 2).

Definir las funciones

  aproximacionPi :: Int -> Double
  grafica        :: Int -> IO ()

1 2	aproximacionPi :: Int -> Double grafica :: Int -> IO ()

tales que

(aproximacionPi n) es la aproximación de pi obtenida sumando los n primeros términos de la serie de Euler. Por ejemplo.

     aproximacionPi 1        ==  1.0
     aproximacionPi 10       ==  2.3289682539682537
     aproximacionPi 100      ==  2.934318000847734
     aproximacionPi 1000     ==  3.0603246224585128
     aproximacionPi 10000    ==  3.1105295744825403
     aproximacionPi 100000   ==  3.134308801935256
     aproximacionPi 1000000  ==  3.1395057903490806

aproximacionPi 1 == 1.0

aproximacionPi 10 == 2.3289682539682537

aproximacionPi 100 == 2.934318000847734

aproximacionPi 1000 == 3.0603246224585128

aproximacionPi 10000 == 3.1105295744825403

aproximacionPi 100000 == 3.134308801935256

aproximacionPi 1000000 == 3.1395057903490806

(grafica n) dibuja la gráfica de las aproximaciones de pi usando k sumando donde k toma los valores de la lista [100,110..n]. Por ejemplo, al evaluar (grafica 4000) se obtiene

Nota: Este ejercicio ha sido propuesto por Paula Macías.

Soluciones

import Data.Numbers.Primes
import Graphics.Gnuplot.Simple

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

aproximacionPi :: Int -> Double
aproximacionPi n =
  sum [1 / fromIntegral (k * signo k) | k <- [1..n]] 

signoPrimo :: Int -> Int
signoPrimo 2 = 1
signoPrimo p | p `mod` 4 == 3 = 1
             | otherwise      = -1

signo :: Int -> Int
signo n | isPrime n = signoPrimo n
        | otherwise = product (map signoPrimo (primeFactors n))

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

aproximacionPi2 :: Int -> Double
aproximacionPi2 n = serieEuler !! (n-1)

serieEuler :: [Double]
serieEuler =
  scanl1 (+) [1 / fromIntegral (n * signo n) | n <- [1..]]

-- Definición de grafica
-- =====================

grafica :: Int -> IO ()
grafica n = 
    plotList [Key Nothing]
             [(k,aproximacionPi2 k) | k <- [100,110..n]]

import Data.Numbers.Primes

import Graphics.Gnuplot.Simple

-- 1ª definición

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

aproximacionPi :: Int -> Double

aproximacionPi n =

sum [1 / fromIntegral (k * signo k) | k <- [1..n]]

signoPrimo :: Int -> Int

signoPrimo 2 = 1

signoPrimo p | p `mod` 4 == 3 = 1

| otherwise = -1

signo :: Int -> Int

signo n | isPrime n = signoPrimo n

| otherwise = product (map signoPrimo (primeFactors n))

-- 2ª definición

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

aproximacionPi2 :: Int -> Double

aproximacionPi2 n = serieEuler !! (n-1)

serieEuler :: [Double]

serieEuler =

scanl1 (+) [1 / fromIntegral (n * signo n) | n <- [1..]]

-- Definición de grafica

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

grafica :: Int -> IO ()

grafica n =

plotList [Key Nothing]

[(k,aproximacionPi2 k) | k <- [100,110..n]]

Regresión lineal

PorJosé A. Alonso 20-febrero-201726-marzo-2022

Dadas dos listas de valores

   xs = [x(1), x(2), ..., x(n)]
   ys = [y(1), y(2), ..., y(n)]

1 2	xs = [x(1), x(2), ..., x(n)] ys = [y(1), y(2), ..., y(n)]

la ecuación de la recta de regresión de ys sobre xs es y = a+bx, donde

   b = (nΣx(i)y(i) - Σx(i)Σy(i)) / (nΣx(i)² - (Σx(i))²)
   a = (Σy(i) - bΣx(i)) / n

1 2	b = (nΣx(i)y(i) - Σx(i)Σy(i)) / (nΣx(i)² - (Σx(i))²) a = (Σy(i) - bΣx(i)) / n

Definir la función

   regresionLineal :: [Double] -> [Double] -> (Double,Double)

1	regresionLineal :: [Double] -> [Double] -> (Double,Double)

tal que (regresionLineal xs ys) es el par (a,b) de los coeficientes de la recta de regresión de ys sobre xs. Por ejemplo, para los valores

   ejX, ejY :: [Double]
   ejX = [5,  7, 10, 12, 16, 20, 23, 27, 19, 14]
   ejY = [9, 11, 15, 16, 20, 24, 27, 29, 22, 20]

ejX, ejY :: [Double]

ejX = [5, 7, 10, 12, 16, 20, 23, 27, 19, 14]

ejY = [9, 11, 15, 16, 20, 24, 27, 29, 22, 20]

se tiene

   λ> regresionLineal ejX ejY
   (5.195045748716805,0.9218924347243919)

1 2	λ> regresionLineal ejX ejY (5.195045748716805,0.9218924347243919)

Para comprobar la definición, se importa la librería Graphics.Gnuplot.Simple y se define el procedimiento

   grafica :: [Double] -> [Double] -> IO ()
   grafica xs ys = 
       plotPathsStyle 
         [YRange (0,10+mY)] 
         [(defaultStyle {plotType = Points,
                         lineSpec = CustomStyle [LineTitle "Datos",
                                                 PointType 2,
                                                 PointSize 2.5]},
                        zip xs ys),
          (defaultStyle {plotType = Lines,
                         lineSpec = CustomStyle [LineTitle "Ajuste",
                                                 LineWidth 2]},
                        [(x,a+b*x) | x <- [0..mX]])]
       where (a,b) = regresionLineal xs ys                      
             mX    = maximum xs
             mY    = maximum ys

grafica :: [Double] -> [Double] -> IO ()

grafica xs ys =

plotPathsStyle

[YRange (0,10+mY)]

[(defaultStyle {plotType = Points,

lineSpec = CustomStyle [LineTitle "Datos",

PointType 2,

PointSize 2.5]},

zip xs ys),

(defaultStyle {plotType = Lines,

lineSpec = CustomStyle [LineTitle "Ajuste",

LineWidth 2]},

[(x,a+b*x) | x <- [0..mX]])]

where (a,b) = regresionLineal xs ys

mX = maximum xs

mY = maximum ys

tal que (grafica xs ys) pinta los puntos correspondientes a las listas de valores xs e ys y su recta de regresión. Por ejemplo, con (grafica ejX ejY) se obtiene el siguiente dibujo

Soluciones

import Data.List (genericLength)
import Graphics.Gnuplot.Simple

ejX, ejY :: [Double]
ejX = [5,  7, 10, 12, 16, 20, 23, 27, 19, 14]
ejY = [9, 11, 15, 16, 20, 24, 27, 29, 22, 20]

regresionLineal :: [Double] -> [Double] -> (Double,Double)
regresionLineal xs ys = (a,b)
    where n     = genericLength xs
          sumX  = sum xs
          sumY  = sum ys
          sumX2 = sum (zipWith (*) xs xs)
          sumY2 = sum (zipWith (*) ys ys)
          sumXY = sum (zipWith (*) xs ys)
          b     = (n*sumXY - sumX*sumY) / (n*sumX2 - sumX^2)
          a     = (sumY - b*sumX) / n

grafica :: [Double] -> [Double] -> IO ()
grafica xs ys = 
    plotPathsStyle 
      [YRange (0,10+mY)] 
      [(defaultStyle {plotType = Points,
                      lineSpec = CustomStyle [LineTitle "Datos",
                                              PointType 2,
                                              PointSize 2.5]},
                     zip xs ys),
       (defaultStyle {plotType = Lines,
                      lineSpec = CustomStyle [LineTitle "Ajuste",
                                              LineWidth 2]},
                     [(x,a+b*x) | x <- [0..mX]])]
    where (a,b) = regresionLineal xs ys                      
          mX    = maximum xs
          mY    = maximum ys

import Data.List (genericLength)

import Graphics.Gnuplot.Simple

ejX, ejY :: [Double]

ejX = [5, 7, 10, 12, 16, 20, 23, 27, 19, 14]

ejY = [9, 11, 15, 16, 20, 24, 27, 29, 22, 20]

regresionLineal :: [Double] -> [Double] -> (Double,Double)

regresionLineal xs ys = (a,b)

where n = genericLength xs

sumX = sum xs

sumY = sum ys

sumX2 = sum (zipWith (*) xs xs)

sumY2 = sum (zipWith (*) ys ys)

sumXY = sum (zipWith (*) xs ys)

b = (n*sumXY - sumX*sumY) / (n*sumX2 - sumX^2)

a = (sumY - b*sumX) / n

grafica :: [Double] -> [Double] -> IO ()

grafica xs ys =

plotPathsStyle

[YRange (0,10+mY)]

[(defaultStyle {plotType = Points,

lineSpec = CustomStyle [LineTitle "Datos",

PointType 2,

PointSize 2.5]},

zip xs ys),

(defaultStyle {plotType = Lines,

lineSpec = CustomStyle [LineTitle "Ajuste",

LineWidth 2]},

[(x,a+b*x) | x <- [0..mX]])]

where (a,b) = regresionLineal xs ys

mX = maximum xs

mY = maximum ys

Sucesión de trazas de dígitos de pi

PorJosé A. Alonso 17-febrero-201724-febrero-2017

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

1	3.1415926535897932384626433832 ... 83996346460422090106105779458151

Las matrices de orden 1×1, 2×2, …, 5×5 formadas por los primeros dígitos de pi son

   ( 3 )  ( 3 1 )  ( 3 1 4 )  ( 3 1 4 1 )  ( 3 1 4 1 5 )
          ( 4 1 )  ( 1 5 9 )  ( 5 9 2 6 )  ( 9 2 6 5 3 )
                   ( 2 6 5 )  ( 5 3 5 8 )  ( 5 8 9 7 9 )
                              ( 9 7 9 3 )  ( 3 2 3 8 4 )
                                           ( 6 2 6 4 3 )

( 3 ) ( 3 1 ) ( 3 1 4 ) ( 3 1 4 1 ) ( 3 1 4 1 5 )

( 4 1 ) ( 1 5 9 ) ( 5 9 2 6 ) ( 9 2 6 5 3 )

( 2 6 5 ) ( 5 3 5 8 ) ( 5 8 9 7 9 )

( 9 7 9 3 ) ( 3 2 3 8 4 )

( 6 2 6 4 3 )

y sus trazas (es decir, sumas de los elementos de la diagonal principal) son 3, 4, 13, 20 y 25, respectivamente.

Definir la función

   trazas :: Int -> IO [Int]

1	trazas :: Int -> IO [Int]

tal que (trazas n) es la lista de las trazas de las matrices de orden 1×1, 2×2, 3×3, …, nxn formadas por los primeros dígitos de pi. Por ejemplo,

   λ> trazas 20
   [3,4,13,20,25,30,19,32,41,59,62,64,58,75,62,60,80,99,78,108]
   λ> ts <- trazas 1000
   λ> maximum ts
   4644
   λ> maximum <$> trazas 1000
   4644

λ> trazas 20

[3,4,13,20,25,30,19,32,41,59,62,64,58,75,62,60,80,99,78,108]

λ> ts <- trazas 1000

λ> maximum ts

4644

λ> maximum <$> trazas 1000

4644

Soluciones

import Data.Char (digitToInt)
import Data.Matrix (fromList, trace)

trazas :: Int -> IO [Int]
trazas n = do
  (d:_:ds) <- readFile "Digitos_de_pi.txt"
  let xs = map digitToInt (d:ds)
  return [trace (fromList k k xs) | k <- [1..n]]

import Data.Char (digitToInt)

import Data.Matrix (fromList, trace)

trazas :: Int -> IO [Int]

trazas n = do

(d:_:ds) <- readFile "Digitos_de_pi.txt"

let xs = map digitToInt (d:ds)

return [trace (fromList k k xs) | k <- [1..n]]

Distribución de dígitos de pi

PorJosé A. Alonso 16-febrero-201725-abril-2021

Se pueden generar los dígitos de Pi, como se explica en el artículo Unbounded spigot algorithms for the digits of pi, con la función digitosPi definida por

   digitosPi :: [Integer]
   digitosPi = g(1,0,1,1,3,3) where
     g (q,r,t,k,n,l) = 
       if 4*q+r-t < n*t
       then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)
       else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

digitosPi :: [Integer]

digitosPi = g(1,0,1,1,3,3) where

g (q,r,t,k,n,l) =

if 4*q+r-t < n*t

then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)

else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

Por ejemplo,

   λ> take 25 digitosPi
   [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3]

1 2	λ> take 25 digitosPi [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3,2,3,8,4,6,2,6,4,3]

La distribución de los primeros 25 dígitos de pi es [0,2,3,5,3,3,3,1,2,3] ya que el 0 no aparece, el 1 ocurre 2 veces, el 3 ocurre 3 veces, el 4 ocurre 5 veces, …

Usando digitosPi, definir las siguientes funciones

   distribucionDigitosPi :: Int -> [Int]
   frecuenciaDigitosPi   :: Int -> [Double]

1 2	distribucionDigitosPi :: Int -> [Int] frecuenciaDigitosPi :: Int -> [Double]

tales que

(distribucionDigitosPi n) es la distribución de los n primeros dígitos de pi. Por ejemplo,

     λ> distribucionDigitosPi 10
     [0,2,1,2,1,2,1,0,0,1]
     λ> distribucionDigitosPi 100
     [8,8,12,12,10,8,9,8,12,13]
     λ> distribucionDigitosPi 1000
     [93,116,103,103,93,97,94,95,101,105]
     λ> distribucionDigitosPi 5000
     [466,531,496,460,508,525,513,488,492,521]

λ> distribucionDigitosPi 10

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

λ> distribucionDigitosPi 100

[8,8,12,12,10,8,9,8,12,13]

λ> distribucionDigitosPi 1000

[93,116,103,103,93,97,94,95,101,105]

λ> distribucionDigitosPi 5000

[466,531,496,460,508,525,513,488,492,521]

(frecuenciaDigitosPi n) es la frecuencia de los n primeros dígitos de pi. Por ejemplo,

   λ> frecuenciaDigitosPi 10
   [0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]
   λ> frecuenciaDigitosPi 100
   [8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]
   λ> frecuenciaDigitosPi 1000
   [9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]
   λ> frecuenciaDigitosPi 5000
   [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

λ> frecuenciaDigitosPi 10

[0.0,20.0,10.0,20.0,10.0,20.0,10.0,0.0,0.0,10.0]

λ> frecuenciaDigitosPi 100

[8.0,8.0,12.0,12.0,10.0,8.0,9.0,8.0,12.0,13.0]

λ> frecuenciaDigitosPi 1000

[9.3,11.6,10.3,10.3,9.3,9.7,9.4,9.5,10.1,10.5]

λ> frecuenciaDigitosPi 5000

[9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

Soluciones

import Data.Array
import Data.List (group, sort)

digitosPi :: [Integer]
digitosPi = g(1,0,1,1,3,3) where
  g (q,r,t,k,n,l) = 
    if 4*q+r-t < n*t
    then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)
    else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

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

distribucionDigitosPi :: Int -> [Int]
distribucionDigitosPi n =
    elems (accumArray (+) 0 (0,9) [(i,1)
                                  | i <- take n digitosPi]) 

frecuenciaDigitosPi :: Int -> [Double]
frecuenciaDigitosPi n =
  [100 * (fromIntegral x / m) | x <- distribucionDigitosPi n]
  where m = fromIntegral n

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

distribucionDigitosPi2 :: Int -> [Int]
distribucionDigitosPi2 n =
  [length xs - 1 | xs <- group (sort (take n digitosPi ++ [0..9]))]

frecuenciaDigitosPi2 :: Int -> [Double]
frecuenciaDigitosPi2 n =
  [100 * (fromIntegral x / m) | x <- distribucionDigitosPi2 n]
  where m = fromIntegral n

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

--    λ> last (take 5000 digitosPi)
--    2
--    (4.47 secs, 3,927,848,448 bytes)
--    λ> frecuenciaDigitosPi 5000
--    [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]
--    (0.01 secs, 0 bytes)
--    λ> frecuenciaDigitosPi2 5000
--    [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]
--    (0.02 secs, 0 bytes)

import Data.Array

import Data.List (group, sort)

digitosPi :: [Integer]

digitosPi = g(1,0,1,1,3,3) where

g (q,r,t,k,n,l) =

if 4*q+r-t < n*t

then n : g (10*q, 10*(r-n*t), t, k, div (10*(3*q+r)) t - 10*n, l)

else g (q*k, (2*q+r)*l, t*l, k+1, div (q*(7*k+2)+r*l) (t*l), l+2)

-- 1ª definición

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

distribucionDigitosPi :: Int -> [Int]

distribucionDigitosPi n =

elems (accumArray (+) 0 (0,9) [(i,1)

| i <- take n digitosPi])

frecuenciaDigitosPi :: Int -> [Double]

frecuenciaDigitosPi n =

[100 * (fromIntegral x / m) | x <- distribucionDigitosPi n]

where m = fromIntegral n

-- 2ª definición

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

distribucionDigitosPi2 :: Int -> [Int]

distribucionDigitosPi2 n =

[length xs - 1 | xs <- group (sort (take n digitosPi ++ [0..9]))]

frecuenciaDigitosPi2 :: Int -> [Double]

frecuenciaDigitosPi2 n =

[100 * (fromIntegral x / m) | x <- distribucionDigitosPi2 n]

where m = fromIntegral n

-- Comparación de eficiencia

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

-- λ> last (take 5000 digitosPi)

-- 2

-- (4.47 secs, 3,927,848,448 bytes)

-- λ> frecuenciaDigitosPi 5000

-- [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

-- (0.01 secs, 0 bytes)

-- λ> frecuenciaDigitosPi2 5000

-- [9.32,10.62,9.92,9.2,10.16,10.5,10.26,9.76,9.84,10.42]

-- (0.02 secs, 0 bytes)

Búsqueda en los dígitos de pi

PorJosé A. Alonso 15-febrero-201726-marzo-2022

El fichero Digitos_de_pi.txt contiene el número pi con un millón de decimales; es decir,

   3.1415926535897932384626433832 ... 83996346460422090106105779458151

1	3.1415926535897932384626433832 ... 83996346460422090106105779458151

Definir la función

   posicion :: String -> IO (Maybe Int)

1	posicion :: String -> IO (Maybe Int)

tal que (posicion n) es (Just k) si k es la posición de n en la sucesión formada por un millón dígitos decimales del número pi y Nothing si n no ocurre en dicha sucesión. Por ejemplo,

   λ> posicion "15"
   Just 3
   λ> posicion "2017"
   Just 8897
   λ> posicion "022017"
   Just 382052
   λ> posicion "14022017"
   Nothing
   λ> posicion "999999"
   Just 762
   λ> posicion "458151"
   Just 999995

λ> posicion "15"

Just 3

λ> posicion "2017"

Just 8897

λ> posicion "022017"

Just 382052

λ> posicion "14022017"

Nothing

λ> posicion "999999"

Just 762

λ> posicion "458151"

Just 999995

Nota. Se puede comprobar la función mediante The pi-search page o Pi search engine.

Soluciones

import Data.List (isPrefixOf)

posicion :: String -> IO (Maybe Int)
posicion ns = do
  ds <- readFile "Digitos_de_pi.txt"
  return (posicionEnLista (drop 2 ds) ns)

posicionEnLista :: Eq a => [a] -> [a] -> Maybe Int
posicionEnLista xs ys = aux xs 1
  where aux [] _ = Nothing
        aux (x:xs) n | ys `isPrefixOf` (x:xs) = Just n
                     | otherwise              = aux xs (n+1)

import Data.List (isPrefixOf)

posicion :: String -> IO (Maybe Int)

posicion ns = do

ds <- readFile "Digitos_de_pi.txt"

return (posicionEnLista (drop 2 ds) ns)

posicionEnLista :: Eq a => [a] -> [a] -> Maybe Int

posicionEnLista xs ys = aux xs 1

where aux [] _ = Nothing

aux (x:xs) n | ys `isPrefixOf` (x:xs) = Just n

| otherwise = aux xs (n+1)

Cálculo de pi usando la fórmula de Vieta

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

La fórmula de Vieta para el cálculo de pi es la siguiente

Definir las funciones

   aproximacionPi :: Int -> Double
   errorPi :: Double -> Int

1 2	aproximacionPi :: Int -> Double errorPi :: Double -> Int

tales que

(aproximacionPi n) es la aproximación de pi usando n factores de la fórmula de Vieta. Por ejemplo,

     aproximacionPi  5  ==  3.140331156954753
     aproximacionPi 10  ==  3.1415914215112
     aproximacionPi 15  ==  3.141592652386592
     aproximacionPi 20  ==  3.1415926535886207
     aproximacionPi 25  ==  3.141592653589795

aproximacionPi 5 == 3.140331156954753

aproximacionPi 10 == 3.1415914215112

aproximacionPi 15 == 3.141592652386592

aproximacionPi 20 == 3.1415926535886207

aproximacionPi 25 == 3.141592653589795

(errorPi x) es el menor número de factores de la fórmula de Vieta necesarios para obtener pi con un error menor que x. Por ejemplo,

     errorPi 0.1        ==  2
     errorPi 0.01       ==  4
     errorPi 0.001      ==  6
     errorPi 0.0001     ==  7
     errorPi 1e-4       ==  7
     errorPi 1e-14      ==  24
     pi                 ==  3.141592653589793
     aproximacionPi 24  ==  3.1415926535897913

errorPi 0.1 == 2

errorPi 0.01 == 4

errorPi 0.001 == 6

errorPi 0.0001 == 7

errorPi 1e-4 == 7

errorPi 1e-14 == 24

pi == 3.141592653589793

aproximacionPi 24 == 3.1415926535897913

Soluciones

-- 1ª definición de aproximacionPi
aproximacionPi :: Int -> Double
aproximacionPi n = product [2 / aux x | x <- [0..n]]
  where
    aux 0 = 1
    aux 1 = sqrt 2
    aux n = sqrt (2 + aux (n-1))

-- 2ª definición de aproximacionPi
aproximacionPi2 :: Int -> Double
aproximacionPi2 n = product [2/x | x <- 1 : xs] 
  where xs = take n $ iterate (\x -> sqrt (2+x)) (sqrt 2)

-- 3ª definición de aproximaxionPi
aproximacionPi3 :: Int -> Double
aproximacionPi3 n =  product (2 : take n (map (2/) xs))
  where xs = sqrt 2 : [sqrt (2 + x) | x <- xs]

-- 1ª definición de errorPi
errorPi :: Double -> Int
errorPi x = head [n | n <- [1..]
                    , abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi
errorPi2 :: Double -> Int
errorPi2 x = until aceptable (+1) 1
  where aceptable n = abs (pi - aproximacionPi n) < x

-- 1ª definición de aproximacionPi

aproximacionPi :: Int -> Double

aproximacionPi n = product [2 / aux x | x <- [0..n]]

where

aux 0 = 1

aux 1 = sqrt 2

aux n = sqrt (2 + aux (n-1))

-- 2ª definición de aproximacionPi

aproximacionPi2 :: Int -> Double

aproximacionPi2 n = product [2/x | x <- 1 : xs]

where xs = take n $ iterate (\x -> sqrt (2+x)) (sqrt 2)

-- 3ª definición de aproximaxionPi

aproximacionPi3 :: Int -> Double

aproximacionPi3 n = product (2 : take n (map (2/) xs))

where xs = sqrt 2 : [sqrt (2 + x) | x <- xs]

-- 1ª definición de errorPi

errorPi :: Double -> Int

errorPi x = head [n | n <- [1..]

, abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi

errorPi2 :: Double -> Int

errorPi2 x = until aceptable (+1) 1

where aceptable n = abs (pi - aproximacionPi n) < x

Cálculo de pi usando el producto de Wallis

PorJosé A. Alonso 13-febrero-201720-febrero-2017

El producto de Wallis es una expresión, descubierta por John Wallis en 1655, para representar el valor de π y que establece que:

    π     2     2     4     4     6     6     8     8
   --- = --- · --- · --- · --- · --- · --- · --- · --- ···
    2     1     3     3     5     5     7     7     9

π 2 2 4 4 6 6 8 8

--- = --- · --- · --- · --- · --- · --- · --- · --- ···

2 1 3 3 5 5 7 7 9

Definir las funciones

   factoresWallis  :: [Rational]
   productosWallis :: [Rational]
   aproximacionPi  :: Int -> Double
   errorPi         :: Double -> Int

factoresWallis :: [Rational]

productosWallis :: [Rational]

aproximacionPi :: Int -> Double

errorPi :: Double -> Int

tales que

factoresWallis es la sucesión de los factores del productos de Wallis. Por ejemplo,

     λ> take 10 factoresWallis
     [2 % 1,2 % 3,4 % 3,4 % 5,6 % 5,6 % 7,8 % 7,8 % 9,10 % 9,10 % 11]

1 2	λ> take 10 factoresWallis [2 % 1,2 % 3,4 % 3,4 % 5,6 % 5,6 % 7,8 % 7,8 % 9,10 % 9,10 % 11]

productosWallis es la sucesión de los productos de los primeros factores de Wallis. Por ejemplo,

     λ> take 7 productosWallis
     [2 % 1,4 % 3,16 % 9,64 % 45,128 % 75,256 % 175,2048 % 1225]

1 2	λ> take 7 productosWallis [2 % 1,4 % 3,16 % 9,64 % 45,128 % 75,256 % 175,2048 % 1225]

(aproximacionPi n) es la aproximación de pi obtenida multiplicando los n primeros factores de Wallis. Por ejemplo,

     aproximacionPi 20     ==  3.2137849402931895
     aproximacionPi 200    ==  3.1493784731686008
     aproximacionPi 2000   ==  3.142377365093878
     aproximacionPi 20000  ==  3.141671186534396

aproximacionPi 20 == 3.2137849402931895

aproximacionPi 200 == 3.1493784731686008

aproximacionPi 2000 == 3.142377365093878

aproximacionPi 20000 == 3.141671186534396

(errorPi x) es el menor número de factores de Wallis necesarios para obtener pi con un error menor que x. Por ejemplo,

     errorPi 0.1     ==  14
     errorPi 0.01    ==  155
     errorPi 0.001   ==  1569
     errorPi 0.0001  ==  15707

errorPi 0.1 == 14

errorPi 0.01 == 155

errorPi 0.001 == 1569

errorPi 0.0001 == 15707

Soluciones

import Data.Ratio

factoresWallis :: [Rational]
factoresWallis =
  concat [[y%(y-1),  y%(y+1)] | x <- [1..], let y = 2*x]

productosWallis :: [Rational]
productosWallis = scanl1 (*) factoresWallis

aproximacionPi :: Int -> Double
aproximacionPi n =
  fromRational (2 * productosWallis !! n)

errorPi :: Double -> Int
errorPi x = head [n | n <- [1..]
                    , abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi
errorPi2 :: Double -> Int
errorPi2 x =
  length (takeWhile (>=x) [abs (pi - 2 * fromRational y)
                          | y <- productosWallis])

-- 2ª definición de aproximacionPi
aproximacionPi2 :: Int -> Double
aproximacionPi2 n =
  2 * productosWallis2 !! n

productosWallis2 :: [Double]
productosWallis2 = scanl1 (*) factoresWallis2

factoresWallis2 :: [Double]
factoresWallis2 =
  concat [[y/(y-1),  y/(y+1)] | x <- [1..], let y = 2*x]

-- 3ª definición de errorPi
errorPi3 :: Double -> Int
errorPi3 x = head [n | n <- [1..]
                     , abs (pi - aproximacionPi2 n) < x]

-- Comparación de eficiencia
--    λ> errorPi 0.001
--    1569
--    (0.82 secs, 374,495,816 bytes)
--
--    λ> errorPi2 0.001
--    1569
--    (0.79 secs, 369,282,320 bytes)
--
--    λ> errorPi3 0.001
--    1569
--    (0.04 secs, 0 bytes)

import Data.Ratio

factoresWallis :: [Rational]

factoresWallis =

concat [[y%(y-1), y%(y+1)] | x <- [1..], let y = 2*x]

productosWallis :: [Rational]

productosWallis = scanl1 (*) factoresWallis

aproximacionPi :: Int -> Double

aproximacionPi n =

fromRational (2 * productosWallis !! n)

errorPi :: Double -> Int

errorPi x = head [n | n <- [1..]

, abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi

errorPi2 :: Double -> Int

errorPi2 x =

length (takeWhile (>=x) [abs (pi - 2 * fromRational y)

| y <- productosWallis])

-- 2ª definición de aproximacionPi

aproximacionPi2 :: Int -> Double

aproximacionPi2 n =

2 * productosWallis2 !! n

productosWallis2 :: [Double]

productosWallis2 = scanl1 (*) factoresWallis2

factoresWallis2 :: [Double]

factoresWallis2 =

concat [[y/(y-1), y/(y+1)] | x <- [1..], let y = 2*x]

-- 3ª definición de errorPi

errorPi3 :: Double -> Int

errorPi3 x = head [n | n <- [1..]

, abs (pi - aproximacionPi2 n) < x]

-- Comparación de eficiencia

-- λ> errorPi 0.001

-- 1569

-- (0.82 secs, 374,495,816 bytes)

-- λ> errorPi2 0.001

-- 1569

-- (0.79 secs, 369,282,320 bytes)

-- λ> errorPi3 0.001

-- 1569

-- (0.04 secs, 0 bytes)

Caminos en un árbol binario con suma dada

PorJosé A. Alonso 10-febrero-201717-febrero-2017

Los árboles binarios se pueden representar con el de tipo de dato algebraico

   data Arbol = H
              | N Int Arbol Arbol
     deriving Show

data Arbol = H

| N Int Arbol Arbol

deriving Show

Por ejemplo, los árboles

       3                7                 1
      / \              / \               /  \
     2   4            5   8             /    \
    / \   \          /   / \           /      \
   1   7   5        6   4   9         3       -1
                                     / \     /  \
                                    2   1   4    5                        
                                       /   / \    \                    
                                      1   1   2    6

3 7 1

/ \ / \ / \

2 4 5 8 / \

/ \ \ / / \ / \

1 7 5 6 4 9 3 -1

/ \ / \

2 1 4 5

/ / \ \

1 1 2 6

se representan por

   ej1, ej2, ej3 :: Arbol
   ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))
   ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))
   ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H))
             (N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H)))

ej1, ej2, ej3 :: Arbol

ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))

ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))

ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H))

(N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H)))

Definir las funciones

   caminos     :: Arbol -> [[Int]]
   caminosSuma :: Arbol -> Int -> [[Int]]

1 2	caminos :: Arbol -> [[Int]] caminosSuma :: Arbol -> Int -> [[Int]]

tales que

(caminos a) es la lista de los caminos entre dos nodos cualesquiera del árbol a. Por ejemplo,

     λ> caminos ej1
     [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5],
      [2],[2,1],[2,7],[1],[7],[4],[4,5],[5]]
     λ> caminos ej2
     [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9],
      [5],[5,6],[6],[8],[8,4],[8,9],[4],[9]]
     λ> length (caminos ej3)
     33

λ> caminos ej1

[[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5],

[2],[2,1],[2,7],[1],[7],[4],[4,5],[5]]

λ> caminos ej2

[[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9],

[5],[5,6],[6],[8],[8,4],[8,9],[4],[9]]

λ> length (caminos ej3)

(caminosSuma a k) es la lista de los caminos entre dos nodos cualesquiera del árbol a cuya suma es k. Por ejemplo,

     λ> caminosSuma ej1 3
     [[3],[2,1]]
     λ> caminosSuma ej3 3
     [[3],[-1,4]]
     λ> caminosSuma ej3 4
     [[1,3],[1,-1,4],[3,1],[-1,4,1],[-1,5],[4]]
     λ> caminosSuma ej3 5
     [[1,3,1],[1,-1,4,1],[1,-1,5],[3,2],[3,1,1],[-1,4,2],[4,1],[5]]
     λ> caminosSuma ej3 6
     [[1,3,2],[1,3,1,1],[1,-1,4,2],[4,2],[6]]
     λ> caminosSuma ej3 7
     []

λ> caminosSuma ej1 3

[[3],[2,1]]

λ> caminosSuma ej3 3

[[3],[-1,4]]

λ> caminosSuma ej3 4

[[1,3],[1,-1,4],[3,1],[-1,4,1],[-1,5],[4]]

λ> caminosSuma ej3 5

[[1,3,1],[1,-1,4,1],[1,-1,5],[3,2],[3,1,1],[-1,4,2],[4,1],[5]]

λ> caminosSuma ej3 6

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

λ> caminosSuma ej3 7

[]

Soluciones

data Arbol = H
           | N Int Arbol Arbol
  deriving Show

ej1, ej2, ej3 :: Arbol
ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))
ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H))
          (N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H)))
  
caminos :: Arbol -> [[Int]]
caminos H           = []
caminos a@(N r i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d

-- (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la
-- raíz de a hasta cualquiera de sus nodos. Por ejemplo.
--    λ> caminosDesdeRaiz ej1
--    [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]]
--    λ> caminosDesdeRaiz ej2
--    [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]]
caminosDesdeRaiz :: Arbol -> [[Int]]
caminosDesdeRaiz H = []
caminosDesdeRaiz (N x i d) =
  [x] : [x:ys | ys <- caminosDesdeRaiz i ++ caminosDesdeRaiz d]

caminosSuma :: Arbol -> Int -> [[Int]]
caminosSuma a k =
  [ys | ys <- caminos a
      , sum ys == k]

data Arbol = H

| N Int Arbol Arbol

deriving Show

ej1, ej2, ej3 :: Arbol

ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))

ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))

ej3 = N 1 (N 3 (N 2 H H) (N 1 (N 1 H H) H))

(N (-1) (N 4 (N 1 H H) (N 2 H H)) (N 5 H (N 6 H H)))

caminos :: Arbol -> [[Int]]

caminos H = []

caminos a@(N r i d) = caminosDesdeRaiz a ++ caminos i ++ caminos d

-- (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la

-- raíz de a hasta cualquiera de sus nodos. Por ejemplo.

-- λ> caminosDesdeRaiz ej1

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

-- λ> caminosDesdeRaiz ej2

-- [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]]

caminosDesdeRaiz :: Arbol -> [[Int]]

caminosDesdeRaiz H = []

caminosDesdeRaiz (N x i d) =

[x] : [x:ys | ys <- caminosDesdeRaiz i ++ caminosDesdeRaiz d]

caminosSuma :: Arbol -> Int -> [[Int]]

caminosSuma a k =

[ys | ys <- caminos a

, sum ys == k]

Referencia

Basado en Print all k-sum paths in a binary tree de GeeksforGeeks.

Máximo común divisor de x e y veces n

PorJosé A. Alonso 9-febrero-201716-febrero-2017

Definir las funciones

   repite :: Int -> Integer -> Integer
   mcdR   :: Integer -> Int -> Int -> Integer

1 2	repite :: Int -> Integer -> Integer mcdR :: Integer -> Int -> Int -> Integer

tales que

(repite x n) es el número obtenido repitiendo x veces el número n. Por ejemplo.

     repite 3 123  ==  123123123

1	repite 3 123 == 123123123

(mcdR n x y) es el máximo común divisor de los números obtenidos repitiendo x veces e y veces el número n. Por ejemplo.

     mcdR 123 2 3                     ==  123
     mcdR 4 4 6                       ==  44
     mcdR 2017 (10^1000) (2+10^1000)  ==  20172017

mcdR 123 2 3 == 123

mcdR 4 4 6 == 44

mcdR 2017 (10^1000) (2+10^1000) == 20172017

Soluciones

import Test.QuickCheck

repite :: Int -> Integer -> Integer
repite x n =
  read (concat (replicate x (show n)))

-- 1ª definición
mcdR :: Integer -> Int -> Int -> Integer
mcdR n x y =
  gcd (repite x n) (repite y n)

-- 2ª definición
mcdR2 :: Integer -> Int -> Int -> Integer
mcdR2 n x y =
  repite (gcd x y) n

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

-- La propiedad es
prop_equivalencia :: (Positive Integer) -> (Positive Int) -> (Positive Int)
                     -> Bool
prop_equivalencia (Positive n) (Positive x) (Positive y) =
  mcdR n x y == mcdR2 n x y

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

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

--    λ> mcdR 2017 (10^6) (2+10^6)
--    20172017
--    (18.92 secs, 6,012,285,224 bytes)
--    λ> mcdR2 2017 (10^6) (2+10^6)
--    20172017
--    (0.01 secs, 0 bytes)

import Test.QuickCheck

repite :: Int -> Integer -> Integer

repite x n =

read (concat (replicate x (show n)))

-- 1ª definición

mcdR :: Integer -> Int -> Int -> Integer

mcdR n x y =

gcd (repite x n) (repite y n)

-- 2ª definición

mcdR2 :: Integer -> Int -> Int -> Integer

mcdR2 n x y =

repite (gcd x y) n

-- Comprobación de equivalencia

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

-- La propiedad es

prop_equivalencia :: (Positive Integer) -> (Positive Int) -> (Positive Int)

-> Bool

prop_equivalencia (Positive n) (Positive x) (Positive y) =

mcdR n x y == mcdR2 n x y

-- La comprobación es

-- λ> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> mcdR 2017 (10^6) (2+10^6)

-- 20172017

-- (18.92 secs, 6,012,285,224 bytes)

-- λ> mcdR2 2017 (10^6) (2+10^6)

-- 20172017

-- (0.01 secs, 0 bytes)

Caminos desde la raíz en un árbol binario

PorJosé A. Alonso 8-febrero-201715-febrero-2017

Los árboles binarios se pueden representar con el de tipo de dato algebraico

   data Arbol = H
              | N Int Arbol Arbol
     deriving Show

data Arbol = H

| N Int Arbol Arbol

deriving Show

Por ejemplo, los árboles

       3                7       
      / \              / \      
     2   4            5   8     
    / \   \          /   / \    
   1   7   5        6   4   9

3 7

/ \ / \

2 4 5 8

/ \ \ / / \

1 7 5 6 4 9

se representan por

   ej1, ej2 :: Arbol
   ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))
   ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))

ej1, ej2 :: Arbol

ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))

ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))

Definir la función

   caminosDesdeRaiz :: Arbol -> [[Int]]

1	caminosDesdeRaiz :: Arbol -> [[Int]]

tal que (caminosDesdeRaiz a) es la lista de las caminosDesdeRaiz desde la raíz de a hasta cualquiera de sus nodos. Por ejemplo.

   λ> caminosDesdeRaiz ej1
   [[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]]
   λ> caminosDesdeRaiz ej2
   [[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]]

λ> caminosDesdeRaiz ej1

[[3],[3,2],[3,2,1],[3,2,7],[3,4],[3,4,5]]

λ> caminosDesdeRaiz ej2

[[7],[7,5],[7,5,6],[7,8],[7,8,4],[7,8,9]]

Soluciones

data Arbol = H
           | N Int Arbol Arbol
  deriving Show

ej1, ej2 :: Arbol
ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))
  
caminosDesdeRaiz :: Arbol -> [[Int]]
caminosDesdeRaiz H = []
caminosDesdeRaiz (N x i d) =
  [x] : [x:ys | ys <- caminosDesdeRaiz i ++ caminosDesdeRaiz d]

data Arbol = H

| N Int Arbol Arbol

deriving Show

ej1, ej2 :: Arbol

ej1 = N 3 (N 2 (N 1 H H) (N 7 H H)) (N 4 H (N 5 H H))

ej2 = N 7 (N 5 (N 6 H H) H) (N 8 (N 4 H H) (N 9 H H))

caminosDesdeRaiz :: Arbol -> [[Int]]

caminosDesdeRaiz H = []

caminosDesdeRaiz (N x i d) =

[x] : [x:ys | ys <- caminosDesdeRaiz i ++ caminosDesdeRaiz d]

Prefijo con suma acotada

PorJosé A. Alonso 7-febrero-201714-febrero-2017

Definir la función

   prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

1	prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

tal que (prefijoAcotado x ys) es el mayor prefijo de ys cuya suma es menor que x. Por ejemplo,

   prefijoAcotado 10 [3,2,5,7]  ==  [3,2]
   prefijoAcotado 10 [1..]      ==  [1,2,3]

1 2	prefijoAcotado 10 [3,2,5,7] == [3,2] prefijoAcotado 10 [1..] == [1,2,3]

Soluciones

-- 1ª definición (por recursión):
prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado x [] = []
prefijoAcotado x (y:ys)
  | y < x     = y : prefijoAcotado (x-y) ys
  | otherwise = []

-- 2ª definición (con scanl1 y takeWhile):
prefijoAcotado2 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado2 x ys = map fst conSumasAcotadas
  where 
    sumas            = scanl1 (+) ys 
    conSumas         = zip ys sumas
    conSumasAcotadas = takeWhile (\(a,b) -> b < x) conSumas

-- 3ª definición (con (.)):
prefijoAcotado3 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado3 x ys = map fst conSumasAcotadas
  where 
    sumas            = scanl1 (+) ys 
    conSumas         = zip ys sumas
    conSumasAcotadas = takeWhile ((<x) . snd) conSumas

-- 4ª definición:
prefijoAcotado4 :: (Num a, Ord a) => a -> [a] -> [a]
prefijoAcotado4 x ys = 
    map fst (takeWhile ((<x) . snd) (zip ys (scanl1 (+) ys)))

-- 1ª definición (por recursión):

prefijoAcotado :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado x [] = []

prefijoAcotado x (y:ys)

| y < x = y : prefijoAcotado (x-y) ys

| otherwise = []

-- 2ª definición (con scanl1 y takeWhile):

prefijoAcotado2 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado2 x ys = map fst conSumasAcotadas

where

sumas = scanl1 (+) ys

conSumas = zip ys sumas

conSumasAcotadas = takeWhile (\(a,b) -> b < x) conSumas

-- 3ª definición (con (.)):

prefijoAcotado3 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado3 x ys = map fst conSumasAcotadas

where

sumas = scanl1 (+) ys

conSumas = zip ys sumas

conSumasAcotadas = takeWhile ((<x) . snd) conSumas

-- 4ª definición:

prefijoAcotado4 :: (Num a, Ord a) => a -> [a] -> [a]

prefijoAcotado4 x ys =

map fst (takeWhile ((<x) . snd) (zip ys (scanl1 (+) ys)))

Aplicaciones de operaciones

PorJosé A. Alonso 6-febrero-201713-febrero-2017

Definir la función

   aplicaciones :: [a -> b -> c] -> [a] -> [b] -> [c]

1	aplicaciones :: [a -> b -> c] -> [a] -> [b] -> [c]

tal que (aplicaciones os xs ys) es la lista obtenida aplicando las operaciones de os a los elementos de xs es ys. Por ejemplo,

   λ> aplicaciones [(+),(*)] [1,2] [5,8]
   [6,9,7,10,5,8,10,16]
   λ> aplicaciones [(+),(*)] [1,2] [5]
   [6,7,5,10]
   λ> aplicaciones [(<),(>)] ["ab","c"] ["def","c"]
   [True,True,True,False,False,False,False,False]
   λ> import Data.List
   λ> aplicaciones [(++),intersect] ["ab","c"] ["bd","cf"]
   ["abbd","abcf","cbd","ccf","b","","","c"]

λ> aplicaciones [(+),(*)] [1,2] [5,8]

[6,9,7,10,5,8,10,16]

λ> aplicaciones [(+),(*)] [1,2] [5]

[6,7,5,10]

λ> aplicaciones [(<),(>)] ["ab","c"] ["def","c"]

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

λ> import Data.List

λ> aplicaciones [(++),intersect] ["ab","c"] ["bd","cf"]

["abbd","abcf","cbd","ccf","b","","","c"]

Soluciones

-- 1ª definición
aplicaciones :: [a -> b -> c] -> [a] -> [b] -> [c]
aplicaciones os xs ys =
  [os x y | os <- os, x <- xs, y <- ys]

-- 2ª definición
aplicaciones2 :: [a -> b -> c] -> [a] -> [b] -> [c]
aplicaciones2 os xs ys = os <*> xs <*> ys

-- 3ª definición
aplicaciones3 :: [a -> b -> c] -> [a] -> [b] -> [c]
aplicaciones3 = ((<*>) .) . (<*>)

-- 1ª definición

aplicaciones :: [a -> b -> c] -> [a] -> [b] -> [c]

aplicaciones os xs ys =

[os x y | os <- os, x <- xs, y <- ys]

-- 2ª definición

aplicaciones2 :: [a -> b -> c] -> [a] -> [b] -> [c]

aplicaciones2 os xs ys = os <*> xs <*> ys

-- 3ª definición

aplicaciones3 :: [a -> b -> c] -> [a] -> [b] -> [c]

aplicaciones3 = ((<*>) .) . (<*>)

Sucesión de Cantor de números innombrables

PorJosé A. Alonso 3-febrero-201725-abril-2021

Un número es innombrable si es divisible por 7 o alguno de sus dígitos es un 7. Un juego infantil consiste en contar saltándose los números innombrables:

   1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

1	1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...

La sucesión de Cantor se obtiene llenando los huecos de la sucesión anterior
como se indica a continuación:

  1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
  24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41  (9) 43
  44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
  (2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
  (25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
  (30) 99 100

1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23

24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41 (9) 43

44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62

(2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)

(25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)

(30) 99 100

Definir la sucesión

   sucCantor :: [Integer]

1	sucCantor :: [Integer]

cuyos elementos son los términos de la sucesión de Cantor. Por ejemplo,

   λ> take 100 sucCantor
   [1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,
    22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,
    40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,
    13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,
    20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,
    6, 92,93,94,95,96, 29, 30 ,99,100]

   λ> sucCantor2 !! (5+10^6)
   544480

   λ> sucCantor2 !! (6+10^6)
   266086

λ> take 100 sucCantor

[1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2, 15,16, 3, 18,19,20, 4,

22,23,24,25,26, 5 , 6 ,29,30,31,32,33,34, 1 ,36 , 8 ,38,39,

40,41, 9 ,43,44,45,46, 10 ,48, 11 ,50,51,52,53,54,55 , 12 ,

13, 58,59,60,61,62, 2 ,64,65,66, 15 ,68,69, 16 , 3 , 18, 19,

20, 4, 22, 23, 24 ,25 ,80,81,82,83, 26 ,85,86, 5 ,88,89,90,

6, 92,93,94,95,96, 29, 30 ,99,100]

λ> sucCantor2 !! (5+10^6)

544480

λ> sucCantor2 !! (6+10^6)

266086

Soluciones

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

sucCantor1 :: [Integer]
sucCantor1 = map fst $ scanl f (1,0) [2..]
  where f (a,i) x
          | esInnombrable x = (sucCantor1 !! i, i+1)
          | otherwise       = (x,i)


esInnombrable :: Integer -> Bool
esInnombrable x =
  rem x 7 == 0 || '7' `elem` show x

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

sucCantor2 :: [Integer]
sucCantor2 = aux 0 1
  where aux i x
          | esInnombrable x = sucCantor2 !! i : aux (i+1) (x+1)
          | otherwise       = x : aux i (x+1)

-- 1ª solución

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

sucCantor1 :: [Integer]

sucCantor1 = map fst $ scanl f (1,0) [2..]

where f (a,i) x

| esInnombrable x = (sucCantor1 !! i, i+1)

| otherwise = (x,i)

esInnombrable :: Integer -> Bool

esInnombrable x =

rem x 7 == 0 || '7' `elem` show x

-- 2ª solución

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

sucCantor2 :: [Integer]

sucCantor2 = aux 0 1

where aux i x

| esInnombrable x = sucCantor2 !! i : aux (i+1) (x+1)

| otherwise = x : aux i (x+1)

Referencia

Basado en Cantor’s unspeakable numbers de
CodeGolf.

Particiones de una lista

PorJosé A. Alonso 2-febrero-20179-febrero-2017

Definir la función

   particiones :: [a] -> [[[a]]]

1	particiones :: [a] -> [[[a]]]

tal que (particiones xs) es la lista de las particiones de xs en segmentos de elementos consecutivos. Por ejemplo,

   λ> particiones [1..3]
   [[[1],[2],[3]],[[1],[2,3]],[[1,2],[3]],[[1,2,3]]]
   λ> mapM_ print (particiones "abcd")
   ["a","b","c","d"]
   ["a","b","cd"]
   ["a","bc","d"]
   ["a","bcd"]
   ["ab","c","d"]
   ["ab","cd"]
   ["abc","d"]
   ["abcd"]
   λ> length (particiones [1..22])
   2097152

λ> particiones [1..3]

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

λ> mapM_ print (particiones "abcd")

["a","b","c","d"]

["a","b","cd"]

["a","bc","d"]

["a","bcd"]

["ab","c","d"]

["ab","cd"]

["abc","d"]

["abcd"]

λ> length (particiones [1..22])

2097152

Comprobar con QuickCheck que la concatenación de cada uno de los elementos de (particiones xs) es igual a xs.

Nota: En la comprobación usar ejemplos pequeños como se indica a continuación

   quickCheckWith (stdArgs {maxSize=10}) prop_particiones

1	quickCheckWith (stdArgs {maxSize=10}) prop_particiones

Soluciones

import Test.QuickCheck

particiones :: [a] -> [[[a]]]
particiones [] = [[]]
particiones xs =
  [(take k xs) : yss | k <- [1..n], yss <- particiones (drop k xs)]
  where n = length xs

-- La propiedad es
prop_particiones :: [Int] -> Bool
prop_particiones xs =
  all (\yss -> concat yss == xs) (particiones xs)

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_particiones
--    +++ OK, passed 100 tests.

import Test.QuickCheck

particiones :: [a] -> [[[a]]]

particiones [] = [[]]

particiones xs =

[(take k xs) : yss | k <- [1..n], yss <- particiones (drop k xs)]

where n = length xs

-- La propiedad es

prop_particiones :: [Int] -> Bool

prop_particiones xs =

all (\yss -> concat yss == xs) (particiones xs)

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_particiones

-- +++ OK, passed 100 tests.

Subrayado de un carácter

PorJosé A. Alonso 1-febrero-20178-febrero-2017

Definir el procedimiento

   subraya :: String -> Char -> IO ()

1	subraya :: String -> Char -> IO ()

tal que (subraya cs c) escribe la cadena cs y debajo otra subrayando las ocurrencias de c. Por ejemplo,

   λ> subraya "Salamanca es castellana" 'a'
   Salamanca es castellana
    ^ ^ ^  ^     ^     ^ ^
   λ> subraya "Salamanca es castellana" 'n'
   Salamanca es castellana
         ^              ^ 
   λ> subraya "Salamanca es castellana" ' '
   Salamanca es castellana
            ^  ^

λ> subraya "Salamanca es castellana" 'a'

Salamanca es castellana

^ ^ ^ ^ ^ ^ ^

λ> subraya "Salamanca es castellana" 'n'

Salamanca es castellana

^ ^

λ> subraya "Salamanca es castellana" ' '

Salamanca es castellana

^ ^

Soluciones

-- 1ª definición
subraya :: String -> Char -> IO ()
subraya cs c = do
  putStrLn cs
  putStrLn (subrayado cs c)

subrayado :: String -> Char -> String
subrayado cs c = map procesa cs
  where procesa x | x == c    = '^'
                  | otherwise = ' '

-- 2ª definición
subraya2 :: String -> Char -> IO ()
subraya2 cs c = 
  mapM_ putStrLn [cs, subrayado cs c]

-- 1ª definición

subraya :: String -> Char -> IO ()

subraya cs c = do

putStrLn cs

putStrLn (subrayado cs c)

subrayado :: String -> Char -> String

subrayado cs c = map procesa cs

where procesa x | x == c = '^'

| otherwise = ' '

-- 2ª definición

subraya2 :: String -> Char -> IO ()

subraya2 cs c =

mapM_ putStrLn [cs, subrayado cs c]

Eliminación de triplicados

PorJosé A. Alonso 31-enero-20178-febrero-2017

Definir la función

   sinTriplicados :: Eq a => [a] -> [a]

1	sinTriplicados :: Eq a => [a] -> [a]

tal que (sinTriplicados xs) es la lista obtenida dejando en xs sólo las dos primeras ocurrencias de cada uno de sus elementos. Por ejemplo,

   sinTriplicados "aaabcbccdbabdcd"  ==  "aabcbcdd"
   sinTriplicados "xxxxx"            ==  "xx"
   sinTriplicados "abcabc"           ==  "abcabc"
   sinTriplicados "abcdabcaba"       ==  "abcdabc"
   sinTriplicados "abacbadcba"       ==  "abacbdc"
   sinTriplicados "aaabcbccdbabdcd"  ==  "aabcbcdd"
   sinTriplicados (show (5^4^3))     ==  "54210108624757363989"
   sinTriplicados (show (8^8^8))     ==  "60145207536139279488"

sinTriplicados "aaabcbccdbabdcd" == "aabcbcdd"

sinTriplicados "xxxxx" == "xx"

sinTriplicados "abcabc" == "abcabc"

sinTriplicados "abcdabcaba" == "abcdabc"

sinTriplicados "abacbadcba" == "abacbdc"

sinTriplicados "aaabcbccdbabdcd" == "aabcbcdd"

sinTriplicados (show (5^4^3)) == "54210108624757363989"

sinTriplicados (show (8^8^8)) == "60145207536139279488"

Soluciones

import Data.List (delete)

sinTriplicados :: Eq a => [a] -> [a]
sinTriplicados xs = aux xs [] []
  where aux [] _ _ = []
        aux (x:xs) ys zs
          | x `elem` zs = aux xs ys zs
          | x `elem` ys = x : aux xs (delete x ys) (x:zs)
          | otherwise   = x : aux xs (x:ys) zs

import Data.List (delete)

sinTriplicados :: Eq a => [a] -> [a]

sinTriplicados xs = aux xs [] []

where aux [] _ _ = []

aux (x:xs) ys zs

| x `elem` zs = aux xs ys zs

| x `elem` ys = x : aux xs (delete x ys) (x:zs)

| otherwise = x : aux xs (x:ys) zs

Máximo producto de pares en la lista

PorJosé A. Alonso 30-enero-201726-marzo-2022

Definir la función

  maximoProducto :: [Int] -> Maybe Int

1	maximoProducto :: [Int] -> Maybe Int

tal que (maximoProducto xs) es el mayor elemento de xs que se puede escribir
como producto de dos elementos distintos de xs o Nothing, en el caso de que
ningún elemento de xs se pueda escribir como producto de dos elementos
distintos de xs, donde xs es una lista de números mayores que 0. Por ejemplo,

   maximoProducto [10, 3, 5, 30, 35]       ==  Just 30
   maximoProducto [10, 2, 2, 4, 30, 35]    ==  Just 4
   maximoProducto [17, 2, 1, 35, 30]       ==  Just 35
   maximoProducto [2,4]                    ==  Nothing
   maximoProducto [2, 5, 7, 8]             ==  Nothing
   maximoProducto [10, 2, 4, 30, 35]       ==  Nothing
   maximoProducto [1+2^n | n <- [1..10^6]] ==  Just 4611686018427387905

maximoProducto [10, 3, 5, 30, 35] == Just 30

maximoProducto [10, 2, 2, 4, 30, 35] == Just 4

maximoProducto [17, 2, 1, 35, 30] == Just 35

maximoProducto [2,4] == Nothing

maximoProducto [2, 5, 7, 8] == Nothing

maximoProducto [10, 2, 4, 30, 35] == Nothing

maximoProducto [1+2^n | n <- [1..10^6]] == Just 4611686018427387905

En el primer ejemplo, 30 es el producto de 10 y 3; en el segundo, 4 es el producto de 2 y 2 y en el tercero, 35 es el producto de 1 y 35.

Soluciones

import Data.List (delete, nub, sort)

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

maximoProducto1 :: [Int] -> Maybe Int
maximoProducto1 xs
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where
    ys = reverse (sort xs)
    zs = [y | y <- ys, y `elem` productos xs]

-- (productos xs) es la lista de los números que son productos de dos
-- elementos de xs. Por ejemplo, 
--   productos [4,3,5,2]  ==  [12,20,8,15,6,10]
productos :: [Int] -> [Int]
productos xs =
  nub [y * z | y <- xs, z <- delete y xs]

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

maximoProducto2 :: [Int] -> Maybe Int
maximoProducto2 xs = aux (reverse (sort xs))
  where aux []     = Nothing
        aux (y:ys) | esProducto y xs = Just y
                   | otherwise       = aux ys

esProducto :: Int -> [Int] -> Bool
esProducto y []     = False
esProducto y (x:xs) = 
  (m == 0 && d `elem` xs) || esProducto y xs
  where (d,m) = divMod y x  

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

--    λ> maximoProducto1 [1..10^4]
--    Just 10000
--    (2.60 secs, 0 bytes)
--    λ> maximoProducto2 [1..10^4]
--    Just 10000
--    (0.01 secs, 0 bytes)

import Data.List (delete, nub, sort)

-- 1ª solución

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

maximoProducto1 :: [Int] -> Maybe Int

maximoProducto1 xs

| null zs = Nothing

| otherwise = Just (head zs)

where

ys = reverse (sort xs)

zs = [y | y <- ys, y `elem` productos xs]

-- (productos xs) es la lista de los números que son productos de dos

-- elementos de xs. Por ejemplo,

-- productos [4,3,5,2] == [12,20,8,15,6,10]

productos :: [Int] -> [Int]

productos xs =

nub [y * z | y <- xs, z <- delete y xs]

-- 2ª solución

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

maximoProducto2 :: [Int] -> Maybe Int

maximoProducto2 xs = aux (reverse (sort xs))

where aux [] = Nothing

aux (y:ys) | esProducto y xs = Just y

| otherwise = aux ys

esProducto :: Int -> [Int] -> Bool

esProducto y [] = False

esProducto y (x:xs) =

(m == 0 && d `elem` xs) || esProducto y xs

where (d,m) = divMod y x

-- Comparación de eficiencia

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

-- λ> maximoProducto1 [1..10^4]

-- Just 10000

-- (2.60 secs, 0 bytes)

-- λ> maximoProducto2 [1..10^4]

-- Just 10000

-- (0.01 secs, 0 bytes)

Suma minimal de productos de pares de elementos consecutivos

PorJosé A. Alonso 27-enero-20173-febrero-2017

Al permutar los elementos de la lista [1,2,3,4] se obtienen los siguientes valores de la suma de pares de elementos consecutivos:

10, por ejemplo con [1,4,2,3] ya que 1×4+2×3 = 10
11, por ejemplo con [1,3,2,4] ya que 1×3+2×4 = 11
14, por ejemplo con [1,2,3,4] ya que 1×2+3×4 = 14

Por tanto, la mínima suma de los productos de elementos consecutivos en las permutaciones de [1,2,3,4] es 10 y una permutación con dicha suma es [1,4,2,3].

Definir las funciones

   minimaSumaProductos  :: (Num a, Ord a) => [a] -> a
   permutacionMinimal   :: (Num a, Ord a) => [a] -> [a]

1 2	minimaSumaProductos :: (Num a, Ord a) => [a] -> a permutacionMinimal :: (Num a, Ord a) => [a] -> [a]

tales que

(minimaSumaProductos xs) es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,

     minimaSumaProductos [1..4]             ==  10
     minimaSumaProductos [3,2,5,7,1,6]      ==  34
     minimaSumaProductos [9,2,8,4,5,7,6,0]  ==  74
     minimaSumaProductos [1,2,1,4,0,5,6,0]  ==  6

minimaSumaProductos [1..4] == 10

minimaSumaProductos [3,2,5,7,1,6] == 34

minimaSumaProductos [9,2,8,4,5,7,6,0] == 74

minimaSumaProductos [1,2,1,4,0,5,6,0] == 6

(permutacionMinimal xs) es una permutación de xs cuya suma de productos de elementos consecutivos de xs es la mínima suma de los productos de elementos consecutivos en las permutaciones de lista xs, suponiendo que xs tiene un número par de elementos. Por ejemplo,

     permutacionMinimal [1..4]             ==  [1,4,3,2]
     permutacionMinimal [3,2,5,7,1,6]      ==  [1,7,2,6,3,5]
     permutacionMinimal [9,2,8,4,5,7,6,0]  ==  [0,9,2,8,4,7,5,6]
     permutacionMinimal [1,2,1,4,0,5,6,0]  ==  [0,6,0,5,1,4,1,2]

permutacionMinimal [1..4] == [1,4,3,2]

permutacionMinimal [3,2,5,7,1,6] == [1,7,2,6,3,5]

permutacionMinimal [9,2,8,4,5,7,6,0] == [0,9,2,8,4,7,5,6]

permutacionMinimal [1,2,1,4,0,5,6,0] == [0,6,0,5,1,4,1,2]

Soluciones

import Data.List (sort, permutations)
import Test.QuickCheck

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

minimaSumaProductos :: (Num a, Ord a) => [a] -> a
minimaSumaProductos xs =
  minimum [sumaProductos ys | ys <- permutations xs]

--    sumaProductos [3,2,1,4]  ==  10
--    sumaProductos [2,4,3,1]  ==  11
--    sumaProductos [1,2,3,4]  ==  14
sumaProductos :: (Num a, Ord a) => [a] -> a
sumaProductos []       = 0
sumaProductos [x]      = x
sumaProductos (x:y:zs) = x*y + sumaProductos zs

permutacionMinimal :: (Num a, Ord a) => [a] -> [a]
permutacionMinimal xs =
  head [ys | ys <- yss
           , sumaProductos ys == m]
  where yss = permutations xs
        m   = minimaSumaProductos xs

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

permutacionMinimal2 :: (Num a, Ord a) => [a] -> [a]
permutacionMinimal2 xs =
  intercala ys (reverse zs)
  where n = length xs
        (ys,zs) = splitAt (n `div` 2) (sort xs)

intercala :: [a] -> [a] -> [a]
intercala xs ys =
  concat [[x,y] | (x,y) <- zip xs ys]

minimaSumaProductos2 :: (Num a, Ord a) => [a] -> a
minimaSumaProductos2 =
  sumaProductos . permutacionMinimal2

-- Equivalencia
-- ============

prop_equivalencia :: [Int] -> Property
prop_equivalencia xs =
  even (length xs) ==>
  minimaSumaProductos xs == minimaSumaProductos2 xs

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=10}) prop_equivalencia
--    +++ OK, passed 100 tests.

import Data.List (sort, permutations)

import Test.QuickCheck

-- 1ª definición

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

minimaSumaProductos :: (Num a, Ord a) => [a] -> a

minimaSumaProductos xs =

minimum [sumaProductos ys | ys <- permutations xs]

-- sumaProductos [3,2,1,4] == 10

-- sumaProductos [2,4,3,1] == 11

-- sumaProductos [1,2,3,4] == 14

sumaProductos :: (Num a, Ord a) => [a] -> a

sumaProductos [] = 0

sumaProductos [x] = x

sumaProductos (x:y:zs) = x*y + sumaProductos zs

permutacionMinimal :: (Num a, Ord a) => [a] -> [a]

permutacionMinimal xs =

head [ys | ys <- yss

, sumaProductos ys == m]

where yss = permutations xs

m = minimaSumaProductos xs

-- 2ª definición

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

permutacionMinimal2 :: (Num a, Ord a) => [a] -> [a]

permutacionMinimal2 xs =

intercala ys (reverse zs)

where n = length xs

(ys,zs) = splitAt (n `div` 2) (sort xs)

intercala :: [a] -> [a] -> [a]

intercala xs ys =

concat [[x,y] | (x,y) <- zip xs ys]

minimaSumaProductos2 :: (Num a, Ord a) => [a] -> a

minimaSumaProductos2 =

sumaProductos . permutacionMinimal2

-- Equivalencia

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

prop_equivalencia :: [Int] -> Property

prop_equivalencia xs =

even (length xs) ==>

minimaSumaProductos xs == minimaSumaProductos2 xs

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=10}) prop_equivalencia

-- +++ OK, passed 100 tests.

Máxima potencia que divide al factorial

PorJosé A. Alonso 26-enero-20172-febrero-2017

La máxima potencia de 2 que divide al factorial de 5 es 3, ya que 5! = 120, 120 es divisible por 2^3 y no lo es por 2^4.

Definir la función

   maxPotDivFact :: Integer -> Integer -> Integer

1	maxPotDivFact :: Integer -> Integer -> Integer

tal que (maxPotDivFact p n), para cada primo p, es el mayor k tal que p^k divide al factorial de n. Por ejemplo,

   maxPotDivFact 2 5       ==  3
   maxPotDivFact 3 6       ==  2
   maxPotDivFact 2 10      ==  8
   maxPotDivFact 3 10      ==  4
   maxPotDivFact 2 (10^2)  ==  97
   maxPotDivFact 2 (10^3)  ==  994
   maxPotDivFact 2 (10^4)  ==  9995
   maxPotDivFact 2 (10^5)  ==  99994
   maxPotDivFact 2 (10^6)  ==  999993
   maxPotDivFact 3 (10^5)  ==  49995
   maxPotDivFact 3 (10^6)  ==  499993
   maxPotDivFact 7 (10^5)  ==  16662
   maxPotDivFact 7 (10^6)  ==  166664
   length (show (maxPotDivFact 2 (10^20000)))  ==  20000

maxPotDivFact 2 5 == 3

maxPotDivFact 3 6 == 2

maxPotDivFact 2 10 == 8

maxPotDivFact 3 10 == 4

maxPotDivFact 2 (10^2) == 97

maxPotDivFact 2 (10^3) == 994

maxPotDivFact 2 (10^4) == 9995

maxPotDivFact 2 (10^5) == 99994

maxPotDivFact 2 (10^6) == 999993

maxPotDivFact 3 (10^5) == 49995

maxPotDivFact 3 (10^6) == 499993

maxPotDivFact 7 (10^5) == 16662

maxPotDivFact 7 (10^6) == 166664

length (show (maxPotDivFact 2 (10^20000))) == 20000

Soluciones

import Data.List (genericIndex, genericTake)
import Data.Numbers.Primes (primes)
import Test.QuickCheck

-- 1ª definición
maxPotDivFact :: Integer -> Integer -> Integer
maxPotDivFact p n =
  head [k | k <- [0..], f `mod` (p^k) /= 0] - 1
  where f = product [1..n]

-- 1ª definición
maxPotDivFact2 :: Integer -> Integer -> Integer
maxPotDivFact2 p n
  | n < p     = 0
  | otherwise = m + maxPotDivFact2 p m
  where m = n `div` p  
  
-- 3ª definición
maxPotDivFact3 :: Integer -> Integer -> Integer
maxPotDivFact3 p = sum . takeWhile (> 0) . tail . iterate (`div` p)

-- Comparación de eficiencia
--    λ> maxPotDivFact 2 (10^4)
--    9995
--    (5.47 secs, 161,040,624 bytes)
--    λ> maxPotDivFact2 2 (10^4)
--    9995
--    (0.01 secs, 0 bytes)
--    λ> maxPotDivFact2 2 (10^4)
--    9995
--    (0.01 secs, 0 bytes)
--
--    λ> length (show (maxPotDivFact2 2 (10^20000)))
--    20000
--    (1.93 secs, 592,168,544 bytes)
--    λ> length (show (maxPotDivFact3 2 (10^20000)))
--    20000
--    (2.93 secs, 861,791,504 bytes)

import Data.List (genericIndex, genericTake)

import Data.Numbers.Primes (primes)

import Test.QuickCheck

-- 1ª definición

maxPotDivFact :: Integer -> Integer -> Integer

maxPotDivFact p n =

head [k | k <- [0..], f `mod` (p^k) /= 0] - 1

where f = product [1..n]

-- 1ª definición

maxPotDivFact2 :: Integer -> Integer -> Integer

maxPotDivFact2 p n

| n < p = 0

| otherwise = m + maxPotDivFact2 p m

where m = n `div` p

-- 3ª definición

maxPotDivFact3 :: Integer -> Integer -> Integer

maxPotDivFact3 p = sum . takeWhile (> 0) . tail . iterate (`div` p)

-- Comparación de eficiencia

-- λ> maxPotDivFact 2 (10^4)

-- 9995

-- (5.47 secs, 161,040,624 bytes)

-- λ> maxPotDivFact2 2 (10^4)

-- 9995

-- (0.01 secs, 0 bytes)

-- λ> maxPotDivFact2 2 (10^4)

-- 9995

-- (0.01 secs, 0 bytes)

-- λ> length (show (maxPotDivFact2 2 (10^20000)))

-- 20000

-- (1.93 secs, 592,168,544 bytes)

-- λ> length (show (maxPotDivFact3 2 (10^20000)))

-- 20000

-- (2.93 secs, 861,791,504 bytes)

Árboles continuos

PorJosé A. Alonso 25-enero-20171-febrero-2017

Los árboles binarios se pueden representar con el de tipo de dato algebraico

   data Arbol a = H
                | N a (Arbol a) (Arbol a)
     deriving Show

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving Show

Por ejemplo, los árboles

       3                7     
      / \              / \    
     2   4            5   8   
    / \   \          / \   \  
   1   3   5        6   4   10

3 7

/ \ / \

2 4 5 8

/ \ \ / \ \

1 3 5 6 4 10

se representan por

   ej1, ej2 :: Arbol Int
   ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
   ej2 = N 7 (N 5 (N 6 H H) (N 4 H H)) (N 8 H (N 10 H H))

ej1, ej2 :: Arbol Int

ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))

ej2 = N 7 (N 5 (N 6 H H) (N 4 H H)) (N 8 H (N 10 H H))

Un árbol binario es continuo si el valor absoluto de la diferencia de los elementos adyacentes es 1. Por ejemplo, el árbol ej1 es continuo ya que el valor absoluto de sus pares de elementos adyacentes son

   |3-2| = |2-1| = |2-3| = |3-4| = |4-5| = 1

1	\|3-2\| = \|2-1\| = \|2-3\| = \|3-4\| = \|4-5\| = 1

En cambio, el ej2 no lo es ya que |8-10| ≠ 1.

Definir la función

   esContinuo :: (Num a, Eq a) => Arbol a -> Bool

1	esContinuo :: (Num a, Eq a) => Arbol a -> Bool

tal que (esContinuo x) se verifica si el árbol x es continuo. Por ejemplo,

   esContinuo ej1  ==  True
   esContinuo ej2  ==  False

1 2	esContinuo ej1 == True esContinuo ej2 == False

Soluciones

data Arbol a = H
             | N a (Arbol a) (Arbol a)
  deriving Show

ej1, ej2 :: Arbol Int
ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))
ej2 = N 7 (N 5 (N 6 H H) (N 4 H H)) (N 8 H (N 10 H H))

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

esContinuo :: (Num a, Eq a) => Arbol a -> Bool
esContinuo H         = True
esContinuo (N _ H H) = True
esContinuo (N x i@(N y _ _) H) =
  abs (x - y) == 1 && esContinuo i
esContinuo (N x H d@(N y _ _)) =
  abs (x - y) == 1 && esContinuo d
esContinuo (N x i@(N y _ _) d@(N z _ _)) =
  abs (x - y) == 1 && esContinuo i && abs (x - z) == 1 && esContinuo d 

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

esContinuo2 :: (Num a, Eq a) => Arbol a -> Bool
esContinuo2 x =
  all esContinua (ramas x)

-- (ramas x) es la lista de las ramas del árbol x. Por ejemplo,
--    ramas ej1  ==  [[3,2,1],[3,2,3],[3,4,5]]
--    ramas ej2  ==  [[7,5,6],[7,5,4],[7,8,10]]
ramas :: Arbol a -> [[a]]
ramas H         = []
ramas (N x H H) = [[x]]
ramas (N x i d) = [x : xs | xs <- ramas i ++ ramas d]

-- (esContinua xs) se verifica si el valor absoluto de la diferencia de
-- los elementos adyacentes de xs es 1. Por ejemplo, 
--    esContinua [3,2,3]   ==  True
--    esContinua [7,8,10]  ==  False
esContinua :: (Num a, Eq a) => [a] -> Bool
esContinua xs =
  and [abs (x - y) == 1 | (x, y) <- zip xs (tail xs)]

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving Show

ej1, ej2 :: Arbol Int

ej1 = N 3 (N 2 (N 1 H H) (N 3 H H)) (N 4 H (N 5 H H))

ej2 = N 7 (N 5 (N 6 H H) (N 4 H H)) (N 8 H (N 10 H H))

-- 1ª solución

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

esContinuo :: (Num a, Eq a) => Arbol a -> Bool

esContinuo H = True

esContinuo (N _ H H) = True

esContinuo (N x i@(N y _ _) H) =

abs (x - y) == 1 && esContinuo i

esContinuo (N x H d@(N y _ _)) =

abs (x - y) == 1 && esContinuo d

esContinuo (N x i@(N y _ _) d@(N z _ _)) =

abs (x - y) == 1 && esContinuo i && abs (x - z) == 1 && esContinuo d

-- 2ª solución

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

esContinuo2 :: (Num a, Eq a) => Arbol a -> Bool

esContinuo2 x =

all esContinua (ramas x)

-- (ramas x) es la lista de las ramas del árbol x. Por ejemplo,

-- ramas ej1 == [[3,2,1],[3,2,3],[3,4,5]]

-- ramas ej2 == [[7,5,6],[7,5,4],[7,8,10]]

ramas :: Arbol a -> [[a]]

ramas H = []

ramas (N x H H) = [[x]]

ramas (N x i d) = [x : xs | xs <- ramas i ++ ramas d]

-- (esContinua xs) se verifica si el valor absoluto de la diferencia de

-- los elementos adyacentes de xs es 1. Por ejemplo,

-- esContinua [3,2,3] == True

-- esContinua [7,8,10] == False

esContinua :: (Num a, Eq a) => [a] -> Bool

esContinua xs =

and [abs (x - y) == 1 | (x, y) <- zip xs (tail xs)]

Referencias

Basado en Continuous tree de GeeksforGeeks.

La sucesión «Mira y di»

PorJosé A. Alonso 24-enero-201731-enero-2017

La sucesión «Mira y di» (en inglés, Look-and-Say) es una sucesión de números naturales en donde cada término se obtiene agrupando las cifras iguales del anterior y recitándolas. Por ejemplo, si x(0) = 1 se lee como «un uno» y por tanto x(1) = 11. Análogamente,

   x(1) = 11     ("dos unos                          --> "21")
   x(2) = 21     ("un dos un uno                     --> "1211")
   x(3) = 1211   ("un uno un dos dos unos            --> "111221")
   x(4) = 111221 ("tres unos dos doses un uno        --> "312211")
   x(5) = 312211 ("un tres un uno dos doses dos unos --> "13112221")

x(1) = 11 ("dos unos --> "21")

x(2) = 21 ("un dos un uno --> "1211")

x(3) = 1211 ("un uno un dos dos unos --> "111221")

x(4) = 111221 ("tres unos dos doses un uno --> "312211")

x(5) = 312211 ("un tres un uno dos doses dos unos --> "13112221")

Definir la función

  sucMiraYDi :: Integer -> [Integer]

1	sucMiraYDi :: Integer -> [Integer]

tal que (sucMiraYDi n) es la sucesión «Mira y di» cuyo primer término es n. Por ejemplo,

   λ> take 9 (sucMiraYdi 1)
   [1,11,21,1211,111221,312211,13112221,1113213211,31131211131221]
   λ> take 5 (sucMiraYdi 2017)
   [2017,12101117,111211103117,31123110132117,1321121321101113122117]
   λ> take 7 (sucMiraYDi 22)
   [22,22,22,22,22,22,22]
   λ> (sucMiraYDi 1) !! 11
   3113112221232112111312211312113211
   λ> (sucMiraYDi 1) !! 12
   1321132132111213122112311311222113111221131221

λ> take 9 (sucMiraYdi 1)

[1,11,21,1211,111221,312211,13112221,1113213211,31131211131221]

λ> take 5 (sucMiraYdi 2017)

[2017,12101117,111211103117,31123110132117,1321121321101113122117]

λ> take 7 (sucMiraYDi 22)

[22,22,22,22,22,22,22]

λ> (sucMiraYDi 1) !! 11

3113112221232112111312211312113211

λ> (sucMiraYDi 1) !! 12

1321132132111213122112311311222113111221131221

Independientemente del término inicial x(0) elegido (con la única salvedad del 22), la sucesión diverge y la razón entre el número de cifras de x(n) y el de x(n-1) tiende a un valor fijo que es la constante de Conway λ ≈ 1.303577269. Por ejemplo, para x(0) = 1, las razones son

   2, 1, 2, 1.5, 1, 1.3333333333333333, 1.25, 1.4, 1.4285714285714286, 1.3

1	2, 1, 2, 1.5, 1, 1.3333333333333333, 1.25, 1.4, 1.4285714285714286, 1.3

Definir la función

   aproximacionConway :: Integer -> Double -> Int

1	aproximacionConway :: Integer -> Double -> Int

tal que (aproximacionConway n e) es el menor k tal que la diferencia entre la constante de Conway y la razón entre el número de cifras de x(k) x(k-1) es, en valor absoluto, menor que e. Por ejemplo,

   aproximacionConway 1 0.3     ==  3
   aproximacionConway 1 0.1     ==  5
   aproximacionConway 1 0.01    ==  9
   aproximacionConway 1 0.001   ==  24
   aproximacionConway 1 0.0001  ==  43
   aproximacionConway 2 0.0001  ==  47

aproximacionConway 1 0.3 == 3

aproximacionConway 1 0.1 == 5

aproximacionConway 1 0.01 == 9

aproximacionConway 1 0.001 == 24

aproximacionConway 1 0.0001 == 43

aproximacionConway 2 0.0001 == 47

Nota: Este ejercicio ha sido propuesto por Elías Guisado.

Soluciones

import Data.List (genericLength, group)

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

sucMiraYdi :: Integer -> [Integer]
sucMiraYdi = iterate di

-- (di x) es el número correspondiente a la lectura de x. Por ejemplo.
--    di 1       ==  11
--    di 11      ==  21
--    di 21      ==  1211
--    di 1211    ==  111221
--    di 111221  ==  312211
--    di 312211  ==  13112221
di :: Integer -> Integer
di = read . concatMap aux . group . show
  where aux s = show (length s) ++ [head s]

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

sucMiraYdi2 :: Integer -> [Integer]
sucMiraYdi2 = iterate (read . concatMap aux . group . show)
  where aux s = show (length s) ++ [head s]

-- Constante de Conway
-- ===================

aproximacionConway :: Integer -> Double -> Int
aproximacionConway n e =
  length (takeWhile aux (razonesMiraYdi n))
  where aux x = abs (x - constanteConway) > e 

constanteConway :: Double
constanteConway = 1.303577269

-- (razonesMiraYdi n) es la sucesión de las razones entre de cada
-- elemento de la sucesión "Mira y di" con elemento inicial n y su
-- anterior. Por ejemplo,
--    λ> take 10 (razonesMiraYdi 1)
--    [2.0,1.0,2.0,1.5,1.0,1.3333333333333333,1.25,1.4,1.4285714285714286,1.3]
--    λ> take 7 (razonesMiraYdi 10)
--    [2.0,1.0,1.5,1.6666666666666667,1.2,1.1666666666666667,1.5714285714285714]
razonesMiraYdi :: Integer -> [Double]
razonesMiraYdi n =
  zipWith (/) (tail xs) xs
  where xs = map (genericLength . show) (sucMiraYdi n)

import Data.List (genericLength, group)

-- 1ª solución

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

sucMiraYdi :: Integer -> [Integer]

sucMiraYdi = iterate di

-- (di x) es el número correspondiente a la lectura de x. Por ejemplo.

-- di 1 == 11

-- di 11 == 21

-- di 21 == 1211

-- di 1211 == 111221

-- di 111221 == 312211

-- di 312211 == 13112221

di :: Integer -> Integer

di = read . concatMap aux . group . show

where aux s = show (length s) ++ [head s]

-- 2ª solución

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

sucMiraYdi2 :: Integer -> [Integer]

sucMiraYdi2 = iterate (read . concatMap aux . group . show)

where aux s = show (length s) ++ [head s]

-- Constante de Conway

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

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n e =

length (takeWhile aux (razonesMiraYdi n))

where aux x = abs (x - constanteConway) > e

constanteConway :: Double

constanteConway = 1.303577269

-- (razonesMiraYdi n) es la sucesión de las razones entre de cada

-- elemento de la sucesión "Mira y di" con elemento inicial n y su

-- anterior. Por ejemplo,

-- λ> take 10 (razonesMiraYdi 1)

-- [2.0,1.0,2.0,1.5,1.0,1.3333333333333333,1.25,1.4,1.4285714285714286,1.3]

-- λ> take 7 (razonesMiraYdi 10)

-- [2.0,1.0,1.5,1.6666666666666667,1.2,1.1666666666666667,1.5714285714285714]

razonesMiraYdi :: Integer -> [Double]

razonesMiraYdi n =

zipWith (/) (tail xs) xs

where xs = map (genericLength . show) (sucMiraYdi n)

Cadena de primos

PorJosé A. Alonso 23-enero-201730-enero-2017

La lista de los primeros números primos es

   [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

1	[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71]

Los primeros elementos de la cadena obtenida concatenado los números primos es

   "23571113171923293137414347535961677173798389971011"

1	"23571113171923293137414347535961677173798389971011"

Definir la función

   primoEnPosicion :: Int -> Integer

1	primoEnPosicion :: Int -> Integer

tal que (primoEnPosicion n) es el número primo que tiene algún dígito en la posición n de la cadena obtenida concatenado los números primos. Por ejemplo,

   primoEnPosicion 0       ==  2
   primoEnPosicion 1       ==  3
   primoEnPosicion 4       ==  11
   primoEnPosicion 5       ==  11
   primoEnPosicion 6       ==  13
   primoEnPosicion 1022    ==  2011
   primoEnPosicion 1023    ==  2017
   primoEnPosicion 1026    ==  2017
   primoEnPosicion 1027    ==  2027
   primoEnPosicion (10^7)  ==  21242357

primoEnPosicion 0 == 2

primoEnPosicion 1 == 3

primoEnPosicion 4 == 11

primoEnPosicion 5 == 11

primoEnPosicion 6 == 13

primoEnPosicion 1022 == 2011

primoEnPosicion 1023 == 2017

primoEnPosicion 1026 == 2017

primoEnPosicion 1027 == 2027

primoEnPosicion (10^7) == 21242357

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck

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

primoEnPosicion :: Int -> Integer
primoEnPosicion = aux primes
  where aux (x:xs) n | m > n     = x
                     | otherwise = aux xs (n-m)
          where m = length (show x)


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

primoEnPosicion2 :: Int -> Integer
primoEnPosicion2 n = p
  where (p,_) = head $ dropWhile (\(x,k) -> k < n) primosYfinales

-- primosYfinales es la sucesión de los pares de los números primos y
-- las posiciones de sus dígitos finales en la sucesión de la
-- concatenación de primos. Por ejemplo, 
--    λ> take 10 primosYfinales
--    [(2,0),(3,1),(5,2),(7,3),(11,5),(13,7),(17,9),(19,11),(23,13),(29,15)]
primosYfinales :: [(Integer, Int)]
primosYfinales = scanl f (2,0) (tail primes)
  where f (p,k) q = (q, k + length (show q))

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

-- La propiedad es
prop_equivalencia (Positive n) =
  primoEnPosicion n == primoEnPosicion2 n

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

import Data.Numbers.Primes

import Test.QuickCheck

-- 1ª definición

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

primoEnPosicion :: Int -> Integer

primoEnPosicion = aux primes

where aux (x:xs) n | m > n = x

| otherwise = aux xs (n-m)

where m = length (show x)

-- 2ª definición

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

primoEnPosicion2 :: Int -> Integer

primoEnPosicion2 n = p

where (p,_) = head $ dropWhile (\(x,k) -> k < n) primosYfinales

-- primosYfinales es la sucesión de los pares de los números primos y

-- las posiciones de sus dígitos finales en la sucesión de la

-- concatenación de primos. Por ejemplo,

-- λ> take 10 primosYfinales

-- [(2,0),(3,1),(5,2),(7,3),(11,5),(13,7),(17,9),(19,11),(23,13),(29,15)]

primosYfinales :: [(Integer, Int)]

primosYfinales = scanl f (2,0) (tail primes)

where f (p,k) q = (q, k + length (show q))

-- Comprobación de equivalencia

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

-- La propiedad es

prop_equivalencia (Positive n) =

primoEnPosicion n == primoEnPosicion2 n

-- La comprobación es

-- λ> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

Notación polaca inversa

PorJosé A. Alonso 20-enero-201727-enero-2017

La notación polaca inversa (en inglés, Reverse Polish Notation, o RPN), es una forma alternativa de escribir expresiones matemáticas. Por ejemplo, la expresión "20 - (4 + 3) * 2" en RPN es "20 4 3 + 2 * -".

Para evaluar una expresión en RPN, usamos una lista auxiliar (inicialmente vacía) y recorremos la expresión de izquierda a derecha. Cada vez que encontramos un número, lo añadimos a la lista auxiliar. Cuando encontramos un operador, retiramos los dos números que hay al principio de la pila, utilizamos el operador con ellos y los quitamos de la lista y le añadimos el resultado. Cuando alcancemos el final de la expresión, debemos tener un solo número en la lista auxiliar si la expresión estaba bien formada, y éste representa el resultado de la expresión. Por ejemplo, la evaluación de RPN "20 4 3 + 2 * -" es la siguiente

   ""                 []
   "20"               [20]
   "20 4"             [4, 20]
   "20 4 3"           [3, 4, 20]
   "20 4 3 +"         [7, 20]
   "20 4 3 + 2"       [2, 7, 20]
   "20 4 3 + 2 *"     [14, 20]
   "20 4 3 + 2 * -"   [6]

"" []

"20" [20]

"20 4" [4, 20]

"20 4 3" [3, 4, 20]

"20 4 3 +" [7, 20]

"20 4 3 + 2" [2, 7, 20]

"20 4 3 + 2 *" [14, 20]

"20 4 3 + 2 * -" [6]

Definir la función

   valor :: String -> Float

1	valor :: String -> Float

tal que (valor cs) es el valor de la expresión RPN cs. Por ejemplo,

   valor "4"               ==  4.0
   valor "4 3 +"           ==  7.0
   valor "4 3 + 2 *"       ==  14.0
   valor "20 4 3 + 2 * -"  ==  6.0
   valor "3 7 + 2 /"       ==  5.0

valor "4" == 4.0

valor "4 3 +" == 7.0

valor "4 3 + 2 *" == 14.0

valor "20 4 3 + 2 * -" == 6.0

valor "3 7 + 2 /" == 5.0

Soluciones

valor :: String -> Float
valor = head . foldl aux [] . words
  where aux (x:y:ys) "+" = (x + y) : ys
        aux (x:y:ys) "-" = (y - x) : ys
        aux (x:y:ys) "*" = (x * y) : ys
        aux (x:y:ys) "/" = (y / x) : ys
        aux xs cs        = read cs : xs

valor :: String -> Float

valor = head . foldl aux [] . words

where aux (x:y:ys) "+" = (x + y) : ys

aux (x:y:ys) "-" = (y - x) : ys

aux (x:y:ys) "*" = (x * y) : ys

aux (x:y:ys) "/" = (y / x) : ys

aux xs cs = read cs : xs

La conjetura de Rodolfo

PorJosé A. Alonso 19-enero-201726-enero-2017

El pasado 1 de enero, Claudio Meller publicó el artículo La conjetura de Rodolfo que afirma que

Todos los números naturales se pueden números pueden expresarse como la suma de un capicúa y un capicúa especial (siendo los capicúas especiales los números que al quitarles los ceros finales son capicúas; por ejemplo, 32300, 50500 y 78987).

Definir las funciones

   descomposiciones               :: Integer -> [(Integer, Integer)]
   contraejemplosConjeturaRodolfo :: [Integer]

1 2	descomposiciones :: Integer -> [(Integer, Integer)] contraejemplosConjeturaRodolfo :: [Integer]

tales que

(descomposiciones x) es la lista de las descomposiciones de x como la suma de un capicúa y un capicúa especial. Por ejemplo,

     descomposiciones 1980  ==  [(99,1881),(979,1001)]
     descomposiciones 2016  ==  [(575,1441),(606,1410)]
     descomposiciones 1971  ==  [(161,1810),(1771,200),(1881,90)]

descomposiciones 1980 == [(99,1881),(979,1001)]

descomposiciones 2016 == [(575,1441),(606,1410)]

descomposiciones 1971 == [(161,1810),(1771,200),(1881,90)]

contraejemplosConjeturaRodolfo es la lista de contraejemplos de la conjetura de Rodolfo; es decir, de los números que no pueden expresarse com la suma de un capicúa y un capicúa especial. Por ejemplo,

     λ> take 12 contraejemplosConjeturaRodolfo
     [1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
     λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
     [3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

λ> take 12 contraejemplosConjeturaRodolfo

[1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]

λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)

[3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

Soluciones

import Data.List (nub)

descomposiciones :: Integer -> [(Integer, Integer)]
descomposiciones x =
  reducida [(y,z) | y <- takeWhile (<= x) capicuas
                  , let z = x - y
                  , esCapicuaG z]

-- capicuas es la sucesión de los números capicúas. Por ejemplo,
--    λ> take 45 capicuas
--    [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,
--     141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,
--     303,313,323,333,343,353]
-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".
capicuas :: [Integer]
capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número
-- par de dígitos. Por ejemplo,  
--    λ> take 17 capicuasPares
--    [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]
capicuasPares :: [Integer]
capicuasPares =
  [read (ns ++ reverse ns) | n <- [0..]
                           , let ns = show n]   

-- capicuasImpares es la sucesión de las capicúas con un número
-- impar de dígitos a partir de 1. Por ejemplo,  
--    λ> take 20 capicuasImpares
--    [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]
capicuasImpares :: [Integer]
capicuasImpares =
  [1..9] ++ [read (ns ++ [z] ++ reverse ns)
            | n <- [1..]
            , let ns = show n
            , z <- "0123456789"]   

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos
-- distintos. Por ejemplo,
--    take 10 (mezcla [2,12..] [5,15..])  ==  [2,5,12,15,22,25,32,35,42,45]
--    take 10 (mezcla [2,22..] [5,15..])  ==  [2,5,15,22,25,35,42,45,55,62]
mezcla :: Ord a => [a] -> [a] -> [a]
mezcla us@(x:xs) vs@(y:ys)
  | x < y     = x : mezcla xs vs
  | otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,
--    esCapicua 353   ==  True
--    esCapicua 3553  ==  True
--    esCapicua 3535  ==  False
esCapicua :: Integer -> Bool
esCapicua x =
  xs == reverse xs
  where xs = show x

esCapicuaG :: Integer -> Bool
esCapicuaG x =
  x == 0 || esCapicua (sinCerosFinales x)

--    sinCerosFinales 3405000  ==  3405
sinCerosFinales :: Integer -> Integer
sinCerosFinales x =
  read (reverse (dropWhile (== '0') (reverse (show x))))

reducida :: [(Integer, Integer)] -> [(Integer, Integer)]
reducida ps =
  nub [(x,y) | (x,y) <- ps
             , x <= y]

--    λ> take 12 contraejemplosConjeturaRodolfo
--    [1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]
--    λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)
--    [3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]
contraejemplosConjeturaRodolfo :: [Integer]
contraejemplosConjeturaRodolfo =
  [x | x <- [0..]
  , null (descomposiciones x)]

import Data.List (nub)

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

descomposiciones x =

reducida [(y,z) | y <- takeWhile (<= x) capicuas

, let z = x - y

, esCapicuaG z]

-- capicuas es la sucesión de los números capicúas. Por ejemplo,

-- λ> take 45 capicuas

-- [0,1,2,3,4,5,6,7,8,9,11,22,33,44,55,66,77,88,99,101,111,121,131,

-- 141,151,161,171,181,191,202,212,222,232,242,252,262,272,282,292,

-- 303,313,323,333,343,353]

-- Se usará la 2ª definición del ejercicio "Sucesión de capicúas".

capicuas :: [Integer]

capicuas = capicuasImpares `mezcla` capicuasPares

-- capicuasPares es la sucesión del cero y las capicúas con un número

-- par de dígitos. Por ejemplo,

-- λ> take 17 capicuasPares

-- [0,11,22,33,44,55,66,77,88,99,1001,1111,1221,1331,1441,1551,1661]

capicuasPares :: [Integer]

capicuasPares =

[read (ns ++ reverse ns) | n <- [0..]

, let ns = show n]

-- capicuasImpares es la sucesión de las capicúas con un número

-- impar de dígitos a partir de 1. Por ejemplo,

-- λ> take 20 capicuasImpares

-- [1,2,3,4,5,6,7,8,9,101,111,121,131,141,151,161,171,181,191,202]

capicuasImpares :: [Integer]

capicuasImpares =

[1..9] ++ [read (ns ++ [z] ++ reverse ns)

| n <- [1..]

, let ns = show n

, z <- "0123456789"]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas

-- ordenadas xs e ys, suponiendo que ambas son infinitas y con elementos

-- distintos. Por ejemplo,

-- take 10 (mezcla [2,12..] [5,15..]) == [2,5,12,15,22,25,32,35,42,45]

-- take 10 (mezcla [2,22..] [5,15..]) == [2,5,15,22,25,35,42,45,55,62]

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla us@(x:xs) vs@(y:ys)

| x < y = x : mezcla xs vs

| otherwise = y : mezcla us ys

-- (esCapicua x) se verifica si x es capicúa. Por ejemplo,

-- esCapicua 353 == True

-- esCapicua 3553 == True

-- esCapicua 3535 == False

esCapicua :: Integer -> Bool

esCapicua x =

xs == reverse xs

where xs = show x

esCapicuaG :: Integer -> Bool

esCapicuaG x =

x == 0 || esCapicua (sinCerosFinales x)

-- sinCerosFinales 3405000 == 3405

sinCerosFinales :: Integer -> Integer

sinCerosFinales x =

read (reverse (dropWhile (== '0') (reverse (show x))))

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

reducida ps =

nub [(x,y) | (x,y) <- ps

, x <= y]

-- λ> take 12 contraejemplosConjeturaRodolfo

-- [1200,1220,1240,1250,1260,1270,1280,1290,1300,1330,1350,1360]

-- λ> take 12 (dropWhile (< 2000) contraejemplosConjeturaRodolfo)

-- [3020,3240,3350,3460,3570,3680,3920,4030,4250,4360,4470,4580]

contraejemplosConjeturaRodolfo :: [Integer]

contraejemplosConjeturaRodolfo =

[x | x <- [0..]

, null (descomposiciones x)]

Sustitución en una posición

PorJosé A. Alonso 18-enero-201725-marzo-2022

Los árboles binarios se pueden representar con el de dato algebraico

   data Arbol a = H
                | N a (Arbol a) (Arbol a)
                deriving Show

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving Show

Por ejemplo, los árboles

        9                9                
       / \              / 
      /   \            /  
     8     6          8  
    / \   / \        / \ 
   3   2 4   5      3   2

9 9

/ \ /

8 6 8

/ \ / \ / \

3 2 4 5 3 2

se pueden representar por

   ej1, ej2:: Arbol Int
   ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
   ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H

ej1, ej2:: Arbol Int

ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H

Para indicar las posiciones del árbol se define el tipo

  type Posicion = [Direccion]

1	type Posicion = [Direccion]

donde

  data Direccion = D | I
    deriving Eq

1 2	data Direccion = D \| I deriving Eq

representa un movimiento hacia la derecha (D) o a la izquierda. Por ejemplo, las posiciones de los elementos del ej1 son

  9 [] 
  8 [I]
  3 [I,I]
  2 [I,D]
  6 [D]
  4 [D,I]
  5 [D,D]

9 []

8 [I]

3 [I,I]

2 [I,D]

6 [D]

4 [D,I]

5 [D,D]

Definir la función

   sustitucion :: Posicion -> a -> Arbol a -> Arbol a

1	sustitucion :: Posicion -> a -> Arbol a -> Arbol a

tal que (sustitucion ds z x) es el árbol obtenido sustituyendo el elemento de x en la posición ds por z. Por ejemplo,

  λ> sustitucion [I,D] 7 ej1
  N 9 (N 8 (N 3 H H) (N 7 H H)) (N 6 (N 4 H H) (N 5 H H))
  λ> sustitucion [D,D] 7 ej1
  N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 7 H H))
  λ> sustitucion [I] 7 ej1
  N 9 (N 7 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
  λ> sustitucion [] 7 ej1
  N 7 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

λ> sustitucion [I,D] 7 ej1

N 9 (N 8 (N 3 H H) (N 7 H H)) (N 6 (N 4 H H) (N 5 H H))

λ> sustitucion [D,D] 7 ej1

N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 7 H H))

λ> sustitucion [I] 7 ej1

N 9 (N 7 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

λ> sustitucion [] 7 ej1

N 7 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

Soluciones

data Arbol a = H | N a (Arbol a) (Arbol a)
  deriving (Eq, Show)

ej1, ej2:: Arbol Int
ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))
ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H

data Direccion = D | I
  deriving Eq

type Posicion = [Direccion]

sustitucion :: Posicion  -> a -> Arbol a -> Arbol a
sustitucion (I:ds) z (N x i d) = N x (sustitucion ds z i) d
sustitucion (D:ds) z (N x i d) = N x i (sustitucion ds z d)
sustitucion []     z (N _ i d) = N z i d

data Arbol a = H | N a (Arbol a) (Arbol a)

deriving (Eq, Show)

ej1, ej2:: Arbol Int

ej1 = N 9 (N 8 (N 3 H H) (N 2 H H)) (N 6 (N 4 H H) (N 5 H H))

ej2 = N 9 (N 8 (N 3 H H) (N 2 H H)) H

data Direccion = D | I

deriving Eq

type Posicion = [Direccion]

sustitucion :: Posicion -> a -> Arbol a -> Arbol a

sustitucion (I:ds) z (N x i d) = N x (sustitucion ds z i) d

sustitucion (D:ds) z (N x i d) = N x i (sustitucion ds z d)

sustitucion [] z (N _ i d) = N z i d

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Referencia

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Referencia

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Referencias

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico