Test.QuickCheck – Página 4

Múltiplos repitunos

PorJosé A. Alonso 26-marzo-201825-marzo-2022

El ejercicio 4 de la Olimpiada Matemáticas de 1993 es el siguiente:

Demostrar que para todo número primo p distinto de 2 y de 5, existen infinitos múltiplos de p de la forma 1111……1 (escrito sólo con unos).

Definir la función

   multiplosRepitunos :: Integer -> Integer -> [Integer]

1	multiplosRepitunos :: Integer -> Integer -> [Integer]

tal que (multiplosRepitunos p n) es la lista de los múltiplos repitunos de p (es decir, de la forma 1111…1 escrito sólo con unos), donde p es un número primo distinto de 2 y 5. Por ejemplo,

   head (multiplosRepitunos  7 10)       == 111111
   head (multiplosRepitunos  7 (10^10))  == 111111111111
   head (multiplosRepitunos  7 (10^20))  == 111111111111111111111111
   head (multiplosRepitunos 19 (10^10))  == 111111111111111111

head (multiplosRepitunos 7 10) == 111111

head (multiplosRepitunos 7 (10^10)) == 111111111111

head (multiplosRepitunos 7 (10^20)) == 111111111111111111111111

head (multiplosRepitunos 19 (10^10)) == 111111111111111111

Comprobar con QuickCheck que para todo primo p mayor que 5 y todo número entero positivo n, existe un mútiplo repituno de p mayor que n.

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck

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

multiplosRepitunos :: Integer -> Integer -> [Integer]
multiplosRepitunos p n =
  [x | x <- dropWhile (<= n) repitunos
     , mod x p == 0]

-- repitunos es la lista de los números de la forma 111...1 (escrito sólo con
-- unos). Por ejemplo,
--    take 5 repitunos  ==  [1,11,111,1111,11111]
repitunos :: [Integer]
repitunos = 1 : [10*x+1 | x <- repitunos]

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

multiplosRepitunos2 :: Integer -> Integer -> [Integer]
multiplosRepitunos2 p n =
  [x | x <- dropWhile (<= n) repitunos2
     , mod x p == 0]

repitunos2 :: [Integer]
repitunos2 = [div (10^n-1) 9 | n <- [1..]]

-- Comprobación
-- ============

-- La propiedad es
prop_multiplosRepitunos :: Int -> Integer -> Property
prop_multiplosRepitunos k n =
  k > 2 && n > 0 ==>
  not (null (multiplosRepitunos (primes !! k) n))

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

import Data.Numbers.Primes

import Test.QuickCheck

-- 1ª solución

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

multiplosRepitunos :: Integer -> Integer -> [Integer]

multiplosRepitunos p n =

[x | x <- dropWhile (<= n) repitunos

, mod x p == 0]

-- repitunos es la lista de los números de la forma 111...1 (escrito sólo con

-- unos). Por ejemplo,

-- take 5 repitunos == [1,11,111,1111,11111]

repitunos :: [Integer]

repitunos = 1 : [10*x+1 | x <- repitunos]

-- 2ª solución

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

multiplosRepitunos2 :: Integer -> Integer -> [Integer]

multiplosRepitunos2 p n =

[x | x <- dropWhile (<= n) repitunos2

, mod x p == 0]

repitunos2 :: [Integer]

repitunos2 = [div (10^n-1) 9 | n <- [1..]]

-- Comprobación

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

-- La propiedad es

prop_multiplosRepitunos :: Int -> Integer -> Property

prop_multiplosRepitunos k n =

k > 2 && n > 0 ==>

not (null (multiplosRepitunos (primes !! k) n))

-- La comprobación es

-- λ> quickCheck prop_multiplosRepitunos

-- +++ OK, passed 100 tests.

Conjetura de Goldbach

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

Una forma de la conjetura de Golbach afirma que todo entero mayor que 1 se puede escribir como la suma de uno, dos o tres números primos.

Si se define el índice de Goldbach de n > 1 como la mínima cantidad de primos necesarios para que su suma sea n, entonces la conjetura de Goldbach afirma que todos los índices de Goldbach de los enteros mayores que 1 son menores que 4.

Definir las siguientes funciones

   indiceGoldbach  :: Int -> Int
   graficaGoldbach :: Int -> IO ()

1 2	indiceGoldbach :: Int -> Int graficaGoldbach :: Int -> IO ()

tales que

(indiceGoldbach n) es el índice de Goldbach de n. Por ejemplo,

     indiceGoldbach 2                        ==  1
     indiceGoldbach 4                        ==  2
     indiceGoldbach 27                       ==  3
     sum (map indiceGoldbach [2..5000])      ==  10619
     maximum (map indiceGoldbach [2..5000])  ==  3

indiceGoldbach 2 == 1

indiceGoldbach 4 == 2

indiceGoldbach 27 == 3

sum (map indiceGoldbach [2..5000]) == 10619

maximum (map indiceGoldbach [2..5000]) == 3

(graficaGoldbach n) dibuja la gráfica de los índices de Goldbach de los números entre 2 y n. Por ejemplo, (graficaGoldbach 150) dibuja

Comprobar con QuickCheck la conjetura de Goldbach anterior.

Soluciones

import Data.Array
import Data.Numbers.Primes
import Graphics.Gnuplot.Simple
import Test.QuickCheck


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

indiceGoldbach :: Int -> Int
indiceGoldbach n =
  minimum (map length (particiones n))

particiones :: Int -> [[Int]]
particiones n = v ! n where
  v = array (0,n) [(i,f i) | i <- [0..n]]
    where f 0 = [[]]
          f m = [x:y | x <- xs, 
                       y <- v ! (m-x), 
                       [x] >= take 1 y]
            where xs = reverse (takeWhile (<= m) primes)

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

indiceGoldbach2 :: Int -> Int
indiceGoldbach2 x =
  head [n | n <- [1..], esSumaDe x n]

-- (esSumaDe x n) se verifica si x se puede escribir como la suma de n
-- primos. Por ejemplo,
--    esSumaDe 2  1  ==  True
--    esSumaDe 4  1  ==  False
--    esSumaDe 4  2  ==  True
--    esSumaDe 27 2  ==  False
--    esSumaDe 27 3  ==  True
esSumaDe :: Int -> Int -> Bool
esSumaDe x 1 = isPrime x
esSumaDe x n = or [esSumaDe (x-p) (n-1) | p <- takeWhile (<= x) primes]

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

indiceGoldbach3 :: Int -> Int
indiceGoldbach3 x =
  head [n | n <- [1..], esSumaDe3 x n]

esSumaDe3 :: Int -> Int -> Bool
esSumaDe3 x n = a ! (x,n) where
  a = array ((2,1),(x,9)) [((i,j),f i j) | i <- [2..x], j <- [1..9]]
  f i 1 = isPrime i
  f i j = or [a!(i-k,j-1) | k <- takeWhile (<= i) primes]

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

indiceGoldbach4 :: Int -> Int
indiceGoldbach4 n = v ! n where
  v = array (2,n) [(i,f i) | i <- [2..n]]
  f i | isPrime i = 1
      | otherwise = 1 + minimum [v!(i-p) | p <- takeWhile (< (i-1)) primes]

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

--    λ> sum (map indiceGoldbach [2..80])
--    142
--    (2.66 secs, 1,194,330,496 bytes)
--    λ> sum (map indiceGoldbach2 [2..80])
--    142
--    (0.01 secs, 1,689,944 bytes)
--    λ> sum (map indiceGoldbach3 [2..80])
--    142
--    (0.03 secs, 27,319,296 bytes)
--    λ> sum (map indiceGoldbach4 [2..80])
--    142
--    (0.03 secs, 47,823,656 bytes)
--    
--    λ> sum (map indiceGoldbach2 [2..1000])
--    2030
--    (0.10 secs, 200,140,264 bytes)
--    λ> sum (map indiceGoldbach3 [2..1000])
--    2030
--    (3.10 secs, 4,687,467,664 bytes)

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

graficaGoldbach :: Int -> IO ()
graficaGoldbach n =
  plotList [ Key Nothing
           , XRange (2,fromIntegral n)
           , PNG ("Conjetura_de_Goldbach_" ++ show n ++ ".png")
           ]
           [indiceGoldbach2 k | k <- [2..n]]

-- Comprobación de la conjetura de Goldbach
-- ========================================

-- La propiedad es
prop_Goldbach :: Int -> Property
prop_Goldbach x =
  x >= 2 ==> indiceGoldbach2 x < 4

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

100

101

102

103

104

105

106

107

import Data.Array

import Data.Numbers.Primes

import Graphics.Gnuplot.Simple

import Test.QuickCheck

-- 1ª definición

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

indiceGoldbach :: Int -> Int

indiceGoldbach n =

minimum (map length (particiones n))

particiones :: Int -> [[Int]]

particiones n = v ! n where

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

where f 0 = [[]]

f m = [x:y | x <- xs,

y <- v ! (m-x),

[x] >= take 1 y]

where xs = reverse (takeWhile (<= m) primes)

-- 2ª definición

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

indiceGoldbach2 :: Int -> Int

indiceGoldbach2 x =

head [n | n <- [1..], esSumaDe x n]

-- (esSumaDe x n) se verifica si x se puede escribir como la suma de n

-- primos. Por ejemplo,

-- esSumaDe 2 1 == True

-- esSumaDe 4 1 == False

-- esSumaDe 4 2 == True

-- esSumaDe 27 2 == False

-- esSumaDe 27 3 == True

esSumaDe :: Int -> Int -> Bool

esSumaDe x 1 = isPrime x

esSumaDe x n = or [esSumaDe (x-p) (n-1) | p <- takeWhile (<= x) primes]

-- 3ª definición

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

indiceGoldbach3 :: Int -> Int

indiceGoldbach3 x =

head [n | n <- [1..], esSumaDe3 x n]

esSumaDe3 :: Int -> Int -> Bool

esSumaDe3 x n = a ! (x,n) where

a = array ((2,1),(x,9)) [((i,j),f i j) | i <- [2..x], j <- [1..9]]

f i 1 = isPrime i

f i j = or [a!(i-k,j-1) | k <- takeWhile (<= i) primes]

-- 4ª definición

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

indiceGoldbach4 :: Int -> Int

indiceGoldbach4 n = v ! n where

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

f i | isPrime i = 1

| otherwise = 1 + minimum [v!(i-p) | p <- takeWhile (< (i-1)) primes]

-- Comparación de eficiencia

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

-- λ> sum (map indiceGoldbach [2..80])

-- 142

-- (2.66 secs, 1,194,330,496 bytes)

-- λ> sum (map indiceGoldbach2 [2..80])

-- 142

-- (0.01 secs, 1,689,944 bytes)

-- λ> sum (map indiceGoldbach3 [2..80])

-- 142

-- (0.03 secs, 27,319,296 bytes)

-- λ> sum (map indiceGoldbach4 [2..80])

-- 142

-- (0.03 secs, 47,823,656 bytes)

-- λ> sum (map indiceGoldbach2 [2..1000])

-- 2030

-- (0.10 secs, 200,140,264 bytes)

-- λ> sum (map indiceGoldbach3 [2..1000])

-- 2030

-- (3.10 secs, 4,687,467,664 bytes)

-- Gráfica

-- =======

graficaGoldbach :: Int -> IO ()

graficaGoldbach n =

plotList [ Key Nothing

, XRange (2,fromIntegral n)

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

]

[indiceGoldbach2 k | k <- [2..n]]

-- Comprobación de la conjetura de Goldbach

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

-- La propiedad es

prop_Goldbach :: Int -> Property

prop_Goldbach x =

x >= 2 ==> indiceGoldbach2 x < 4

-- La comprobación es

-- λ> quickCheck prop_Goldbach

-- +++ OK, passed 100 tests.

La conjetura de Levy

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

Hyman Levy observó que

    7 = 3 + 2 x 2
    9 = 3 + 2 x 3 =  5 + 2 x 2
   11 = 5 + 2 x 3 =  7 + 2 x 2
   13 = 3 + 2 x 5 =  7 + 2 x 3
   15 = 3 + 2 x 5 = 11 + 2 x 2
   17 = 3 + 2 x 7 =  7 + 2 x 5 = 11 + 2 x 3 = 13 + 2 x 2
   19 = 5 + 2 x 7 = 13 + 2 x 3

7 = 3 + 2 x 2

9 = 3 + 2 x 3 = 5 + 2 x 2

11 = 5 + 2 x 3 = 7 + 2 x 2

13 = 3 + 2 x 5 = 7 + 2 x 3

15 = 3 + 2 x 5 = 11 + 2 x 2

17 = 3 + 2 x 7 = 7 + 2 x 5 = 11 + 2 x 3 = 13 + 2 x 2

19 = 5 + 2 x 7 = 13 + 2 x 3

y conjeturó que todos los número impares mayores o iguales que 7 se pueden escribir como la suma de un primo y el doble de un primo. El objetivo de los siguientes ejercicios es comprobar la conjetura de Levy.

Definir las siguientes funciones

   descomposicionesLevy :: Integer -> [(Integer,Integer)]
   graficaLevy          :: Integer -> IO ()

1 2	descomposicionesLevy :: Integer -> [(Integer,Integer)] graficaLevy :: Integer -> IO ()

tales que

(descomposicionesLevy x) es la lista de pares de primos (p,q) tales que x = p + 2q. Por ejemplo,

     descomposicionesLevy  7  ==  [(3,2)]
     descomposicionesLevy  9  ==  [(3,3),(5,2)]
     descomposicionesLevy 17  ==  [(3,7),(7,5),(11,3),(13,2)]

descomposicionesLevy 7 == [(3,2)]

descomposicionesLevy 9 == [(3,3),(5,2)]

descomposicionesLevy 17 == [(3,7),(7,5),(11,3),(13,2)]

(graficaLevy n) dibuja los puntos (x,y) tales que x pertenece a [7,9..7+2x(n-1)] e y es el número de descomposiciones de Levy de x. Por ejemplo, (graficaLevy 200) dibuja

Comprobar con QuickCheck la conjetura de Levy.

Soluciones

[schedule on=’2018-03-19′ at=»06:00″]

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

descomposicionesLevy :: Integer -> [(Integer,Integer)]
descomposicionesLevy x =
  [(p,q) | p <- takeWhile (< x) (tail primes)
         , let q = (x - p) `div` 2
         , isPrime q]

-- graficaLevy 300
graficaLevy :: Integer -> IO ()
graficaLevy n =
  plotList [ Key Nothing
           , XRange (7,fromIntegral (7+2*(n-1)))
           , PNG ("La_conjetura_de_Levy-" ++ show n ++ ".png")
           ]
           [(x, length (descomposicionesLevy x)) | x <- [7,9..7+2*(n-1)]] 

-- La propiedad es
prop_Levy :: Integer -> Bool
prop_Levy x =
  not (null (descomposicionesLevy (7 + 2 * abs x)))

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

import Data.Numbers.Primes

import Test.QuickCheck

import Graphics.Gnuplot.Simple

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

descomposicionesLevy x =

[(p,q) | p <- takeWhile (< x) (tail primes)

, let q = (x - p) `div` 2

, isPrime q]

-- graficaLevy 300

graficaLevy :: Integer -> IO ()

graficaLevy n =

plotList [ Key Nothing

, XRange (7,fromIntegral (7+2*(n-1)))

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

]

[(x, length (descomposicionesLevy x)) | x <- [7,9..7+2*(n-1)]]

-- La propiedad es

prop_Levy :: Integer -> Bool

prop_Levy x =

not (null (descomposicionesLevy (7 + 2 * abs x)))

-- La comprobación es

-- λ> quickCheck prop_Levy

-- +++ OK, passed 100 tests.

Cruce de listas

PorJosé A. Alonso 5-marzo-201812-marzo-2018

Definir la función

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

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

tal que (cruce xs ys) es la lista de las listas obtenidas uniendo las listas de xs sin un elemento con las de ys sin un elemento. Por ejemplo,

   ghci> cruce [1,5,3] [2,4]
   [[5,3,4],[5,3,2],[1,3,4],[1,3,2],[1,5,4],[1,5,2]]
   ghci> cruce [1,5,3] [2,4,6]
   [[5,3,4,6],[5,3,2,6],[5,3,2,4],[1,3,4,6],[1,3,2,6],
    [1,3,2,4],[1,5,4,6],[1,5,2,6],[1,5,2,4]]

ghci> cruce [1,5,3] [2,4]

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

ghci> cruce [1,5,3] [2,4,6]

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

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

Comprobar con QuickCheck que el número de elementos de (cruce xs ys) es el producto de los números de elementos de xs y de ys.

Soluciones

import Data.List (delete)
import Test.QuickCheck

cruce :: Eq a => [a] -> [a] -> [[a]]
cruce xs ys = [(delete x xs) ++ (delete y ys) | x <- xs, y <- ys]

-- La propiedad es
prop_cruce :: Eq a => [a] -> [a] -> Bool
prop_cruce xs ys =
  length (cruce xs ys) == length xs * length ys

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

import Data.List (delete)

import Test.QuickCheck

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

cruce xs ys = [(delete x xs) ++ (delete y ys) | x <- xs, y <- ys]

-- La propiedad es

prop_cruce :: Eq a => [a] -> [a] -> Bool

prop_cruce xs ys =

length (cruce xs ys) == length xs * length ys

-- La comprobación es

-- ghci> quickCheck prop_cruce

-- +++ OK, passed 100 tests.

Números que no son cuadrados

PorJosé A. Alonso 15-febrero-201822-febrero-2018

Definir las funciones

   noCuadrados :: [Integer]
   graficaNoCuadrados :: Integer -> IO ()

1 2	noCuadrados :: [Integer] graficaNoCuadrados :: Integer -> IO ()

tales que

noCuadrados es la lista de los números naturales que no son cuadrados. Por ejemplo,

     λ> take 25 noCuadrados
     [2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27,28,29,30]

1 2	λ> take 25 noCuadrados [2,3,5,6,7,8,10,11,12,13,14,15,17,18,19,20,21,22,23,24,26,27,28,29,30]

(graficaNoCuadrados n) dibuja las diferencias entre los n primeros elementos de noCuadrados y sus posiciones. Por ejemplo, (graficaNoCuadrados 300) dibuja

(graficaNoCuadrados 3000) dibuja

(graficaNoCuadrados 30000) dibuja

Comprobar con QuickCheck que el término de noCuadrados en la posición n-1 es (n + floor(1/2 + sqrt(n))).

Soluciones

import Data.List (genericIndex)
import Graphics.Gnuplot.Simple
import Test.QuickCheck

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

noCuadrados :: [Integer]
noCuadrados = aux [0..] cuadrados
  where aux xs (y:ys) = as ++ aux bs ys
          where (as,_:bs) = span (<y) xs

cuadrados :: [Integer]
cuadrados = [x^2 | x <- [0..]]

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

noCuadrados2 :: [Integer]
noCuadrados2 = aux 2 [1..]
  where aux n (_:xs) = ys ++ aux (n+2) zs
          where (ys,zs) = splitAt n xs

-- Definición de graficaNoCuadrados
-- ================================

graficaNoCuadrados :: Integer -> IO ()
graficaNoCuadrados n =
  plotList [ Key Nothing
           , PNG ("Numeros_que_no_son_cuadrados_" ++ show n ++ ".png")
           ]
           (zipWith (-) noCuadrados [0..n-1])

-- La propiedad es
prop_noCuadrados :: Positive Integer -> Bool
prop_noCuadrados (Positive n) =
  noCuadrados `genericIndex` (n-1) ==
  n + floor (1/2 + sqrt (fromIntegral n))

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

import Data.List (genericIndex)

import Graphics.Gnuplot.Simple

import Test.QuickCheck

-- 1ª definición

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

noCuadrados :: [Integer]

noCuadrados = aux [0..] cuadrados

where aux xs (y:ys) = as ++ aux bs ys

where (as,_:bs) = span (<y) xs

cuadrados :: [Integer]

cuadrados = [x^2 | x <- [0..]]

-- 2ª definición

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

noCuadrados2 :: [Integer]

noCuadrados2 = aux 2 [1..]

where aux n (_:xs) = ys ++ aux (n+2) zs

where (ys,zs) = splitAt n xs

-- Definición de graficaNoCuadrados

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

graficaNoCuadrados :: Integer -> IO ()

graficaNoCuadrados n =

plotList [ Key Nothing

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

]

(zipWith (-) noCuadrados [0..n-1])

-- La propiedad es

prop_noCuadrados :: Positive Integer -> Bool

prop_noCuadrados (Positive n) =

noCuadrados `genericIndex` (n-1) ==

n + floor (1/2 + sqrt (fromIntegral n))

-- La comprobación es

-- λ> quickCheck prop_noCuadrados

-- +++ OK, passed 100 tests.

Celdas interiores de una retícula

PorJosé A. Alonso 5-febrero-201812-febrero-2018

Las celdas de una retícula cuadrada se numeran consecutivamente. Por ejemplo, la numeración de la retícula cuadrada de lado 4 es

   1, 2, 3, 4
   5, 6, 7, 8
   9,10,11,12
  13,14,15,16

1, 2, 3, 4

5, 6, 7, 8

9,10,11,12

13,14,15,16

Los números de sus celdas interiores son 6,7,10,11.

Definir la función

   interiores :: Int -> [Int]

1	interiores :: Int -> [Int]

tal que (interiores n) es la lista de los números de las celdas interiores de la retícula cuadrada de lado n. Por ejemplo,

   interiores 4  == [6,7,10,11]
   interiores 5  == [7,8,9,12,13,14,17,18,19]
   interiores 6  == [8,9,10,11,14,15,16,17,20,21,22,23,26,27,28,29]
   interiores 2  == []
   length (interiores 2018)  == 4064256

interiores 4 == [6,7,10,11]

interiores 5 == [7,8,9,12,13,14,17,18,19]

interiores 6 == [8,9,10,11,14,15,16,17,20,21,22,23,26,27,28,29]

interiores 2 == []

length (interiores 2018) == 4064256

Comprobar con QuickCheck que el número de celdas interiores de la retícula cuadrada de lado n, con n > 1, es (n-2)^2.

Soluciones

import Test.QuickCheck
import Data.List.Split (divvy)

-- 1ª solución
interiores :: Int -> [Int]
interiores n = [i | i <- [n..n*n-n], i `mod` n > 1]

-- 2ª solución
interiores2 :: Int -> [Int]
interiores2 n = aux [n+1..n^2-n]
  where aux xss@(x:xs) = take (n-2) xs ++ aux (drop n xss)
        aux []         = []

-- 3ª solución 
interiores3 :: Int -> [Int]
interiores3 n = concat (divvy (n-2) n [n+2..n*(n-1)-1])

-- 4ª solución
interiores4 :: Int -> [Int]
interiores4 n = concat [map (+(n*k)) [2..n-1] | k <- [1..n-2]]

-- 5ª solución
interiores5 :: Int -> [Int]
interiores5 n = concat (take (n-2) (iterate (map (+n)) [n+2..2*n-1]))

-- La propiedad es
prop_interiores :: Int -> Property
prop_interiores n =
  n > 1 ==> length (interiores n) == (n-2)^2

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

import Test.QuickCheck

import Data.List.Split (divvy)

-- 1ª solución

interiores :: Int -> [Int]

interiores n = [i | i <- [n..n*n-n], i `mod` n > 1]

-- 2ª solución

interiores2 :: Int -> [Int]

interiores2 n = aux [n+1..n^2-n]

where aux xss@(x:xs) = take (n-2) xs ++ aux (drop n xss)

aux [] = []

-- 3ª solución

interiores3 :: Int -> [Int]

interiores3 n = concat (divvy (n-2) n [n+2..n*(n-1)-1])

-- 4ª solución

interiores4 :: Int -> [Int]

interiores4 n = concat [map (+(n*k)) [2..n-1] | k <- [1..n-2]]

-- 5ª solución

interiores5 :: Int -> [Int]

interiores5 n = concat (take (n-2) (iterate (map (+n)) [n+2..2*n-1]))

-- La propiedad es

prop_interiores :: Int -> Property

prop_interiores n =

n > 1 ==> length (interiores n) == (n-2)^2

-- La comprobación es

-- λ> quickCheck prop_interiores

-- +++ OK, passed 100 tests.

Sucesión de Lichtenberg

PorJosé A. Alonso 25-enero-20181-febrero-2018

La sucesión de Lichtenberg esta formada por la representación decimal de los números binarios de la sucesión de dígitos 0 y 1 alternados Los primeros términos de ambas sucesiones son

   Alternada ..... Lichtenberg
   0 ....................... 0
   1 ....................... 1
   10 ...................... 2
   101 ..................... 5
   1010 ................... 10
   10101 .................. 21
   101010 ................. 42
   1010101 ................ 85
   10101010 .............. 170
   101010101 ............. 341
   1010101010 ............ 682
   10101010101 .......... 1365
   101010101010 ......... 2730

Alternada ..... Lichtenberg

0 ....................... 0

1 ....................... 1

10 ...................... 2

101 ..................... 5

1010 ................... 10

10101 .................. 21

101010 ................. 42

1010101 ................ 85

10101010 .............. 170

101010101 ............. 341

1010101010 ............ 682

10101010101 .......... 1365

101010101010 ......... 2730

Definir las funciones

   lichtenberg        :: [Integer]
   graficaLichtenberg :: Int -> IO ()

1 2	lichtenberg :: [Integer] graficaLichtenberg :: Int -> IO ()

tales que

lichtenberg es la lista cuyos elementos son los términos de la sucesión de Lichtenberg. Por ejemplo,

     λ> take 17 lichtenberg
     [0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690]

1 2	λ> take 17 lichtenberg [0,1,2,5,10,21,42,85,170,341,682,1365,2730,5461,10922,21845,43690]

(graficaLichtenberg n) dibuja la gráfica del número de dígitos de los n primeros términos de la sucesión de Lichtenberg. Por ejemlo, (graficaLichtenberg 100) dibuja

Comprobar con QuickCheck que todos los términos de la sucesión de Lichtenberg, a partir del 4º, son números compuestos.

Soluciones

import Data.Char (digitToInt)
import Graphics.Gnuplot.Simple
import Test.QuickCheck
import Data.Numbers.Primes (isPrime)

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

lichtenberg1 :: [Integer]
lichtenberg1 = map binarioAdecimal sucAlternada

-- sucAlternada es la lista cuyos elementos son los términos de la
-- sucesión de los dígitos 0 y 1 alternados. Por ejemplo,
--    λ> take 7 sucAlternada
--    ["0","1","10","101","1010","10101","101010"]
sucAlternada :: [String]
sucAlternada =
  ['0'] : [take n cadenaAlternada | n <- [1..]]

-- cadenaAltenada es la cadena formada alternando los caracteres 1 y
-- 0. Por ejemplo,
--    take 20 cadenaAlternada  ==  "10101010101010101010"
cadenaAlternada :: String
cadenaAlternada = cycle ['1','0']

-- (binarioAdecimal cs) es el número decimal correspondiente al número
-- binario cuya cadena de dígitos es cs. Por ejemplo,
--    binarioAdecimal "11101"  ==  29
binarioAdecimal :: String -> Integer
binarioAdecimal =
  foldl (\acc x -> acc * 2 + (toInteger . digitToInt) x) 0
  
-- 2ª solución
lichtenberg2 :: [Integer]
lichtenberg2 = map a [0..]
  where a 0 = 0
        a 1 = 1
        a n = a (n-1) + 2 * a (n-2) + 1

-- 3ª solución
lichtenberg3 :: [Integer]
lichtenberg3 =
  0 : 1 : map (+1) (zipWith (+) (tail lichtenberg3) (map (*2) lichtenberg3)) 

-- Comprobación de eficiencia
--    λ> length (show (lichtenberg1 !! 27))
--    8
--    (0.02 secs, 155,384 bytes)
--    λ> length (show (lichtenberg2 !! 27))
--    8
--    (2.22 secs, 311,157,760 bytes)
--    
--    λ> length (show (lichtenberg1 !! (8*10^4)))
--    24083
--    (1.28 secs, 664,207,040 bytes)
--    λ> length (show (lichtenberg3 !! (8*10^4)))
--    24083
--    (2.59 secs, 1,253,328,200 bytes)

-- La propiedad es
propLichtenberg :: Int -> Property
propLichtenberg n =
  n > 4 ==> not (isPrime (lichtenberg1 !! n))

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

graficaLichtenberg :: Int -> IO ()
graficaLichtenberg n =
  plotList [ Key Nothing
           , Title "Numero de digitos de la sucesion de Lichtenberg"
           , PNG "Sucesion_de_Lichtenberg.png"
           ]
           (take n (map (length . show) lichtenberg1))

import Data.Char (digitToInt)

import Graphics.Gnuplot.Simple

import Test.QuickCheck

import Data.Numbers.Primes (isPrime)

-- 1ª solución

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

lichtenberg1 :: [Integer]

lichtenberg1 = map binarioAdecimal sucAlternada

-- sucAlternada es la lista cuyos elementos son los términos de la

-- sucesión de los dígitos 0 y 1 alternados. Por ejemplo,

-- λ> take 7 sucAlternada

-- ["0","1","10","101","1010","10101","101010"]

sucAlternada :: [String]

sucAlternada =

['0'] : [take n cadenaAlternada | n <- [1..]]

-- cadenaAltenada es la cadena formada alternando los caracteres 1 y

-- 0. Por ejemplo,

-- take 20 cadenaAlternada == "10101010101010101010"

cadenaAlternada :: String

cadenaAlternada = cycle ['1','0']

-- (binarioAdecimal cs) es el número decimal correspondiente al número

-- binario cuya cadena de dígitos es cs. Por ejemplo,

-- binarioAdecimal "11101" == 29

binarioAdecimal :: String -> Integer

binarioAdecimal =

foldl (\acc x -> acc * 2 + (toInteger . digitToInt) x) 0

-- 2ª solución

lichtenberg2 :: [Integer]

lichtenberg2 = map a [0..]

where a 0 = 0

a 1 = 1

a n = a (n-1) + 2 * a (n-2) + 1

-- 3ª solución

lichtenberg3 :: [Integer]

lichtenberg3 =

0 : 1 : map (+1) (zipWith (+) (tail lichtenberg3) (map (*2) lichtenberg3))

-- Comprobación de eficiencia

-- λ> length (show (lichtenberg1 !! 27))

-- 8

-- (0.02 secs, 155,384 bytes)

-- λ> length (show (lichtenberg2 !! 27))

-- 8

-- (2.22 secs, 311,157,760 bytes)

-- λ> length (show (lichtenberg1 !! (8*10^4)))

-- 24083

-- (1.28 secs, 664,207,040 bytes)

-- λ> length (show (lichtenberg3 !! (8*10^4)))

-- 24083

-- (2.59 secs, 1,253,328,200 bytes)

-- La propiedad es

propLichtenberg :: Int -> Property

propLichtenberg n =

n > 4 ==> not (isPrime (lichtenberg1 !! n))

-- La comprobación es

-- λ> quickCheck propLichtenberg

-- +++ OK, passed 100 tests.

graficaLichtenberg :: Int -> IO ()

graficaLichtenberg n =

plotList [ Key Nothing

, Title "Numero de digitos de la sucesion de Lichtenberg"

, PNG "Sucesion_de_Lichtenberg.png"

]

(take n (map (length . show) lichtenberg1))

Sumas parciales de Juzuk

PorJosé A. Alonso 23-enero-201830-enero-2018

En 1939 Dov Juzuk extendió el método de Nicómaco del cálculo de los cubos. La extensión se basaba en los siguientes pasos:

se comienza con la lista de todos los enteros positivos

     [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

1	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, ...

se agrupan tomando el primer elemento, los dos siguientes, los tres
siguientes, etc.

     [[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15], ...

1	[[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15], ...

se seleccionan los elementos en posiciones pares

     [[1],         [4, 5, 6],                [11, 12, 13, 14, 15], ...

1	[[1], [4, 5, 6], [11, 12, 13, 14, 15], ...

se suman los elementos de cada grupo

     [1,           15,                       65,                   ...

1	[1, 15, 65, ...

se calculan las sumas acumuladas

     [1,           16,                       81,                   ...

1	[1, 16, 81, ...

Las sumas obtenidas son las cuantas potencias de los números enteros positivos.

Definir las funciones

   listasParcialesJuzuk :: [a] -> [[a]]
   sumasParcialesJuzuk  :: [Integer] -> [Integer]

1 2	listasParcialesJuzuk :: [a] -> [[a]] sumasParcialesJuzuk :: [Integer] -> [Integer]

tal que

(listasParcialesJuzuk xs) es lalista de ls listas parciales de Juzuk; es decir, la selección de los elementos en posiciones pares de la agrupación de los elementos de xs tomando el primer elemento, los dos siguientes, los tres siguientes, etc. Por ejemplo,

     λ> take 4 (listasParcialesJuzuk [1..])
     [[1],[4,5,6],[11,12,13,14,15],[22,23,24,25,26,27,28]]
     λ> take 4 (listasParcialesJuzuk [1,3..])
     [[1],[7,9,11],[21,23,25,27,29],[43,45,47,49,51,53,55]]

λ> take 4 (listasParcialesJuzuk [1..])

[[1],[4,5,6],[11,12,13,14,15],[22,23,24,25,26,27,28]]

λ> take 4 (listasParcialesJuzuk [1,3..])

[[1],[7,9,11],[21,23,25,27,29],[43,45,47,49,51,53,55]]

(sumasParcialesJuzuk xs) es la lista de las sumas acumuladas de los elementos de las listas de Juzuk generadas por xs. Por ejemplo,

     take 4 (sumasParcialesJuzuk [1..])  ==  [1,16,81,256]
     take 4 (sumasParcialesJuzuk [1,3..])  ==  [1,28,153,496]

1 2	take 4 (sumasParcialesJuzuk [1..]) == [1,16,81,256] take 4 (sumasParcialesJuzuk [1,3..]) == [1,28,153,496]

Comprobar con QuickChek que, para todo entero positivo n,

el elemento de (sumasParcialesJuzuk [1..]) en la posición (n-1) es n^4.
el elemento de (sumasParcialesJuzuk [1,3..]) en la posición (n-1) es n^2*(2*n^2 - 1).
el elemento de (sumasParcialesJuzuk [1,5..]) en la posición (n-1) es 4*n^4-3*n^2.
el elemento de (sumasParcialesJuzuk [2,3..]) en la posición (n-1) es n^2*(n^2+1).

Soluciones

import Data.List (genericIndex)
import Test.QuickCheck

listasParcialesJuzuk :: [a] -> [[a]]
listasParcialesJuzuk = elementosEnPares . listasParciales

-- (listasParciales xs) es la agrupación de los elementos de xs obtenida
-- tomando el primer elemento, los dos siguientes, los tres siguientes,
-- etc. Por ejemplo, 
--    λ> take 5 (listasParciales [1..])
--    [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]
listasParciales :: [a] -> [[a]]
listasParciales = aux 1
  where aux n xs = ys : aux (n+1) zs  
          where (ys,zs) = splitAt n xs

-- (elementosEnPares xs) es la lista de los elementos de xs en
-- posiciones pares. Por ejemplo,
--    λ> elementosEnPares [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]
--    [[1],[4,5,6],[11,12,13,14,15]]
elementosEnPares :: [a] -> [a]
elementosEnPares []       = []
elementosEnPares [x]      = [x]
elementosEnPares (x:_:xs) = x : elementosEnPares xs

sumasParcialesJuzuk :: [Integer] -> [Integer]
sumasParcialesJuzuk xs =
  scanl1 (+) (map sum (listasParcialesJuzuk xs))

-- La primera propiedad es
prop_sumasParcialesJuzuk :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk (Positive n) =
  sumasParcialesJuzuk [1..] `genericIndex` (n-1) == n^4

-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk
--    +++ OK, passed 100 tests.

-- La segunda propiedad es
prop_sumasParcialesJuzuk2 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk2 (Positive n) =
  sumasParcialesJuzuk [1,3..] `genericIndex` (n-1) == n^2*(2*n^2 - 1)

-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk2
--    +++ OK, passed 100 tests.

-- La tercera propiedad es
prop_sumasParcialesJuzuk3 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk3 (Positive n) =
  sumasParcialesJuzuk [1,5..] `genericIndex` (n-1) == 4*n^4-3*n^2

-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk3
--    +++ OK, passed 100 tests.

-- La cuarta propiedad es
prop_sumasParcialesJuzuk4 :: (Positive Integer) -> Bool
prop_sumasParcialesJuzuk4 (Positive n) =
  sumasParcialesJuzuk [2,3..] `genericIndex` (n-1) == n^2*(n^2+1)
  
-- Su comprobación es
--    λ> quickCheck prop_sumasParcialesJuzuk4
--    +++ OK, passed 100 tests.

import Data.List (genericIndex)

import Test.QuickCheck

listasParcialesJuzuk :: [a] -> [[a]]

listasParcialesJuzuk = elementosEnPares . listasParciales

-- (listasParciales xs) es la agrupación de los elementos de xs obtenida

-- tomando el primer elemento, los dos siguientes, los tres siguientes,

-- etc. Por ejemplo,

-- λ> take 5 (listasParciales [1..])

-- [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]

listasParciales :: [a] -> [[a]]

listasParciales = aux 1

where aux n xs = ys : aux (n+1) zs

where (ys,zs) = splitAt n xs

-- (elementosEnPares xs) es la lista de los elementos de xs en

-- posiciones pares. Por ejemplo,

-- λ> elementosEnPares [[1],[2,3],[4,5,6],[7,8,9,10],[11,12,13,14,15]]

-- [[1],[4,5,6],[11,12,13,14,15]]

elementosEnPares :: [a] -> [a]

elementosEnPares [] = []

elementosEnPares [x] = [x]

elementosEnPares (x:_:xs) = x : elementosEnPares xs

sumasParcialesJuzuk :: [Integer] -> [Integer]

sumasParcialesJuzuk xs =

scanl1 (+) (map sum (listasParcialesJuzuk xs))

-- La primera propiedad es

prop_sumasParcialesJuzuk :: (Positive Integer) -> Bool

prop_sumasParcialesJuzuk (Positive n) =

sumasParcialesJuzuk [1..] `genericIndex` (n-1) == n^4

-- Su comprobación es

-- λ> quickCheck prop_sumasParcialesJuzuk

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_sumasParcialesJuzuk2 :: (Positive Integer) -> Bool

prop_sumasParcialesJuzuk2 (Positive n) =

sumasParcialesJuzuk [1,3..] `genericIndex` (n-1) == n^2*(2*n^2 - 1)

-- Su comprobación es

-- λ> quickCheck prop_sumasParcialesJuzuk2

-- +++ OK, passed 100 tests.

-- La tercera propiedad es

prop_sumasParcialesJuzuk3 :: (Positive Integer) -> Bool

prop_sumasParcialesJuzuk3 (Positive n) =

sumasParcialesJuzuk [1,5..] `genericIndex` (n-1) == 4*n^4-3*n^2

-- Su comprobación es

-- λ> quickCheck prop_sumasParcialesJuzuk3

-- +++ OK, passed 100 tests.

-- La cuarta propiedad es

prop_sumasParcialesJuzuk4 :: (Positive Integer) -> Bool

prop_sumasParcialesJuzuk4 (Positive n) =

sumasParcialesJuzuk [2,3..] `genericIndex` (n-1) == n^2*(n^2+1)

-- Su comprobación es

-- λ> quickCheck prop_sumasParcialesJuzuk4

-- +++ OK, passed 100 tests.

Complemento potencial

PorJosé A. Alonso 22-enero-201829-enero-2018

El complemento potencial de un número entero positivo x es el menor número y tal que el producto de x por y es un una potencia perfecta. Por ejemplo,

el complemento potencial de 12 es 3 ya que 12 y 24 no son potencias perfectas pero 36 sí lo es;
el complemento potencial de 54 es 4 ya que 54, 108 y 162 no son potencias perfectas pero 216 = 6^3 sí lo es.

Definir las funciones

   complemento                 :: Integer -> Integer
   graficaComplementoPotencial :: Integer -> IO ()

1 2	complemento :: Integer -> Integer graficaComplementoPotencial :: Integer -> IO ()

tales que

(complemento x) es el complemento potencial de x; por ejemplo,

     complemento 12     ==  3
     complemento 54     ==  4
     complemento 720    ==  5
     complemento 24000  ==  9
     complemento 2018   ==  2018

complemento 12 == 3

complemento 54 == 4

complemento 720 == 5

complemento 24000 == 9

complemento 2018 == 2018

(graficaComplementoPotencial n) dibuja la gráfica de los complementos potenciales de los n primeros números enteros positivos. Por ejemplo, (graficaComplementoPotencial 100) dibuja

y (graficaComplementoPotencial 500) dibuja

Comprobar con QuickCheck que (complemento x) es menor o igual que x.

Soluciones

import Data.Numbers.Primes     (primeFactors)
import Data.List               (genericLength, group)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, PNG, Title))
import Test.QuickCheck

complemento :: Integer -> Integer
complemento 1 = 1
complemento x =
  head [y | y <- [1..]
          , esPotenciaPerfecta (x*y)]
  
-- (esPotenciaPerfecta x) se verifica si x es una potencia perfecta. Por
-- ejemplo, 
--    esPotenciaPerfecta 36  ==  True
--    esPotenciaPerfecta 72  ==  False
esPotenciaPerfecta :: Integer -> Bool
esPotenciaPerfecta x = mcd (exponentes x) > 1

-- (exponentes x) es la lista de los exponentes de la factorización prima
-- de x. Por ejemplos,
--    exponentes 36  ==  [2,2]
--    exponentes 72  ==  [3,2]
exponentes :: Integer -> [Integer]
exponentes = map snd . factorizacion
  
-- (factorizacion n) es la factorizacion prima de n. Por ejemplo,
--    factorizacion 1400  ==  [(2,3),(5,2),(7,1)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  [(x,genericLength xs) | xs@(x:_) <- group (primeFactors n)]

-- (mcd xs) es el máximo común divisor de la lista xs. Por ejemplo,
--    mcd [4,6,10]  ==  2
--    mcd [4,5,10]  ==  1
mcd :: [Integer] -> Integer
mcd = foldl1 gcd

-- La propiedad es
prop_complemento :: (Positive Integer) -> Bool
prop_complemento (Positive x) =
  complemento x <= x

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

graficaComplementoPotencial :: Integer -> IO ()
graficaComplementoPotencial n =
  plotList [Key Nothing
           , PNG ("Complemento_potencial_"  ++ show n ++ ".png")
           , Title ("(graficaComplementoPotencial " ++ show n ++ ")") 
           ]
           (map complemento [1..n])

import Data.Numbers.Primes (primeFactors)

import Data.List (genericLength, group)

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

import Test.QuickCheck

complemento :: Integer -> Integer

complemento 1 = 1

complemento x =

head [y | y <- [1..]

, esPotenciaPerfecta (x*y)]

-- (esPotenciaPerfecta x) se verifica si x es una potencia perfecta. Por

-- ejemplo,

-- esPotenciaPerfecta 36 == True

-- esPotenciaPerfecta 72 == False

esPotenciaPerfecta :: Integer -> Bool

esPotenciaPerfecta x = mcd (exponentes x) > 1

-- (exponentes x) es la lista de los exponentes de la factorización prima

-- de x. Por ejemplos,

-- exponentes 36 == [2,2]

-- exponentes 72 == [3,2]

exponentes :: Integer -> [Integer]

exponentes = map snd . factorizacion

-- (factorizacion n) es la factorizacion prima de n. Por ejemplo,

-- factorizacion 1400 == [(2,3),(5,2),(7,1)]

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

factorizacion n =

[(x,genericLength xs) | xs@(x:_) <- group (primeFactors n)]

-- (mcd xs) es el máximo común divisor de la lista xs. Por ejemplo,

-- mcd [4,6,10] == 2

-- mcd [4,5,10] == 1

mcd :: [Integer] -> Integer

mcd = foldl1 gcd

-- La propiedad es

prop_complemento :: (Positive Integer) -> Bool

prop_complemento (Positive x) =

complemento x <= x

-- La comprobación es

-- λ> quickCheck prop_complemento

-- +++ OK, passed 100 tests.

graficaComplementoPotencial :: Integer -> IO ()

graficaComplementoPotencial n =

plotList [Key Nothing

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

, Title ("(graficaComplementoPotencial " ++ show n ++ ")")

]

(map complemento [1..n])

Enumeración de los números enteros

PorJosé A. Alonso 9-enero-201825-marzo-2022

Definir la sucesión

   enteros :: [Int]

1	enteros :: [Int]

tal que sus elementos son los números enteros comenzando en el 0 e intercalando los positivos y los negativos. Por ejemplo,

   ghci> take 23 enteros
   [0,1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10,11,-11]

1 2	ghci> take 23 enteros [0,1,-1,2,-2,3,-3,4,-4,5,-5,6,-6,7,-7,8,-8,9,-9,10,-10,11,-11]

Comprobar con QuickCheck que el n-ésimo término de la sucesión es
(1-(2*n+1)*(-1)^n)/4.

Nota. En la comprobación usar

   quickCheckWith (stdArgs {maxSize=7}) prop_enteros

1	quickCheckWith (stdArgs {maxSize=7}) prop_enteros

Soluciones

import Test.QuickCheck
import Control.Applicative ((<**>))

-- 1ª definición
enteros :: [Int]
enteros = 0 : concat [[n,-n] | n <- [1..]]

-- 2ª definición
enteros2 :: [Int]
enteros2 = 0 : [y | x <- [1..], y <- [x, -x]]

-- 3ª definición
enteros3 :: [Int]
enteros3 = iterate siguiente 0
  where siguiente i | i > 0     = -i
                    | otherwise = 1 - i

-- 4ª definición
enteros4 :: [Int]
enteros4 = iterate (\i -> if i > 0 then -i else 1-i) 0

-- 5ª definición
enteros5 :: [Int]
enteros5 = 0 : [f x | x <- [1..], f <- [id, negate]]

-- 6ª definición
enteros6 :: [Int]
enteros6 = 0 : ([1..] <**> [id, negate])

-- La propiedad es
prop_enteros :: Int -> Property
prop_enteros n = 
    n >= 0 ==> enteros !! n == (1-(2*n+1)*(-1)^n) `div` 4

-- La comprobación es
--    ghci> quickCheckWith (stdArgs {maxSize=7}) prop_enteros
--    +++ OK, passed 100 tests.

import Test.QuickCheck

import Control.Applicative ((<**>))

-- 1ª definición

enteros :: [Int]

enteros = 0 : concat [[n,-n] | n <- [1..]]

-- 2ª definición

enteros2 :: [Int]

enteros2 = 0 : [y | x <- [1..], y <- [x, -x]]

-- 3ª definición

enteros3 :: [Int]

enteros3 = iterate siguiente 0

where siguiente i | i > 0 = -i

| otherwise = 1 - i

-- 4ª definición

enteros4 :: [Int]

enteros4 = iterate (\i -> if i > 0 then -i else 1-i) 0

-- 5ª definición

enteros5 :: [Int]

enteros5 = 0 : [f x | x <- [1..], f <- [id, negate]]

-- 6ª definición

enteros6 :: [Int]

enteros6 = 0 : ([1..] <**> [id, negate])

-- La propiedad es

prop_enteros :: Int -> Property

prop_enteros n =

n >= 0 ==> enteros !! n == (1-(2*n+1)*(-1)^n) `div` 4

-- La comprobación es

-- ghci> quickCheckWith (stdArgs {maxSize=7}) prop_enteros

-- +++ OK, passed 100 tests.

Normalización de expresiones aritméticas

PorJosé A. Alonso 26-abril-201710-mayo-2017

El siguiente tipo de dato representa expresiones construidas con variables, sumas y productos

   data Expr = Var String
             | S Expr Expr
             | P Expr Expre
             deriving (Eq, Show)

data Expr = Var String

| S Expr Expr

| P Expr Expre

deriving (Eq, Show)

Por ejemplo, x*(y+z) se representa por (P (V "x") (S (V "y") (V "z")))

Una expresión es un término si es un producto de variables. Por ejemplo, x*(y*z) es un término pero x+(y*z) ni x*(y+z) lo son.

Una expresión está en forma normal si es una suma de términos. Por ejemplo, x*(y*z) y x+(y*z) están en forma normal; pero x*(y+z) y (x+y)*(x+z) no lo están.

Definir la función

   esTermino :: Expr -> Bool
   esTermino :: Expr -> Bool
   normal    :: Expr -> Expr

esTermino :: Expr -> Bool

normal :: Expr -> Expr

tales que

(esTermino a) se verifica si a es un término. Por ejemplo,

     esTermino (V "x")                         == True
     esTermino (P (V "x") (P (V "y") (V "z"))) == True
     esTermino (P (V "x") (S (V "y") (V "z"))) == False
     esTermino (S (V "x") (P (V "y") (V "z"))) == False

esTermino (V "x") == True

esTermino (P (V "x") (P (V "y") (V "z"))) == True

esTermino (P (V "x") (S (V "y") (V "z"))) == False

esTermino (S (V "x") (P (V "y") (V "z"))) == False

(esNormal a) se verifica si a está en forma normal. Por ejemplo,

     esNormal (V "x")                                     == True
     esNormal (P (V "x") (P (V "y") (V "z")))             == True
     esNormal (S (V "x") (P (V "y") (V "z")))             == True
     esNormal (P (V "x") (S (V "y") (V "z")))             == False
     esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False
     esNormal (S (P (V "x") (V "y")) (S (V "z") (V "x"))) == True

esNormal (V "x") == True

esNormal (P (V "x") (P (V "y") (V "z"))) == True

esNormal (S (V "x") (P (V "y") (V "z"))) == True

esNormal (P (V "x") (S (V "y") (V "z"))) == False

esNormal (P (S (V "x") (V "y")) (S (V "y") (V "z"))) == False

esNormal (S (P (V "x") (V "y")) (S (V "z") (V "x"))) == True

(normal e) es la forma normal de la expresión e obtenida aplicando, mientras que sea posible, las propiedades distributivas:

     (a+b)*c = a*c+b*c
     c*(a+b) = c*a+c*b

1 2	(a+b)c = ac+bc c(a+b) = ca+cb

Por ejemplo,

     λ> normal (P (S (V "x") (V "y")) (V "z"))
     S (P (V "x") (V "z")) (P (V "y") (V "z"))
     λ> normal (P (V "z") (S (V "x") (V "y")))
     S (P (V "z") (V "x")) (P (V "z") (V "y"))
     λ> normal (P (S (V "x") (V "y")) (S (V "u") (V "v")))
     S (S (P (V "x") (V "u")) (P (V "x") (V "v"))) 
       (S (P (V "y") (V "u")) (P (V "y") (V "v")))
     λ> normal (S (P (V "x") (V "y")) (V "z"))
     S (P (V "x") (V "y")) (V "z")
     λ> normal (V "x")
     V "x"

λ> normal (P (S (V "x") (V "y")) (V "z"))

S (P (V "x") (V "z")) (P (V "y") (V "z"))

λ> normal (P (V "z") (S (V "x") (V "y")))

S (P (V "z") (V "x")) (P (V "z") (V "y"))

λ> normal (P (S (V "x") (V "y")) (S (V "u") (V "v")))

S (S (P (V "x") (V "u")) (P (V "x") (V "v")))

(S (P (V "y") (V "u")) (P (V "y") (V "v")))

λ> normal (S (P (V "x") (V "y")) (V "z"))

S (P (V "x") (V "y")) (V "z")

λ> normal (V "x")

V "x"

Comprobar con QuickCheck que para cualquier expresión e, (normal e) está en forma normal y que (normal (normal e)) es igual a (normal e).

Nota. Para la comprobación se usará el siguiente generador de expresiones aritméticas

   import Test.QuickCheck
   import Control.Monad
   
   instance Arbitrary Expr where
     arbitrary = sized arb 
       where
         arb 0         = liftM V arbitrary
         arb n | n > 0 = oneof [liftM V arbitrary,
                                liftM2 S sub sub, 
                                liftM2 P sub sub] 
           where sub = arb (n `div` 2)

import Test.QuickCheck

import Control.Monad

instance Arbitrary Expr where

arbitrary = sized arb

where

arb 0 = liftM V arbitrary

arb n | n > 0 = oneof [liftM V arbitrary,

liftM2 S sub sub,

liftM2 P sub sub]

where sub = arb (n `div` 2)

Soluciones

import Test.QuickCheck
import Control.Monad

data Expr = V String
          | S Expr Expr
          | P Expr Expr
          deriving (Eq, Show)

esTermino :: Expr -> Bool
esTermino (V _)   = True
esTermino (S _ _) = False
esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool
esNormal (S a b) = esNormal a && esNormal b
esNormal a       = esTermino a

normal :: Expr -> Expr
normal (V v)   = V v
normal (S a b) = S (normal a) (normal b)
normal (P a b) = p (normal a) (normal b)
  where p (S a b) c = S (p a c) (p b c)
        p a (S b c) = S (p a b) (p a c)
        p a b       = P a b

prop_normal :: Expr -> Bool
prop_normal e = 
     esNormal (normal e)
  && normal (normal e) == normal e

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

instance Arbitrary Expr where
  arbitrary = sized arb 
    where
      arb 0         = liftM V arbitrary
      arb n | n > 0 = oneof [liftM V arbitrary,
                             liftM2 S sub sub, 
                             liftM2 P sub sub] 
        where sub = arb (n `div` 2)

import Test.QuickCheck

import Control.Monad

data Expr = V String

| S Expr Expr

| P Expr Expr

deriving (Eq, Show)

esTermino :: Expr -> Bool

esTermino (V _) = True

esTermino (S _ _) = False

esTermino (P a b) = esTermino a && esTermino b

esNormal :: Expr -> Bool

esNormal (S a b) = esNormal a && esNormal b

esNormal a = esTermino a

normal :: Expr -> Expr

normal (V v) = V v

normal (S a b) = S (normal a) (normal b)

normal (P a b) = p (normal a) (normal b)

where p (S a b) c = S (p a c) (p b c)

p a (S b c) = S (p a b) (p a c)

p a b = P a b

prop_normal :: Expr -> Bool

prop_normal e =

esNormal (normal e)

&& normal (normal e) == normal e

-- La comprobación es

-- λ> quickCheck prop_normal

-- +++ OK, passed 100 tests.

instance Arbitrary Expr where

arbitrary = sized arb

where

arb 0 = liftM V arbitrary

arb n | n > 0 = oneof [liftM V arbitrary,

liftM2 S sub sub,

liftM2 P sub sub]

where sub = arb (n `div` 2)

Distancias entre primos consecutivos

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

Los 15 primeros números primos son

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

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

Las distancias entre los elementos consecutivos son

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

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

La distribución de las distancias es

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

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

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

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

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

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

Definir las funciones

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

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

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

graficas :: [Int] -> IO ()

distanciasMasFrecuentes :: Int -> [Int]

tales que

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

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

λ> cuentaDistancias 15

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

λ> cuentaDistancias 100

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

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

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

λ> frecuenciasDistancias 15

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

λ> frecuenciasDistancias 30

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

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

(graficas [1000,2000,3000]) dibuja

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

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

distanciasMasFrecuentes 15 == [2]

distanciasMasFrecuentes 26 == [2,4]

distanciasMasFrecuentes 32 == [4]

distanciasMasFrecuentes 41 == [2,4,6]

distanciasMasFrecuentes 77 == [6]

distanciasMasFrecuentes 160 == [4,6]

distanciasMasFrecuentes (10^6) == [6]

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

Soluciones

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

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

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

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

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

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

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

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

import Data.Numbers.Primes

import qualified Data.Map as M

import Graphics.Gnuplot.Simple

import Test.QuickCheck

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

cuentaDistancias = M.toList . dicDistancias

dicDistancias :: Int -> M.Map Int Int

dicDistancias n =

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

distancias :: Int -> [Int]

distancias n =

zipWith (-) (tail xs) xs

where xs = take n primes

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

frecuenciasDistancias n =

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

where n1 = fromIntegral (n-1)

graficas :: [Int] -> IO ()

graficas ns =

plotLists [Key Nothing]

(map frecuenciasDistancias ns)

distanciasMasFrecuentes :: Int -> [Int]

distanciasMasFrecuentes n =

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

where d = dicDistancias n

m = maximum (M.elems d)

-- La propiedad es

prop_distanciasMasFrecuentes :: Int -> Bool

prop_distanciasMasFrecuentes n =

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

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.

Sumas de tres capicúas

PorJosé A. Alonso 12-enero-201719-enero-2017

Definir la función

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

1	sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]

tales que (sumas3Capicuas x) es la lista de las descomposiciones de x como suma de tres capicúas (con los sumandos no decrecientes). Por ejemplo,

   sumas3Capicuas 0  ==  [(0,0,0)]
   sumas3Capicuas 1  ==  [(0,0,1)]
   sumas3Capicuas 2  ==  [(0,0,2),(0,1,1)]
   sumas3Capicuas 3  ==  [(0,0,3),(0,1,2),(1,1,1)]
   sumas3Capicuas 4  ==  [(0,0,4),(0,1,3),(0,2,2),(1,1,2)]
   length (sumas3Capicuas 17)      ==  17
   length (sumas3Capicuas 2017)    ==  47
   length (sumas3Capicuas 999999)  ==  15266

sumas3Capicuas 0 == [(0,0,0)]

sumas3Capicuas 1 == [(0,0,1)]

sumas3Capicuas 2 == [(0,0,2),(0,1,1)]

sumas3Capicuas 3 == [(0,0,3),(0,1,2),(1,1,1)]

sumas3Capicuas 4 == [(0,0,4),(0,1,3),(0,2,2),(1,1,2)]

length (sumas3Capicuas 17) == 17

length (sumas3Capicuas 2017) == 47

length (sumas3Capicuas 999999) == 15266

Comprobar con QuickCheck que todo número natural se puede escribir como suma de tres capicúas.

Soluciones

import Test.QuickCheck

sumas3Capicuas :: Integer -> [(Integer, Integer, Integer)]
sumas3Capicuas x =
  [(a,b,c) | a <- as
           , b <- dropWhile (< a) as
           , let c = x - a - b
           , b <= c 
           , esCapicua c]
  where as = takeWhile (<= x) capicuas

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

-- La propiedad es
prop_sumas3Capicuas :: Integer -> Property
prop_sumas3Capicuas x =
  x >= 0 ==> not (null (sumas3Capicuas x))

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

import Test.QuickCheck

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

sumas3Capicuas x =

[(a,b,c) | a <- as

, b <- dropWhile (< a) as

, let c = x - a - b

, b <= c

, esCapicua c]

where as = takeWhile (<= x) capicuas

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

-- La propiedad es

prop_sumas3Capicuas :: Integer -> Property

prop_sumas3Capicuas x =

x >= 0 ==> not (null (sumas3Capicuas x))

-- La comprobación es

-- λ> quickCheck prop_sumas3Capicuas

-- +++ OK, passed 100 tests.

Números de Perrin

PorJosé A. Alonso 29-diciembre-201625-abril-2021

Los números de Perrin se definen por la relación de recurrencia

   P(n) = P(n - 2) + P(n - 3) si n > 2,

1	P(n) = P(n - 2) + P(n - 3) si n > 2,

con los valores iniciales

   P(0) = 3, P(1) = 0 y P(2) = 2.

1	P(0) = 3, P(1) = 0 y P(2) = 2.

Definir la sucesión

   sucPerrin :: [Integer]

1	sucPerrin :: [Integer]

cuyos elementos son los números de Perrin. Por ejemplo,

   λ> take 15 sucPerrin
   [3,0,2,3,2,5,5,7,10,12,17,22,29,39,51]
   λ> length (show (sucPerrin !! (2*10^5)))
   24425

λ> take 15 sucPerrin

[3,0,2,3,2,5,5,7,10,12,17,22,29,39,51]

λ> length (show (sucPerrin !! (2*10^5)))

24425

Comprobar con QuickCheck si se verifica la siguiente propiedad: para todo entero n > 1, el n-ésimo término de la sucesión de Perrin es divisible por n si y sólo si n es primo.

Soluciones

import Data.List (genericIndex, unfoldr)
import Data.Numbers.Primes (isPrime)
import Test.QuickCheck

-- 1ª definición
sucPerrin1 :: [Integer]
sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1)

-- 2ª definición
sucPerrin2 :: [Integer]
sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)]
  where op (a,b,c) = (b,c,a+b)
 
-- 3ª definición
sucPerrin3 :: [Integer]
sucPerrin3 =
  unfoldr (\(a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2))

-- Comparación de eficiencia
--    λ> length (show (sucPerrin1 !! (10^5)))
--    12213
--    (1.44 secs, 295,373,680 bytes)
--    λ> length (show (sucPerrin2 !! (10^5)))
--    12213
--    (1.22 secs, 301,493,408 bytes)
--    λ> length (show (sucPerrin3 !! (10^5)))
--    12213
--    (0.86 secs, 296,911,304 bytes)

-- Usaremos la 3ª
sucPerrin :: [Integer]
sucPerrin = sucPerrin3

-- La propiedad es  
conjeturaPerrin :: Integer -> Property
conjeturaPerrin n =
  n > 1 ==>
  (perrin n `mod` n == 0) == isPrime n

-- (perrin n) es el n-ésimo término de la sucesión de Perrin. Por
-- ejemplo,
--    perrin 4  ==  2
--    perrin 5  ==  5
--    perrin 6  ==  5
perrin :: Integer -> Integer
perrin n = sucPerrin `genericIndex` n

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

import Data.List (genericIndex, unfoldr)

import Data.Numbers.Primes (isPrime)

import Test.QuickCheck

-- 1ª definición

sucPerrin1 :: [Integer]

sucPerrin1 = 3 : 0 : 2 : zipWith (+) sucPerrin1 (tail sucPerrin1)

-- 2ª definición

sucPerrin2 :: [Integer]

sucPerrin2 = [x | (x,_,_) <- iterate op (3,0,2)]

where op (a,b,c) = (b,c,a+b)

-- 3ª definición

sucPerrin3 :: [Integer]

sucPerrin3 =

unfoldr (\(a, (b,c)) -> Just (a, (b,(c,a+b)))) (3,(0,2))

-- Comparación de eficiencia

-- λ> length (show (sucPerrin1 !! (10^5)))

-- 12213

-- (1.44 secs, 295,373,680 bytes)

-- λ> length (show (sucPerrin2 !! (10^5)))

-- 12213

-- (1.22 secs, 301,493,408 bytes)

-- λ> length (show (sucPerrin3 !! (10^5)))

-- 12213

-- (0.86 secs, 296,911,304 bytes)

-- Usaremos la 3ª

sucPerrin :: [Integer]

sucPerrin = sucPerrin3

-- La propiedad es

conjeturaPerrin :: Integer -> Property

conjeturaPerrin n =

n > 1 ==>

(perrin n `mod` n == 0) == isPrime n

-- (perrin n) es el n-ésimo término de la sucesión de Perrin. Por

-- ejemplo,

-- perrin 4 == 2

-- perrin 5 == 5

-- perrin 6 == 5

perrin :: Integer -> Integer

perrin n = sucPerrin `genericIndex` n

-- La comprobación es

-- λ> quickCheck conjeturaPerrin

-- +++ OK, passed 100 tests.

Nota: Aunque QuickCheck no haya encontrado contraejemplos, la propiedad no es cierta. Sólo lo es una de las implicaciones: si n es primo, entonces el n-ésimo término de la sucesión de Perrin es divisible por n. La otra es falsa y los primeros contraejemplos son

   271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291

1	271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291

Listas duplicadas

PorJosé A. Alonso 23-diciembre-201630-diciembre-2016

Se observa que en la cadena «aabbccddeffgg» todos los caracteres están duplicados excepto el ‘e’. Al añadirlo obtenemos la lista «aabbccddeeffgg» y se dice que esta última está duplicada.

También se observa que «aaaabbbccccdd» no está duplicada (porque hay un número impar de ‘b’ consecutivas). Añadiendo una ‘b’ se obtiene «aaaabbbbccccdd» que está duplicada.

Definir las funciones

   esDuplicada :: Eq a => [a] -> Bool
   duplica     :: Eq a => [a] -> [a]

1 2	esDuplicada :: Eq a => [a] -> Bool duplica :: Eq a => [a] -> [a]

tales que

(esDuplicada xs) se verifica si xs es una lista duplicada. Por ejemplo,

     esDuplicada "aabbccddeffgg"   ==  False
     esDuplicada "aabbccddeeffgg"  ==  True
     esDuplicada "aaaabbbccccdd"   ==  False
     esDuplicada "aaaabbbbccccdd"  ==  True

esDuplicada "aabbccddeffgg" == False

esDuplicada "aabbccddeeffgg" == True

esDuplicada "aaaabbbccccdd" == False

esDuplicada "aaaabbbbccccdd" == True

(duplica xs) es la lista obtenida duplicando los elementos de xs que no lo están. Por ejemplo,

     duplica "b"        ==  "bb"
     duplica "abba"     ==  "aabbaa"
     duplica "Betis"    ==  "BBeettiiss"
     duplica [1,1,1]    ==  [1,1,1,1]
     duplica [1,1,1,1]  ==  [1,1,1,1]

duplica "b" == "bb"

duplica "abba" == "aabbaa"

duplica "Betis" == "BBeettiiss"

duplica [1,1,1] == [1,1,1,1]

duplica [1,1,1,1] == [1,1,1,1]

Comprobar con QuickCheck que, para cualquier lista de enteros xs, se verifica la siguiente propiedad:

  esDuplicada (duplica xs)

1	esDuplicada (duplica xs)

Soluciones

import Data.List (group)
import Test.QuickCheck

-- 1ª definición de esDuplicada
esDuplicada :: Eq a => [a] -> Bool
esDuplicada []       = True
esDuplicada [_]      = False
esDuplicada (x:y:zs) = x == y && esDuplicada zs

-- 2ª definición de esDuplicada
esDuplicada2 :: Eq a => [a] -> Bool
esDuplicada2 = all (even . length) . group

-- 1ª definición de duplica
duplica :: Eq a => [a] -> [a]
duplica []       = []
duplica [x]      = [x,x]
duplica (x:y:zs) | x == y    = x : x : duplica zs
                 | otherwise = x : x : duplica (y:zs)

-- 2ª definición de duplica
duplica2 :: Eq a => [a] -> [a]
duplica2 xs = concatMap dupl (group xs)
  where dupl ys@(y:_) | (even.length) ys = ys
                      | otherwise        = y : ys

-- Propiedad
prop_duplica_esDuplicada :: [Int] -> Bool
prop_duplica_esDuplicada xs =
  esDuplicada (duplica xs)

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

import Data.List (group)

import Test.QuickCheck

-- 1ª definición de esDuplicada

esDuplicada :: Eq a => [a] -> Bool

esDuplicada [] = True

esDuplicada [_] = False

esDuplicada (x:y:zs) = x == y && esDuplicada zs

-- 2ª definición de esDuplicada

esDuplicada2 :: Eq a => [a] -> Bool

esDuplicada2 = all (even . length) . group

-- 1ª definición de duplica

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

duplica [] = []

duplica [x] = [x,x]

duplica (x:y:zs) | x == y = x : x : duplica zs

| otherwise = x : x : duplica (y:zs)

-- 2ª definición de duplica

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

duplica2 xs = concatMap dupl (group xs)

where dupl ys@(y:_) | (even.length) ys = ys

| otherwise = y : ys

-- Propiedad

prop_duplica_esDuplicada :: [Int] -> Bool

prop_duplica_esDuplicada xs =

esDuplicada (duplica xs)

-- La comprobación es

-- λ> quickCheck prop_duplica_esDuplicada

-- +++ OK, passed 100 tests.

Elementos que respetan la ordenación

PorJosé A. Alonso 7-diciembre-201614-diciembre-2016

Se dice que un elemento x de una lista xs respeta la ordenación si x es mayor o igual que todos lo que tiene delante en xs y es menor o igual que todos lo que tiene detrás en xs. Por ejemplo, en la lista lista [3,2,1,4,6,5,7,9,8] el número 4 respeta la ordenación pero el número 5 no la respeta (porque es mayor que el 6 que está delante).

Definir la función

   respetuosos :: Ord a => [a] -> [a]

1	respetuosos :: Ord a => [a] -> [a]

tal que (respetuosos xs) es la lista de los elementos de xs que respetan la ordenación. Por ejemplo,

   respetuosos [3,2,1,4,6,4,7,9,8]  ==  [4,7]
   respetuosos [2,1,3,4,6,4,7,8,9]  ==  [3,4,7,8,9]
   respetuosos "abaco"              ==  "aco"
   respetuosos "amor"               ==  "amor"
   respetuosos "romanos"            ==  "s"
   respetuosos [1..9]               ==  [1,2,3,4,5,6,7,8,9]
   respetuosos [9,8..1]             ==  []

respetuosos [3,2,1,4,6,4,7,9,8] == [4,7]

respetuosos [2,1,3,4,6,4,7,8,9] == [3,4,7,8,9]

respetuosos "abaco" == "aco"

respetuosos "amor" == "amor"

respetuosos "romanos" == "s"

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

respetuosos [9,8..1] == []

Comprobar con QuickCheck que para cualquier lista de enteros xs se verifican las siguientes propiedades:

todos los elementos de (sort xs) respetan la ordenación y
en la lista (nub (reverse (sort xs))) hay como máximo un elemento que respeta la ordenación.

Soluciones

import Data.List (inits, nub, sort, tails)
import Test.QuickCheck

-- 1ª definición (por comprensión):
respetuosos :: Ord a => [a] -> [a]
respetuosos xs =
  [z | k <- [0..n-1]
     , let (ys,z:zs) = splitAt k xs
     , all (<=z) ys
     , all (>=z) zs]
  where n = length xs

-- 2ª definición (por recursión):
respetuosos2 :: Ord a => [a] -> [a]
respetuosos2 xs = aux [] [] xs
  where aux zs _  []      = reverse zs
        aux zs ys (x:xs)
          | all (<=x) ys && all (>=x) xs = aux (x:zs) (x:ys) xs
          | otherwise                    = aux zs     (x:ys) xs

-- 3ª definición
respetuosos3 :: Ord a => [a] -> [a]
respetuosos3 xs = [ x | (ys,x,zs) <- zip3 (inits xs) xs (tails xs)
                      , all (<=x) ys
                      , all (x<=) zs ]

-- 4ª solución
respetuosos4 :: Ord a =>[a] ->[a]
respetuosos4 xs =
  [x | (a, x, b) <- zip3 (scanl1 max xs) xs (scanr1 min xs)
     , a <= x && x <= b]

-- Comparación de eficiencia
--    λ> length (respetuosos [1..3000])
--    3000
--    (3.31 secs, 1,140,407,224 bytes)
--    λ> length (respetuosos2 [1..3000])
--    3000
--    (2.85 secs, 587,082,160 bytes)
--    λ> length (respetuosos3 [1..3000])
--    3000
--    (2.12 secs, 785,446,880 bytes)
--    λ> length (respetuosos4 [1..3000])
--    3000
--    (0.02 secs, 0 bytes)

-- 1ª propiedad
prop_respetuosos1 :: [Int] -> Bool
prop_respetuosos1 xs =
  respetuosos (sort xs) == sort xs

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

-- La 2ª propiedad
prop_respetuosos2 :: [Int] -> Bool
prop_respetuosos2 xs =
  length (respetuosos (nub (reverse (sort xs)))) <= 1

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

import Data.List (inits, nub, sort, tails)

import Test.QuickCheck

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

respetuosos :: Ord a => [a] -> [a]

respetuosos xs =

[z | k <- [0..n-1]

, let (ys,z:zs) = splitAt k xs

, all (<=z) ys

, all (>=z) zs]

where n = length xs

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

respetuosos2 :: Ord a => [a] -> [a]

respetuosos2 xs = aux [] [] xs

where aux zs _ [] = reverse zs

aux zs ys (x:xs)

| all (<=x) ys && all (>=x) xs = aux (x:zs) (x:ys) xs

| otherwise = aux zs (x:ys) xs

-- 3ª definición

respetuosos3 :: Ord a => [a] -> [a]

respetuosos3 xs = [ x | (ys,x,zs) <- zip3 (inits xs) xs (tails xs)

, all (<=x) ys

, all (x<=) zs ]

-- 4ª solución

respetuosos4 :: Ord a =>[a] ->[a]

respetuosos4 xs =

[x | (a, x, b) <- zip3 (scanl1 max xs) xs (scanr1 min xs)

, a <= x && x <= b]

-- Comparación de eficiencia

-- λ> length (respetuosos [1..3000])

-- 3000

-- (3.31 secs, 1,140,407,224 bytes)

-- λ> length (respetuosos2 [1..3000])

-- 3000

-- (2.85 secs, 587,082,160 bytes)

-- λ> length (respetuosos3 [1..3000])

-- 3000

-- (2.12 secs, 785,446,880 bytes)

-- λ> length (respetuosos4 [1..3000])

-- 3000

-- (0.02 secs, 0 bytes)

-- 1ª propiedad

prop_respetuosos1 :: [Int] -> Bool

prop_respetuosos1 xs =

respetuosos (sort xs) == sort xs

-- La comprobación es

-- λ> quickCheck prop_respetuosos1

-- +++ OK, passed 100 tests.

-- La 2ª propiedad

prop_respetuosos2 :: [Int] -> Bool

prop_respetuosos2 xs =

length (respetuosos (nub (reverse (sort xs)))) <= 1

-- La comprobación es

-- λ> quickCheck prop_respetuosos2

-- +++ OK, passed 100 tests.

Sin ceros finales

PorJosé A. Alonso 6-diciembre-201613-diciembre-2016

Definir la función

   sinCerosFinales :: Int -> Int

1	sinCerosFinales :: Int -> Int

tal que (sinCerosFinales n) es el número obtenido eliminando los ceros finales de n. Por ejemplo,

   sinCerosFinales 104050     == 10405
   sinCerosFinales 960000     == 96
   sinCerosFinales 100050     == 10005
   sinCerosFinales (-10050)   == -1005
   sinCerosFinales 12         == 12
   sinCerosFinales 0          == 0

sinCerosFinales 104050 == 10405

sinCerosFinales 960000 == 96

sinCerosFinales 100050 == 10005

sinCerosFinales (-10050) == -1005

sinCerosFinales 12 == 12

sinCerosFinales 0 == 0

Comprobar con QuickCheck que, para cualquier número entero n,

   sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

1	sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

Soluciones

import Test.QuickCheck

-- 1ª solución
sinCerosFinales :: Int -> Int
sinCerosFinales 0 = 0
sinCerosFinales n
  | r /= 0    = n
  | otherwise = sinCerosFinales q  
  where (q,r) = quotRem n 10

-- 2ª solución
sinCerosFinales2 :: Int -> Int
sinCerosFinales2 0 = 0
sinCerosFinales2 n =
  read (reverse (dropWhile (=='0') (reverse (show n))))

-- 3ª solución
sinCerosFinales3 :: Int -> Int
sinCerosFinales3 0 = 0
sinCerosFinales3 n =
  (read . reverse . dropWhile (== '0') . reverse . show) n

-- 4ª solución
sinCerosFinales4 :: Int -> Int
sinCerosFinales4 0 = 0
sinCerosFinales4 n =
  read . reverse . dropWhile (== '0') . reverse . show $ n

-- La propiedad es
prop_sinCerosFinales :: Int -> Bool
prop_sinCerosFinales n =
  sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

-- 5ª solución
sinCerosFinales5 :: Int -> Int
sinCerosFinales5 0 = 0
sinCerosFinales5 n = until (\x -> mod x 10 /= 0) (`div` 10) n

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

import Test.QuickCheck

-- 1ª solución

sinCerosFinales :: Int -> Int

sinCerosFinales 0 = 0

sinCerosFinales n

| r /= 0 = n

| otherwise = sinCerosFinales q

where (q,r) = quotRem n 10

-- 2ª solución

sinCerosFinales2 :: Int -> Int

sinCerosFinales2 0 = 0

sinCerosFinales2 n =

read (reverse (dropWhile (=='0') (reverse (show n))))

-- 3ª solución

sinCerosFinales3 :: Int -> Int

sinCerosFinales3 0 = 0

sinCerosFinales3 n =

(read . reverse . dropWhile (== '0') . reverse . show) n

-- 4ª solución

sinCerosFinales4 :: Int -> Int

sinCerosFinales4 0 = 0

sinCerosFinales4 n =

read . reverse . dropWhile (== '0') . reverse . show $ n

-- La propiedad es

prop_sinCerosFinales :: Int -> Bool

prop_sinCerosFinales n =

sinCerosFinales (sinCerosFinales n) == sinCerosFinales n

-- 5ª solución

sinCerosFinales5 :: Int -> Int

sinCerosFinales5 0 = 0

sinCerosFinales5 n = until (\x -> mod x 10 /= 0) (`div` 10) n

-- La comprobación es

-- λ> quickCheck prop_sinCerosFinales

-- +++ OK, passed 100 tests.

Representación binaria de los números de Carol

PorJosé A. Alonso 28-noviembre-20165-diciembre-2016

Un número de Carol es un número entero de la forma $4^n-2^{n+1}-1$ o, equivalentemente, $(2^n-1)^2-2$ . Los primeros números de Carol son -1, 7, 47, 223, 959, 3967, 16127, 65023, 261119, 1046527.

Definir las funciones

   carol        :: Integer -> Integer
   carolBinario :: Integer -> Integer

1 2	carol :: Integer -> Integer carolBinario :: Integer -> Integer

tales que

(carol n) es el n-ésimo número de Carol. Por ejemplo,

     carol  3  ==  47
     carol  4  ==  223
     carol 25  ==  1125899839733759

carol 3 == 47

carol 4 == 223

carol 25 == 1125899839733759

(carolBinario n) es la representación binaria del n-ésimo número de Carol. Por ejemplo,

     carolBinario 3  ==  101111
     carolBinario 4  ==  11011111
     carolBinario 5  ==  1110111111

carolBinario 3 == 101111

carolBinario 4 == 11011111

carolBinario 5 == 1110111111

Comprobar con QuickCheck que, para n > 2, la representación binaria del n-ésimo número de Carol es el número formado por n-2 veces el dígito 1, seguido por un 0 y a continuación n+1 veces el dígito 1.

Soluciones

import Test.QuickCheck

carol :: Integer -> Integer
carol n = x^2 - 2
  where x = 2^n - 1

carolBinario :: Integer -> Integer
carolBinario = binario . carol

-- (binario x) es el número binario correspondiente al número decimal
-- x. Por ejemplo, 
--    binario 223  ==  11011111
binario :: Integer -> Integer 
binario = digitosAnumero . reverse . int2bin

-- (int2bin x) es el número binario (representado como la lista
-- invertida de sus dígitos) correspondiente al número decimal
-- x. Por ejemplo, 
--    int2bin 223  ==  [1,1,1,1,1,0,1,1]
int2bin :: Integer -> [Integer]
int2bin n | n < 2     = [n]
          | otherwise = n `mod` 2 : int2bin (n `div` 2)

-- (digitosAnumero xs) es el número cuya lista de dígitos es xs. Por
-- ejemplo,  
--    digitosAnumero [3,2,5]  ==  325
digitosAnumero :: [Integer] -> Integer
digitosAnumero xs =
  read (concatMap show xs)

-- En la definición anterior se pueden eliminar el argumento
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 = read . (concatMap show)

-- La propiedad es
prop_carol :: Integer -> Property
prop_carol n =
  n > 2 ==> carolBinario n == carolBinario2 n
  where
    carolBinario2 n =
      digitosAnumero ((replicate (m-2) 1) ++ [0] ++ (replicate (m+1) 1))
      where m = fromIntegral n

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

import Test.QuickCheck

carol :: Integer -> Integer

carol n = x^2 - 2

where x = 2^n - 1

carolBinario :: Integer -> Integer

carolBinario = binario . carol

-- (binario x) es el número binario correspondiente al número decimal

-- x. Por ejemplo,

-- binario 223 == 11011111

binario :: Integer -> Integer

binario = digitosAnumero . reverse . int2bin

-- (int2bin x) es el número binario (representado como la lista

-- invertida de sus dígitos) correspondiente al número decimal

-- x. Por ejemplo,

-- int2bin 223 == [1,1,1,1,1,0,1,1]

int2bin :: Integer -> [Integer]

int2bin n | n < 2 = [n]

| otherwise = n `mod` 2 : int2bin (n `div` 2)

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

-- ejemplo,

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

digitosAnumero :: [Integer] -> Integer

digitosAnumero xs =

read (concatMap show xs)

-- En la definición anterior se pueden eliminar el argumento

digitosAnumero2 :: [Integer] -> Integer

digitosAnumero2 = read . (concatMap show)

-- La propiedad es

prop_carol :: Integer -> Property

prop_carol n =

n > 2 ==> carolBinario n == carolBinario2 n

where

carolBinario2 n =

digitosAnumero ((replicate (m-2) 1) ++ [0] ++ (replicate (m+1) 1))

where m = fromIntegral n

-- La comprobación es

-- λ> quickCheck prop_carol

-- +++ OK, passed 100 tests.

Referencias

Carol number por Shashank Mishra en GeeksforGeeks.
Carol number en la Wikipedia.

Números consecutivos compuestos

PorJosé A. Alonso 22-noviembre-201629-noviembre-2016

Una serie compuesta de longitud n es una lista de n números consecutivos que son todos compuestos. Por ejemplo, [8,9,10] y [24,25,26] son dos series compuestas de longitud 3.

Cada serie compuesta se puede representar por el par formado por su primer y último elemento. Por ejemplo, las dos series anteriores se pueden representar pos (8,10) y (24,26) respectivamente.

Definir la función

   menorSerieCompuesta :: Integer -> (Integer,Integer)

1	menorSerieCompuesta :: Integer -> (Integer,Integer)

tal que (menorSerieCompuesta n) es la menor serie compuesta (es decir, la que tiene menores elementos) de longitud 3. Por ejemplo,

   menorSerieCompuesta 3    ==  (8,10)
   menorSerieCompuesta 4    ==  (24,27)
   menorSerieCompuesta 5    ==  (24,28)
   menorSerieCompuesta 150  ==  (4652354,4652503)

menorSerieCompuesta 3 == (8,10)

menorSerieCompuesta 4 == (24,27)

menorSerieCompuesta 5 == (24,28)

menorSerieCompuesta 150 == (4652354,4652503)

Comprobar con QuickCheck que para n > 1, el primer elemento de (menorSerieCompuesta n) es igual al primero de (menorSerieCompuesta (n-1)) o al primero de (menorSerieCompuesta (n+1)).

Soluciones

import Data.Numbers.Primes
import Test.QuickCheck

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

menorSerieCompuesta1 :: Integer -> (Integer,Integer)
menorSerieCompuesta1 n = (x,x+n-1)
  where x = head [y | y <- [1..]
                    , esCompuesta [y..y+n-1]]

esCompuesta :: [Integer] -> Bool
esCompuesta xs =  all (not . isPrime) xs

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

menorSerieCompuesta2 :: Integer -> (Integer,Integer)
menorSerieCompuesta2 n = (x+1,x+n)
  where (x,y) = head [(p,q) | (p,q) <- zip primes (tail primes)
                            , q - p >= n + 1]

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

--    λ> menorSerieCompuesta1 75
--    (155922,155996)
--    (12.16 secs, 30,378,380,552 bytes)
--    λ> menorSerieCompuesta2 75
--    (155922,155996)
--    (0.07 secs, 89,813,752 bytes)


-- Comprobación de la propiedad
-- ============================

-- La propiedad es
prop_menorSerieCompuesta :: Integer -> Property
prop_menorSerieCompuesta n =
  n > 1 ==> x == y || y == z
  where [x,y,z] = map (fst . menorSerieCompuesta2) [n-1,n,n+1]

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

import Data.Numbers.Primes

import Test.QuickCheck

-- 1ª definición

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

menorSerieCompuesta1 :: Integer -> (Integer,Integer)

menorSerieCompuesta1 n = (x,x+n-1)

where x = head [y | y <- [1..]

, esCompuesta [y..y+n-1]]

esCompuesta :: [Integer] -> Bool

esCompuesta xs = all (not . isPrime) xs

-- 2ª definición

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

menorSerieCompuesta2 :: Integer -> (Integer,Integer)

menorSerieCompuesta2 n = (x+1,x+n)

where (x,y) = head [(p,q) | (p,q) <- zip primes (tail primes)

, q - p >= n + 1]

-- Comparación de eficiencia

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

-- λ> menorSerieCompuesta1 75

-- (155922,155996)

-- (12.16 secs, 30,378,380,552 bytes)

-- λ> menorSerieCompuesta2 75

-- (155922,155996)

-- (0.07 secs, 89,813,752 bytes)

-- Comprobación de la propiedad

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

-- La propiedad es

prop_menorSerieCompuesta :: Integer -> Property

prop_menorSerieCompuesta n =

n > 1 ==> x == y || y == z

where [x,y,z] = map (fst . menorSerieCompuesta2) [n-1,n,n+1]

-- La comprobación es

-- λ> quickCheck prop_menorSerieCompuesta

-- +++ OK, passed 100 tests.

Referencias

Sucesión A030296 de la OEIS.

Persistencia multiplicativa de un número

PorJosé A. Alonso 14-noviembre-201621-noviembre-2016

La persistencia multiplicativa de un número es la cantidad de pasos requeridos para reducirlo a una cifra multiplicando sus dígitos. Por ejemplo, la persistencia de 39 es 3 porque 3×9 = 27, 2×7 = 14 y 1×4 = 4.

Definir las funciones

   persistencia     :: Integer -> Integer
   menorPersistente :: Integer -> Integer

1 2	persistencia :: Integer -> Integer menorPersistente :: Integer -> Integer

tales que

(persistencia x) es la persistencia de x. Por ejemplo,

     persistencia 39                             ==   3
     persistencia 2677889                        ==   8
     persistencia 26888999                       ==   9
     persistencia 3778888999                     ==  10
     persistencia 277777788888899                ==  11
     persistencia 77777733332222222222222222222  ==  11

persistencia 39 == 3

persistencia 2677889 == 8

persistencia 26888999 == 9

persistencia 3778888999 == 10

persistencia 277777788888899 == 11

persistencia 77777733332222222222222222222 == 11

(menorPersistente n) es el menor número con persistencia n. Por ejemplo,

     menorPersistente 0  ==  1
     menorPersistente 1  ==  10
     menorPersistente 2  ==  25
     menorPersistente 3  ==  39
     menorPersistente 4  ==  77
     menorPersistente 5  ==  679
     menorPersistente 6  ==  6788
     menorPersistente 7  ==  68889

menorPersistente 0 == 1

menorPersistente 1 == 10

menorPersistente 2 == 25

menorPersistente 3 == 39

menorPersistente 4 == 77

menorPersistente 5 == 679

menorPersistente 6 == 6788

menorPersistente 7 == 68889

Comprobar con QuickCheck si todos los números menores que 10^233 tienen una persistencia multiplicativa menor o igual que 11.

Nota: Este ejercicio ha sido propuesto por Marcos Giráldez.

Soluciones

import Test.QuickCheck

persistencia :: Integer -> Integer
persistencia x
  | x < 10    = 0
  | otherwise = 1 + persistencia (productoDigitos x)

productoDigitos :: Integer -> Integer
productoDigitos x 
  | x < 10    = x
  | otherwise = r * productoDigitos y
  where (y,r) = quotRem x 10

menorPersistente :: Integer -> Integer
menorPersistente n =
  head [x | x <- [1..]
          , persistencia x == n]

-- La propiedad es
prop_persistencia :: Integer -> Property
prop_persistencia x =
  x <= y ==> persistencia x <= 11
  where y = 10^233

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

import Test.QuickCheck

persistencia :: Integer -> Integer

persistencia x

| x < 10 = 0

| otherwise = 1 + persistencia (productoDigitos x)

productoDigitos :: Integer -> Integer

productoDigitos x

| x < 10 = x

| otherwise = r * productoDigitos y

where (y,r) = quotRem x 10

menorPersistente :: Integer -> Integer

menorPersistente n =

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

, persistencia x == n]

-- La propiedad es

prop_persistencia :: Integer -> Property

prop_persistencia x =

x <= y ==> persistencia x <= 11

where y = 10^233

-- La comprobación es

-- λ> quickCheck prop_persistencia

-- +++ OK, passed 100 tests.

Referencias

Persistencia multiplicativa y el número 77777733332222222222222222222 por M. Macho
Multiplicative persistence por Eric W. Weisstein en MathWorld.
Sucesión A003001 de la OEIS.

Número de divisiones en el algoritmo de Euclides

PorJosé A. Alonso 5-mayo-201612-mayo-2016

Dados dos números naturales, a y b, es posible calcular su máximo común divisor mediante el Algoritmo de Euclides. Este algoritmo se puede resumir en la siguiente fórmula:

   mcd(a,b) = a,                   si b = 0
            = b,                   si a = 0               
            = mcd (a módulo b, b), si a > b
            = mcd (a, b módulo a), si b >= a

mcd(a,b) = a, si b = 0

= b, si a = 0

= mcd (a módulo b, b), si a > b

= mcd (a, b módulo a), si b >= a

Definir la función

   mcdYdivisiones :: Int -> Int -> (Int,Int)

1	mcdYdivisiones :: Int -> Int -> (Int,Int)

tal que (mcdYdivisiones a b) es el número de divisiones usadas en el cálculo del máximo común divisor de a y b mediante el algoritmo de Euclides. Por ejemplo,

   mcdYdivisiones 252 198 == (18,4)

1	mcdYdivisiones 252 198 == (18,4)

ya que los 4 divisiones del cálculo son

     mcd 252 198
   = mcd  54 198
   = mcd  54  36
   = mcd  18  36
   = mcd  18   0

mcd 252 198

= mcd 54 198

= mcd 54 36

= mcd 18 36

= mcd 18 0

Comprobar con QuickCheck que el número de divisiones requeridas por el algoritmo de Euclides para calcular el MCD de a y b es igual o menor que cinco veces el número de dígitos de menor de los números a y b.

Soluciones

import Test.QuickCheck
import Debug.Trace 

mcdYdivisiones :: Int -> Int -> (Int,Int)
mcdYdivisiones a b = mcd a b 0
    where mcd a 0 n = (a,n)
          mcd 0 b n = (b,n)
          mcd a b n | a > b     = mcd (a `mod` b) b (n+1)
                    | otherwise = mcd a (b `mod` a) (n+1) 

-- La propiedad es
prop_mcdYdivisiones :: Int -> Int -> Property
prop_mcdYdivisiones a b =
    a > 0 && b > 0 ==>
      n < 5 * length (show (min a b))  
    where (_,n) = mcdYdivisiones a b
                 
-- La comprobación es
--    λ> quickCheck prop_mcdYdivisiones
--    +++ OK, passed 100 tests.

-- 2ª definición (con traza)
mcdYdivisiones2 :: Int -> Int -> (Int,Int)
mcdYdivisiones2 a b = mcd a b 0
    where mcd a b n
              | trace (show a ++ ", " ++ show b) False = undefined
          mcd a 0 n = (a,n)
          mcd 0 b n = (b,n)
          mcd a b n | a > b     = mcd (a `mod` b) b (n+1)
                    | otherwise = mcd a (b `mod` a) (n+1) 

-- Por ejemplo,
--    λ> mcdYdivisiones2 252 198
--    252, 198
--    54, 198
--    54, 36
--    18, 36
--    18, 0
--    (18,4)

import Test.QuickCheck

import Debug.Trace

mcdYdivisiones :: Int -> Int -> (Int,Int)

mcdYdivisiones a b = mcd a b 0

where mcd a 0 n = (a,n)

mcd 0 b n = (b,n)

mcd a b n | a > b = mcd (a `mod` b) b (n+1)

| otherwise = mcd a (b `mod` a) (n+1)

-- La propiedad es

prop_mcdYdivisiones :: Int -> Int -> Property

prop_mcdYdivisiones a b =

a > 0 && b > 0 ==>

n < 5 * length (show (min a b))

where (_,n) = mcdYdivisiones a b

-- La comprobación es

-- λ> quickCheck prop_mcdYdivisiones

-- +++ OK, passed 100 tests.

-- 2ª definición (con traza)

mcdYdivisiones2 :: Int -> Int -> (Int,Int)

mcdYdivisiones2 a b = mcd a b 0

where mcd a b n

| trace (show a ++ ", " ++ show b) False = undefined

mcd a 0 n = (a,n)

mcd 0 b n = (b,n)

mcd a b n | a > b = mcd (a `mod` b) b (n+1)

| otherwise = mcd a (b `mod` a) (n+1)

-- Por ejemplo,

-- λ> mcdYdivisiones2 252 198

-- 252, 198

-- 54, 198

-- 54, 36

-- 18, 36

-- 18, 0

-- (18,4)

Raíz entera

PorJosé A. Alonso 8-abril-20161-mayo-2016

Definir la función

   raizEnt :: Integer -> Integer -> Integer

1	raizEnt :: Integer -> Integer -> Integer

tal que (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor número entero y tal que y^n <= x. Por ejemplo,

   raizEnt  8 3      ==  2
   raizEnt  9 3      ==  2
   raizEnt 26 3      ==  2
   raizEnt 27 3      ==  3
   raizEnt (10^50) 2 ==  10000000000000000000000000

raizEnt 8 3 == 2

raizEnt 9 3 == 2

raizEnt 26 3 == 2

raizEnt 27 3 == 3

raizEnt (10^50) 2 == 10000000000000000000000000

Comprobar con QuickCheck que para todo número natural n,

    raizEnt (10^(2*n)) 2 == 10^n

1	raizEnt (10^(2*n)) 2 == 10^n

Soluciones

import Test.QuickCheck

-- 1ª definición
raizEnt1 :: Integer -> Integer -> Integer
raizEnt1 x n =
    last (takeWhile (\y -> y^n <= x) [0..])

-- 2ª definición         
raizEnt2 :: Integer -> Integer -> Integer
raizEnt2 x n =
    floor ((fromIntegral x)**(1 / fromIntegral n))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,
--    λ> raizEnt2 (10^50) 2 == 10^25
--    False
          
-- 3ª definición          
raizEnt3 :: Integer -> Integer -> Integer
raizEnt3 x n = aux (1,x)
    where aux (a,b) | d == x    = c
                    | c == a    = c
                    | d < x     = aux (c,b)
                    | otherwise = aux (a,c) 
              where c = (a+b) `div` 2
                    d = c^n

-- Comparación de eficiencia
--    λ> raizEnt1 (10^14) 2
--    10000000
--    (6.15 secs, 6,539,367,976 bytes)
--    λ> raizEnt2 (10^14) 2
--    10000000
--    (0.00 secs, 0 bytes)
--    λ> raizEnt3 (10^14) 2
--    10000000
--    (0.00 secs, 25,871,944 bytes)
--    
--    λ> raizEnt2 (10^50) 2
--    9999999999999998758486016
--    (0.00 secs, 0 bytes)
--    λ> raizEnt3 (10^50) 2
--    10000000000000000000000000
--    (0.00 secs, 0 bytes)
                        
-- La propiedad es                        
prop_raizEnt :: Integer -> Bool
prop_raizEnt n =
    raizEnt3 (10^(2*m)) 2 == 10^m
    where m = abs n

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

import Test.QuickCheck

-- 1ª definición

raizEnt1 :: Integer -> Integer -> Integer

raizEnt1 x n =

last (takeWhile (\y -> y^n <= x) [0..])

-- 2ª definición

raizEnt2 :: Integer -> Integer -> Integer

raizEnt2 x n =

floor ((fromIntegral x)**(1 / fromIntegral n))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,

-- λ> raizEnt2 (10^50) 2 == 10^25

-- False

-- 3ª definición

raizEnt3 :: Integer -> Integer -> Integer

raizEnt3 x n = aux (1,x)

where aux (a,b) | d == x = c

| c == a = c

| d < x = aux (c,b)

| otherwise = aux (a,c)

where c = (a+b) `div` 2

d = c^n

-- Comparación de eficiencia

-- λ> raizEnt1 (10^14) 2

-- 10000000

-- (6.15 secs, 6,539,367,976 bytes)

-- λ> raizEnt2 (10^14) 2

-- 10000000

-- (0.00 secs, 0 bytes)

-- λ> raizEnt3 (10^14) 2

-- 10000000

-- (0.00 secs, 25,871,944 bytes)

-- λ> raizEnt2 (10^50) 2

-- 9999999999999998758486016

-- (0.00 secs, 0 bytes)

-- λ> raizEnt3 (10^50) 2

-- 10000000000000000000000000

-- (0.00 secs, 0 bytes)

-- La propiedad es

prop_raizEnt :: Integer -> Bool

prop_raizEnt n =

raizEnt3 (10^(2*m)) 2 == 10^m

where m = abs n

-- La comprobación es

-- λ> quickCheck prop_raizEnt

-- +++ OK, passed 100 tests.

Soluciones en Maxima

raizEnt (x,n) := inrt (x,n)$

1	raizEnt (x,n) := inrt (x,n)$

Factorial generalizado

PorJosé A. Alonso 4-abril-201611-abril-2016

El factorial generalizado de x respecto de y y z es el producto x(x-z)(x-2z) … (x-(y-1)z). Por ejemplo, el factorial generalizado de 7 respecto de 3 y 2 es 7x5x3 = 105 y el de 7 respecto de 2 y 3 es 7×4 = 28

Definir la función

   factGen :: Integer -> Integer -> Integer -> Integer

1	factGen :: Integer -> Integer -> Integer -> Integer

tal que (factGen x y z) es el factorial generalizado de x respecto de y y z. Por ejemplo,

   factGen 7 3 2  ==  105
   factGen 7 2 3  ==  28

1 2	factGen 7 3 2 == 105 factGen 7 2 3 == 28

Nota: Se supone que x, y y z son positivos y z < x.

Comprobar con QuickCheck que (factGen x x 1) es el factorial de x.

Soluciones

import Test.QuickCheck

-- 1ª definición (por comprensión):
factGen :: Integer -> Integer -> Integer -> Integer
factGen x y z = product [x,x-z..x-(y-1)*z]

-- 2ª definición (por recursión):
factGen2 :: Integer -> Integer -> Integer -> Integer
factGen2 x 1 _ = x
factGen2 x y z = x * factGen2 (x-z) (y-1) z

-- Propiedad de equivalencia
prop_equiv :: Positive Integer
           -> Positive Integer -> Positive Integer -> Property
prop_equiv (Positive x) (Positive y) (Positive z) =
    z < x ==> factGen x y z == factGen2 x y z

-- La comprobación es
--    λ> quickCheck prop_equiv
--    +++ OK, passed 100 tests.
      
-- La propiedad es       
prop_factGen :: Positive Integer -> Bool
prop_factGen (Positive x) =
    factGen x x 1 == product [1..x]

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

import Test.QuickCheck

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

factGen :: Integer -> Integer -> Integer -> Integer

factGen x y z = product [x,x-z..x-(y-1)*z]

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

factGen2 :: Integer -> Integer -> Integer -> Integer

factGen2 x 1 _ = x

factGen2 x y z = x * factGen2 (x-z) (y-1) z

-- Propiedad de equivalencia

prop_equiv :: Positive Integer

-> Positive Integer -> Positive Integer -> Property

prop_equiv (Positive x) (Positive y) (Positive z) =

z < x ==> factGen x y z == factGen2 x y z

-- La comprobación es

-- λ> quickCheck prop_equiv

-- +++ OK, passed 100 tests.

-- La propiedad es

prop_factGen :: Positive Integer -> Bool

prop_factGen (Positive x) =

factGen x x 1 == product [1..x]

-- La comprobación es

-- λ> quickCheck prop_factGen

-- +++ OK, passed 100 tests.

Solución en Maxima

factGen (x,y,z) := genfact (x,y,z)$

1	factGen (x,y,z) := genfact (x,y,z)$

Representación decimal de números racionales

PorJosé A. Alonso 1-abril-20168-abril-2016

Los números decimales se representan por ternas, donde el primer elemento es la parte entera, el segundo es el anteperíodo y el tercero es el período. Por ejemplo,

    6/2  = 3                  se representa por (3,[],[])
    1/2  = 0.5                se representa por (0,[5],[])
    1/3  = 0.333333...        se representa por (0,[],[3])  
   23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

6/2 = 3 se representa por (3,[],[])

1/2 = 0.5 se representa por (0,[5],[])

1/3 = 0.333333... se representa por (0,[],[3])

23/14 = 1.6428571428571... se representa por (1,[6],[4,2,8,5,7,1])

Su tipo es

   type Decimal = (Integer,[Integer],[Integer])

1	type Decimal = (Integer,[Integer],[Integer])

Los números racionales se representan por un par de enteros, donde el primer elemento es el numerador y el segundo el denominador. Por ejemplo, el número 2/3 se representa por (2,3). Su tipo es

   type Racional = (Integer,Integer)

1	type Racional = (Integer,Integer)

Definir las funciones

   decimal  :: Racional -> Decimal
   racional :: Decimal -> Racional

1 2	decimal :: Racional -> Decimal racional :: Decimal -> Racional

tales que

(decimal r) es la representación decimal del número racional r. Por ejemplo,

        decimal (1,4)    ==  (0,[2,5],[])
        decimal (1,3)    ==  (0,[],[3])
        decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])

decimal (1,4) == (0,[2,5],[])

decimal (1,3) == (0,[],[3])

decimal (23,14) == (1,[6],[4,2,8,5,7,1])

(racional d) es el número racional cuya representación decimal es d. Por ejemplo,

        racional (0,[2,5],[])           ==  (1,4)
        racional (0,[],[3])             ==  (1,3)
        racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)

racional (0,[2,5],[]) == (1,4)

racional (0,[],[3]) == (1,3)

racional (1,[6],[4,2,8,5,7,1]) == (23,14)

Con la función decimal se puede calcular los períodos de los números racionales. Por ejemplo,

   ghci> let (_,_,p) = decimal (23,14) in concatMap show p
   "428571"
   ghci> let (_,_,p) = decimal (1,47) in concatMap show p
   "0212765957446808510638297872340425531914893617"
   ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)
   540

ghci> let (_,_,p) = decimal (23,14) in concatMap show p

"428571"

ghci> let (_,_,p) = decimal (1,47) in concatMap show p

"0212765957446808510638297872340425531914893617"

ghci> let (_,_,p) = decimal (1,541) in length (concatMap show p)

540

Comprobar con QuickCheck si las funciones decimal y racional son inversas.

Soluciones

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Data.List
import Test.QuickCheck

-- ---------------------------------------------------------------------
-- § Tipos                                                            --
-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el
-- primer elemento es el numerador y el segundo el denominador.
type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte
-- entera, el segundo es el anteperíodo y el tercero es el período.
type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------
-- § De racional a decimal                                            --
-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,
--    mayorExponente 2 40  ==  3
--    mayorExponente 5 40  ==  1
--    mayorExponente 5 41  ==  0
mayorExponente :: Integer -> Integer -> Integer
mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudAnteperiodo 2   ==  1
--    longitudAnteperiodo 3   ==  0
--    longitudAnteperiodo 14  ==  1
longitudAnteperiodo :: Integer -> Integer
longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de
-- cualquier fracción irreducible de denominador n). Por ejemplo, 
--    longitudPeriodo 2  ==  0
--    longitudPeriodo 3  ==  1
--    longitudPeriodo 7  ==  6
longitudPeriodo :: Integer -> Integer
longitudPeriodo n
    | m == 1    = 0 
    | otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]
    where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo, 
--    take 10 (expansionDec (1,4))    ==  [0,2,5]
--    take 10 (expansionDec (1,7))    ==  [0,1,4,2,8,5,7,1,4,2]
--    take 12 (expansionDec (90,7))   ==  [12,8,5,7,1,4,2,8,5,7,1,4]
--    take 12 (expansionDec (23,14))  ==  [1,6,4,2,8,5,7,1,4,2,8,5]
expansionDec :: Racional -> [Integer]
expansionDec (x,y) 
    | r == 0    = [q] 
    | otherwise = q : expansionDec (r*10,y)
    where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,
--    parteEntera (125,3)  ==  41
parteEntera :: Racional -> Integer
parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de
-- cifras que se encuentran entre la parte entera y el primer período de
-- a/b. Por ejemplo,
--    antePeriodo (23,14)  ==  [6]
--    antePeriodo (1,5)    ==  [2]
antePeriodo :: Racional -> [Integer]
antePeriodo (a,b) = genericTake s (tail xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b; es decir, la lista de cifras que
-- se encuentran entre la parte entera y el primer período de a/b. Por
-- ejemplo, 
--    periodo (1,3)                   ==  [3]
--    periodo (1,5)                   ==  []
--    periodo (1,7)                   ==  [1,4,2,8,5,7]
--    periodo (23,14)                 ==  [4,2,8,5,7,1]
--    concatMap show $ periodo (1,29) == "0344827586206896551724137931"
periodo :: Racional -> [Integer]
periodo (a,b) = genericTake t (genericDrop (1+s) xs)
    where xs = expansionDec (a,b)
          s  = longitudAnteperiodo b
          t  = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por
-- ejemplo, 
--    reducido (40,80)  ==  (1,2)
reducido :: Racional -> Racional
reducido (a,b) = (a `div` m, b `div` m) 
    where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna
-- formada por la parte entera, la parte decimal pura y la parte decimal
-- periódica. Por ejemplo, 
--    decimal (1,4)    ==  (0,[2,5],[])
--    decimal (1,3)    ==  (0,[],[3])
--    decimal (23,14)  ==  (1,[6],[4,2,8,5,7,1])
decimal :: Racional -> Decimal
decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)
    where r = reducido (a,b)

-- ---------------------------------------------------------------------
-- § De decimal a racional                                            --
-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de
-- dígitos xs. Por ejemplo,
--    digitosAnumero [3,2,5]  ==  325
digitosAnumero :: [Integer] -> Integer
digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)
digitosAnumero2 :: [Integer] -> Integer
digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]
    where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación
-- decimal es (x,ys,zs). Por ejemplo,
--    racional (0,[2,5],[])           ==  (1,4)
--    racional (0,[],[3])             ==  (1,3)
--    racional (1,[6],[4,2,8,5,7,1])  ==  (23,14)
racional :: Decimal -> Racional
racional (x,ys,[]) = reducido (a,b) where
    a = digitosAnumero (x:ys)
    b = 10^(length ys)
racional (x,ys,zs) = reducido (a,b) where 
    a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)
    b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------
-- § Propiedades                                                      --
-- ---------------------------------------------------------------------

-- La 1ª propiedad es
prop_RacionalDecimal :: Racional -> Property
prop_RacionalDecimal (a,b) =
    a >= 0 && b > 0  ==>
    racional (decimal (a,b)) == reducido (a,b)

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

-- En lugar de reducido se puede usar un generador de números racionales
numeroRacional :: Gen Racional
numeroRacional = do a <- arbitrary
                    b <- arbitrary
                    return (reducido (abs a, 1+ abs b))

-- La propiedad es
prop_RacionalDecimal2 :: Property
prop_RacionalDecimal2 =
    forAll numeroRacional
           (\(a,b) -> racional (decimal (a,b)) == (a,b))

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

-- Para la 2ª propiedad se define un generador de números decimales
numeroDecimal :: Gen Decimal
numeroDecimal = do a <- arbitrary
                   b <- arbitrary
                   return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es
prop_DecimalRacional :: Property
prop_DecimalRacional =
    forAll numeroDecimal 
           (\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

-- ---------------------------------------------------------------------

-- § Librerías auxiliares --

-- ---------------------------------------------------------------------

import Data.List

import Test.QuickCheck

-- ---------------------------------------------------------------------

-- § Tipos --

-- ---------------------------------------------------------------------

-- Un número racional se representa por un par de enteros, donde el

-- primer elemento es el numerador y el segundo el denominador.

type Racional = (Integer,Integer)

-- Un número decimal es una terna donde el primer elemento es la parte

-- entera, el segundo es el anteperíodo y el tercero es el período.

type Decimal = (Integer,[Integer],[Integer])

-- ---------------------------------------------------------------------

-- § De racional a decimal --

-- ---------------------------------------------------------------------

-- (mayorExponente a x) es el mayor n tal que a^n divide a x. Por ejemplo,

-- mayorExponente 2 40 == 3

-- mayorExponente 5 40 == 1

-- mayorExponente 5 41 == 0

mayorExponente :: Integer -> Integer -> Integer

mayorExponente a x = head [n | n <- [1..], mod x (a^n) /= 0] - 1

-- (longitudAnteperiodo n) es la longitud del anteperíodo de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudAnteperiodo 2 == 1

-- longitudAnteperiodo 3 == 0

-- longitudAnteperiodo 14 == 1

longitudAnteperiodo :: Integer -> Integer

longitudAnteperiodo n = max (mayorExponente 2 n) (mayorExponente 5 n)

-- (longitudPeriodo n) es la longitud del período de 1/n (y de

-- cualquier fracción irreducible de denominador n). Por ejemplo,

-- longitudPeriodo 2 == 0

-- longitudPeriodo 3 == 1

-- longitudPeriodo 7 == 6

longitudPeriodo :: Integer -> Integer

longitudPeriodo n

| m == 1 = 0

| otherwise = head [k | k <- [1..], (10^k) `mod` m == 1]

where m = n `div` (2^(mayorExponente 2 n) * 5^(mayorExponente 5 n))

-- (expansionDec (x,y)) es la expansión decimal de x/y. Por ejemplo,

-- take 10 (expansionDec (1,4)) == [0,2,5]

-- take 10 (expansionDec (1,7)) == [0,1,4,2,8,5,7,1,4,2]

-- take 12 (expansionDec (90,7)) == [12,8,5,7,1,4,2,8,5,7,1,4]

-- take 12 (expansionDec (23,14)) == [1,6,4,2,8,5,7,1,4,2,8,5]

expansionDec :: Racional -> [Integer]

expansionDec (x,y)

| r == 0 = [q]

| otherwise = q : expansionDec (r*10,y)

where (q,r) = quotRem x y

-- (parteEntera (a,b)) es la parte entera de a/b. Por ejemplo,

-- parteEntera (125,3) == 41

parteEntera :: Racional -> Integer

parteEntera (a,b) = a `div` b

-- (antePeriodo (a,b)) es el anteperíodo de a/b; es decir, la lista de

-- cifras que se encuentran entre la parte entera y el primer período de

-- a/b. Por ejemplo,

-- antePeriodo (23,14) == [6]

-- antePeriodo (1,5) == [2]

antePeriodo :: Racional -> [Integer]

antePeriodo (a,b) = genericTake s (tail xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

-- (periodo (a,b)) es el período de a/b; es decir, la lista de cifras que

-- se encuentran entre la parte entera y el primer período de a/b. Por

-- ejemplo,

-- periodo (1,3) == [3]

-- periodo (1,5) == []

-- periodo (1,7) == [1,4,2,8,5,7]

-- periodo (23,14) == [4,2,8,5,7,1]

-- concatMap show $ periodo (1,29) == "0344827586206896551724137931"

periodo :: Racional -> [Integer]

periodo (a,b) = genericTake t (genericDrop (1+s) xs)

where xs = expansionDec (a,b)

s = longitudAnteperiodo b

t = longitudPeriodo b

-- (reducido (a,b)) es la forma reducida del número racional a/b. Por

-- ejemplo,

-- reducido (40,80) == (1,2)

reducido :: Racional -> Racional

reducido (a,b) = (a `div` m, b `div` m)

where m = gcd a b

-- (decimal (x,y)) es la forma decimal de x/y; es decir, la terna

-- formada por la parte entera, la parte decimal pura y la parte decimal

-- periódica. Por ejemplo,

-- decimal (1,4) == (0,[2,5],[])

-- decimal (1,3) == (0,[],[3])

-- decimal (23,14) == (1,[6],[4,2,8,5,7,1])

decimal :: Racional -> Decimal

decimal (a,b) = (parteEntera r, antePeriodo r, periodo r)

where r = reducido (a,b)

-- ---------------------------------------------------------------------

-- § De decimal a racional --

-- ---------------------------------------------------------------------

-- (digitosAnumero xs) es el número correspondiente a la lista de

-- dígitos xs. Por ejemplo,

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

digitosAnumero :: [Integer] -> Integer

digitosAnumero = foldl (\a y -> 10*a+y) 0

-- 2ª definición de digitosAnumero (por comprensión)

digitosAnumero2 :: [Integer] -> Integer

digitosAnumero2 xs = sum [x*(10^i) | (x,i) <- zip xs [n-1,n-2..0]]

where n = length xs

-- (racional (x,ys,zs)) es el número racional cuya representación

-- decimal es (x,ys,zs). Por ejemplo,

-- racional (0,[2,5],[]) == (1,4)

-- racional (0,[],[3]) == (1,3)

-- racional (1,[6],[4,2,8,5,7,1]) == (23,14)

racional :: Decimal -> Racional

racional (x,ys,[]) = reducido (a,b) where

a = digitosAnumero (x:ys)

b = 10^(length ys)

racional (x,ys,zs) = reducido (a,b) where

a = digitosAnumero (x:ys++zs) - digitosAnumero (x:ys)

b = digitosAnumero (replicate (length zs) 9 ++ replicate (length ys) 0)

-- ---------------------------------------------------------------------

-- § Propiedades --

-- ---------------------------------------------------------------------

-- La 1ª propiedad es

prop_RacionalDecimal :: Racional -> Property

prop_RacionalDecimal (a,b) =

a >= 0 && b > 0 ==>

racional (decimal (a,b)) == reducido (a,b)

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal

-- +++ OK, passed 100 tests.

-- En lugar de reducido se puede usar un generador de números racionales

numeroRacional :: Gen Racional

numeroRacional = do a <- arbitrary

b <- arbitrary

return (reducido (abs a, 1+ abs b))

-- La propiedad es

prop_RacionalDecimal2 :: Property

prop_RacionalDecimal2 =

forAll numeroRacional

(\(a,b) -> racional (decimal (a,b)) == (a,b))

-- La comprobación es

-- ghci> quickCheck prop_RacionalDecimal2

-- +++ OK, passed 100 tests.

-- Para la 2ª propiedad se define un generador de números decimales

numeroDecimal :: Gen Decimal

numeroDecimal = do a <- arbitrary

b <- arbitrary

return (decimal (abs a, 1+ abs b))

-- La 2ª propiedad es

prop_DecimalRacional :: Property

prop_DecimalRacional =

forAll numeroDecimal

(\(x,ys,zs) -> decimal (racional (x,ys,zs)) == (x,ys,zs))

-- La comprobación es

-- ghci> quickCheck prop_DecimalRacional

-- +++ OK, passed 100 tests.

Números cuyos dígitos coinciden con los de sus factores primos

PorJosé A. Alonso 30-marzo-201625-marzo-2022

Un número n es especial si al unir los dígitos de sus factores primos, se obtienen exactamente los dígitos de n, aunque puede ser en otro orden. Por ejemplo, 1255 es especial, pues los factores primos de 1255 son 5 y 251.

Definir la función

   esEspecial :: Integer -> Bool

1	esEspecial :: Integer -> Bool

tal que (esEspecial n) se verifica si un número n es especial. Por ejemplo,

   esEspecial 1255 == True
   esEspecial 125  == False
   esEspecial 132  == False

esEspecial 1255 == True

esEspecial 125 == False

esEspecial 132 == False

Comprobar con QuickCheck que todo número primo es especial.

Calcular los 5 primeros números especiales que no son primos.

Soluciones

import Data.List (nub, sort)
import Data.Numbers.Primes (isPrime, primeFactors)
import Test.QuickCheck

esEspecial :: Integer -> Bool
esEspecial n = 
    sort (show n) == sort (concatMap show (nub (primeFactors n)))

-- La propiedad es
prop_primos:: Integer -> Property
prop_primos n = 
    isPrime (abs n) ==> esEspecial (abs n)

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

-- El cálculo es
--    ghci> take 5 [n | n <- [2..], esEspecial n, not (isPrime n)]
--    [735,1255,3792,7236,11913]

import Data.List (nub, sort)

import Data.Numbers.Primes (isPrime, primeFactors)

import Test.QuickCheck

esEspecial :: Integer -> Bool

esEspecial n =

sort (show n) == sort (concatMap show (nub (primeFactors n)))

-- La propiedad es

prop_primos:: Integer -> Property

prop_primos n =

isPrime (abs n) ==> esEspecial (abs n)

-- La comprobación es

-- ghci> quickCheck prop_primos

-- +++ OK, passed 100 tests.

-- El cálculo es

-- ghci> take 5 [n | n <- [2..], esEspecial n, not (isPrime n)]

-- [735,1255,3792,7236,11913]

Menor no expresable como suma

PorJosé A. Alonso 7-marzo-201625-abril-2021

Definir la función

   menorNoSuma :: [Integer] -> Integer

1	menorNoSuma :: [Integer] -> Integer

tal que (menorNoSuma xs) es el menor número que no se puede escribir como suma de un subconjunto de xs, donde se supone que xs es un conjunto de números enteros positivos. Por ejemplo,

   menorNoSuma [6,1,2]    ==  4
   menorNoSuma [1,2,3,9]  ==  7
   menorNoSuma [5]        ==  1
   menorNoSuma [1..20]    ==  211
   menorNoSuma [1..10^6]  ==  500000500001

menorNoSuma [6,1,2] == 4

menorNoSuma [1,2,3,9] == 7

menorNoSuma [5] == 1

menorNoSuma [1..20] == 211

menorNoSuma [1..10^6] == 500000500001

Comprobar con QuickCheck que para todo n,

   menorNoSuma [1..n] == 1 + sum [1..n]

1	menorNoSuma [1..n] == 1 + sum [1..n]

Soluciones

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

import Data.List (sort, subsequences)
import Test.QuickCheck
    
menorNoSuma1 :: [Integer] -> Integer
menorNoSuma1 xs =
  head [n | n <- [1..], n `notElem` sumas xs]

-- (sumas xs) es la lista de las sumas de los subconjuntos de xs. Por ejemplo,
--    sumas [1,2,6]  ==  [0,1,2,3,6,7,8,9]
--    sumas [6,1,2]  ==  [0,6,1,7,2,8,3,9]
sumas :: [Integer] -> [Integer]
sumas xs = map sum (subsequences xs)

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

menorNoSuma2 :: [Integer] -> Integer
menorNoSuma2  = menorNoSumaOrd . reverse . sort 

-- (menorNoSumaOrd xs) es el menor número que no se puede escribir como
-- suma de un subconjunto de xs, donde xs es una lista de números
-- naturales ordenada de mayor a menor. Por ejemplo,
--    menorNoSumaOrd [6,2,1]  ==  4
menorNoSumaOrd [] = 1
menorNoSumaOrd (x:xs) | x > y     = y
                      | otherwise = y+x
    where y = menorNoSumaOrd xs

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

--    λ> menorNoSuma1 [1..20]
--    211
--    (20.40 secs, 28,268,746,320 bytes)
--    λ> menorNoSuma2 [1..20]
--    211
--    (0.01 secs, 0 bytes)
           
-- Propiedad
-- =========

-- La propiedad es
prop_menorNoSuma :: (Positive Integer) -> Bool
prop_menorNoSuma (Positive n) =
    menorNoSuma2 [1..n] == 1 + sum [1..n]

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

-- 1ª definición

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

import Data.List (sort, subsequences)

import Test.QuickCheck

menorNoSuma1 :: [Integer] -> Integer

menorNoSuma1 xs =

head [n | n <- [1..], n `notElem` sumas xs]

-- (sumas xs) es la lista de las sumas de los subconjuntos de xs. Por ejemplo,

-- sumas [1,2,6] == [0,1,2,3,6,7,8,9]

-- sumas [6,1,2] == [0,6,1,7,2,8,3,9]

sumas :: [Integer] -> [Integer]

sumas xs = map sum (subsequences xs)

-- 2ª definición

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

menorNoSuma2 :: [Integer] -> Integer

menorNoSuma2 = menorNoSumaOrd . reverse . sort

-- (menorNoSumaOrd xs) es el menor número que no se puede escribir como

-- suma de un subconjunto de xs, donde xs es una lista de números

-- naturales ordenada de mayor a menor. Por ejemplo,

-- menorNoSumaOrd [6,2,1] == 4

menorNoSumaOrd [] = 1

menorNoSumaOrd (x:xs) | x > y = y

| otherwise = y+x

where y = menorNoSumaOrd xs

-- Comparación de eficiencia

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

-- λ> menorNoSuma1 [1..20]

-- 211

-- (20.40 secs, 28,268,746,320 bytes)

-- λ> menorNoSuma2 [1..20]

-- 211

-- (0.01 secs, 0 bytes)

-- Propiedad

-- =========

-- La propiedad es

prop_menorNoSuma :: (Positive Integer) -> Bool

prop_menorNoSuma (Positive n) =

menorNoSuma2 [1..n] == 1 + sum [1..n]

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=7}) prop_menorNoSuma

-- +++ OK, passed 100 tests.

El algoritmo binario del mcd

PorJosé A. Alonso 1-febrero-20168-febrero-2016

El máximo común divisor (mcd) de dos números enteros no negativos se puede calcular mediante un algoritmo binario basado en las siguientes propiedades:

Si a,b son pares, entonces mcd(a,b) = 2*mcd(a/2,b/2)
Si a es par y b impar, entonces mcd(a,b) = mcd(a/2,b)
Si a es impar y b par, entonces mcd(a,b) = mcd(a,b/2)
Si a y b son impares y a > b, entonces mcd(a,b) = mcd((a-b)/2,b)
Si a y b son impares y a < b, entonces mcd(a,b) = mcd(a,(b-a)/2)
mcd(a,0) = a
mcd(0,b) = b
mcd(a,a) = a

Por ejemplo, el cálculo del mcd(660,420) es

   mcd(660,420)
   = 2*mcd(330,210)    [por 1]
   = 2*2*mcd(165,105)  [por 1]
   = 2*2*mcd(30,105)   [por 4]
   = 2*2*mcd(15,105)   [por 2]
   = 2*2*mcd(15,45)    [por 4]
   = 2*2*mcd(15,15)    [por 4]
   = 2*2*15            [por 8]
   = 60

mcd(660,420)

= 2*mcd(330,210) [por 1]

= 2*2*mcd(165,105) [por 1]

= 2*2*mcd(30,105) [por 4]

= 2*2*mcd(15,105) [por 2]

= 2*2*mcd(15,45) [por 4]

= 2*2*mcd(15,15) [por 4]

= 2*2*15 [por 8]

= 60

Definir la función

   mcd :: Integer -> Integer -> Integer

1	mcd :: Integer -> Integer -> Integer

Definir la función

tal que (mcd a b) es el máximo común divisor de a y b calculado mediante el algoritmo binario del mcd. Por ejemplo,

   mcd 660 420  ==  60
   mcd 3 0      ==  3
   mcd 0 3      ==  3

mcd 660 420 == 60

mcd 3 0 == 3

mcd 0 3 == 3

Comprobar con QuickCheck que, para los enteros no negativos, las funciones mcd y gcd son equivalentes.

Soluciones

import Test.QuickCheck

mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd 0 b = b
mcd a b | a == b           = a
        | even a && even b = 2 * mcd (a `div` 2) (b `div` 2)
        | even a           = mcd (a `div` 2)     b
        | even b           = mcd a               (b `div` 2)
        | a > b            = mcd ((a-b) `div` 2) b
        | otherwise        = mcd a               ((b-a) `div` 2)

-- Propiedad de equivalencia 
prop_mcd :: Integer -> Integer -> Bool
prop_mcd a b = mcd a1 b1 == gcd a1 b1
    where a1 = abs a
          b1 = abs b

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

import Test.QuickCheck

mcd :: Integer -> Integer -> Integer

mcd a 0 = a

mcd 0 b = b

mcd a b | a == b = a

| even a && even b = 2 * mcd (a `div` 2) (b `div` 2)

| even a = mcd (a `div` 2) b

| even b = mcd a (b `div` 2)

| a > b = mcd ((a-b) `div` 2) b

| otherwise = mcd a ((b-a) `div` 2)

-- Propiedad de equivalencia

prop_mcd :: Integer -> Integer -> Bool

prop_mcd a b = mcd a1 b1 == gcd a1 b1

where a1 = abs a

b1 = abs b

-- La comprobación es

-- λ> quickCheck prop_mcd

-- +++ OK, passed 100 tests.

Conjunto de funciones

PorJosé A. Alonso 26-enero-20162-febrero-2016

Una función f entre dos conjuntos A e B se puede representar mediante una lista de pares de AxB tales que para cada elemento a de A existe un único elemento b de B tal que (a,b) pertenece a f. Por ejemplo,

[(1,2),(3,6)] es una función de [1,3] en [2,4,6];
[(1,2)] no es una función de [1,3] en [2,4,6], porque no tiene ningún par cuyo primer elemento sea igual a 3;
[(1,2),(3,6),(1,4)] no es una función porque hay dos pares distintos cuya primer elemento es 1.

Definir la función

   funciones :: [a] -> [a] -> [[(a,a)]]

1	funciones :: [a] -> [a] -> [[(a,a)]]

tal que (funciones xs ys) es el conjunto de las funciones de xs en ys. Por ejemplo,

   λ> funciones [] [2,4,6]
   [[]]
   λ> funciones [3] [2,4,6]
   [[(3,2)],[(3,4)],[(3,6)]]
   λ> funciones [1,3] [2,4,6]
   [[(1,2),(3,2)], [(1,2),(3,4)], [(1,2),(3,6)], [(1,4),(3,2)], [(1,4),(3,4)],
    [(1,4),(3,6)], [(1,6),(3,2)], [(1,6),(3,4)], [(1,6),(3,6)]]

λ> funciones [] [2,4,6]

[[]]

λ> funciones [3] [2,4,6]

[[(3,2)],[(3,4)],[(3,6)]]

λ> funciones [1,3] [2,4,6]

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

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

Comprobar con QuickCheck que si xs es un conjunto con n elementos e ys un conjunto con m elementos, entonces (funciones xs ys) tiene m^n elementos.

Nota. Al hacer la comprobación limitar el tamaño de las pruebas como se indica a continuación

   λ> quickCheckWith (stdArgs {maxSize=7}) prop_funciones
   +++ OK, passed 100 tests.

1 2	λ> quickCheckWith (stdArgs {maxSize=7}) prop_funciones +++ OK, passed 100 tests.

Soluciones

import Test.QuickCheck

funciones :: [a] -> [a] -> [[(a,a)]]
funciones [] _      = [[]]
funciones (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]
    where fs = funciones xs ys

prop_funciones :: [Int] -> [Int] -> Bool
prop_funciones xs ys =
    length (funciones xs ys) == (length ys)^(length xs)

import Test.QuickCheck

funciones :: [a] -> [a] -> [[(a,a)]]

funciones [] _ = [[]]

funciones (x:xs) ys = [((x,y):f) | y <- ys, f <- fs]

where fs = funciones xs ys

prop_funciones :: [Int] -> [Int] -> Bool

prop_funciones xs ys =

length (funciones xs ys) == (length ys)^(length xs)

Los números de Armstrong

PorJosé A. Alonso 3-diciembre-201510-diciembre-2015

Un número de n dígitos es un número de Armstrong si es igual a la suma de las n-ésimas potencias de sus dígitos. Por ejemplo, 371, 8208 y 4210818 son números de Armstrong ya que

       371 = 3^3 + 7 + 1³ y  
      8208 = 8^4 + 2^4 + 0^4 + 8^4 
   4210818 = 4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7

371 = 3^3 + 7 + 1³ y

8208 = 8^4 + 2^4 + 0^4 + 8^4

4210818 = 4^7 + 2^7 + 1^7 + 0^7 + 8^7 + 1^7 + 8^7

Definir las funciones

   esArmstrong :: Integer -> Bool
   armstrong   :: [Integer]

1 2	esArmstrong :: Integer -> Bool armstrong :: [Integer]

tales que

(esArmstrong x) se verifica si x es un número de Armstrong. Por ejemplo,

     esArmstrong 371                                      ==  True
     esArmstrong 8208                                     ==  True
     esArmstrong 4210818                                  ==  True
     esArmstrong 2015                                     ==  False
     esArmstrong 115132219018763992565095597973971522401  ==  True
     esArmstrong 115132219018763992565095597973971522402  ==  False

esArmstrong 371 == True

esArmstrong 8208 == True

esArmstrong 4210818 == True

esArmstrong 2015 == False

esArmstrong 115132219018763992565095597973971522401 == True

esArmstrong 115132219018763992565095597973971522402 == False

armstrong es la lista cuyos elementos son los números de Armstrong. Por ejemplo,

     λ> take 18 armstrong
     [1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727]

1 2	λ> take 18 armstrong [1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727]

Comprobar con QuickCheck que los números mayores que
115132219018763992565095597973971522401 no son números de Armstrong.

Soluciones

import Test.QuickCheck

esArmstrong :: Integer -> Bool
esArmstrong x = 
    x == sum [d^n | d <- digitos x]
    where n = length (show x)

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

armstrong :: [Integer]
armstrong = [n | n <- [1..], esArmstrong n]

-- La propiedad es
prop_Armstrong :: Integer -> Bool
prop_Armstrong n =
    not (esArmstrong (115132219018763992565095597973971522401 + abs n + 1))

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

import Test.QuickCheck

esArmstrong :: Integer -> Bool

esArmstrong x =

x == sum [d^n | d <- digitos x]

where n = length (show x)

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

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

digitos :: Integer -> [Integer]

digitos x = [read [d] | d <- show x]

armstrong :: [Integer]

armstrong = [n | n <- [1..], esArmstrong n]

-- La propiedad es

prop_Armstrong :: Integer -> Bool

prop_Armstrong n =

not (esArmstrong (115132219018763992565095597973971522401 + abs n + 1))

-- La comprobación es

-- λ> quickCheck prop_Armstrong

-- +++ OK, passed 100 tests.

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Referencias

Soluciones

Referencias

Soluciones

Referencias

Soluciones

Soluciones

Soluciones en Maxima

Soluciones

Solución en Maxima

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico