José A. Alonso

Caminos reducidos

PorJosé A. Alonso 21-abril-201525-abril-2021

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

   data Direccion = N | S | E | O deriving (Show, Eq)
   type Camino = [Direccion]

1 2	data Direccion = N \| S \| E \| O deriving (Show, Eq) type Camino = [Direccion]

Definir la función

   reducido :: Camino -> Camino

1	reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

   reducido []                              ==  []
   reducido [N]                             ==  [N]
   reducido [N,O]                           ==  [N,O]
   reducido [N,O,E]                         ==  [N]
   reducido [N,O,E,S]                       ==  [] 
   reducido [N,O,S,E]                       ==  [N,O,S,E]
   reducido [N,S,S,E,O,N]                   ==  []
   reducido [N,S,S,E,O,N,O]                 ==  [O]
   reducido (take (10^7) (cycle [N,E,O,S])) ==  []

reducido [] == []

reducido [N] == [N]

reducido [N,O] == [N,O]

reducido [N,O,E] == [N]

reducido [N,O,E,S] == []

reducido [N,O,S,E] == [N,O,S,E]

reducido [N,S,S,E,O,N] == []

reducido [N,S,S,E,O,N,O] == [O]

reducido (take (10^7) (cycle [N,E,O,S])) == []

Nótese que en el penúltimo ejemplo las reducciones son

       [N,S,S,E,O,N,O]  
   --> [S,E,O,N,O]  
   --> [S,N,O]  
   --> [O]

[N,S,S,E,O,N,O]

--> [S,E,O,N,O]

--> [S,N,O]

--> [O]

Soluciones

data Direccion = N | S | E | O deriving (Show, Eq)

type Camino = [Direccion]

-- 1ª solución (por recursión):
reducido1 :: Camino -> Camino
reducido1 [] = []
reducido1 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido1 ds

opuesta :: Direccion -> Direccion
opuesta N = S
opuesta S = N
opuesta E = O
opuesta O = E

-- 2ª solución (por plegado)
reducido2 :: Camino -> Camino
reducido2 = foldr aux []
    where aux N (S:xs) = xs
          aux S (N:xs) = xs
          aux E (O:xs) = xs
          aux O (E:xs) = xs
          aux x xs     = x:xs

-- 3ª solución 
reducido3 :: Camino -> Camino
reducido3 []       = []
reducido3 (N:S:ds) = reducido3 ds
reducido3 (S:N:ds) = reducido3 ds
reducido3 (E:O:ds) = reducido3 ds
reducido3 (O:E:ds) = reducido3 ds
reducido3 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido3 ds

-- 4ª solución
reducido4 :: Camino -> Camino
reducido4 ds = reverse (aux ([],ds)) where 
    aux (N:xs, S:ys) = aux (xs,ys)
    aux (S:xs, N:ys) = aux (xs,ys)
    aux (E:xs, O:ys) = aux (xs,ys)
    aux (O:xs, E:ys) = aux (xs,ys)
    aux (  xs, y:ys) = aux (y:xs,ys)
    aux (  xs,   []) = xs

-- Comparación de eficiencia
--    ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (3.87 secs, 460160736 bytes)
--    ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (1.16 secs, 216582880 bytes)
--    ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.58 secs, 98561872 bytes)
--    ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.64 secs, 176154640 bytes)
--    
--    ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (5.43 secs, 962694784 bytes)
--    ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (9.29 secs, 1722601528 bytes)
-- 
--    ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (4.52 secs, 547004960 bytes)
--    ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (2.17 secs, 379049224 bytes)
--    
--    ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)
--    []
--    (7.35 secs, 537797096 bytes)
--    ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)
--    []
--    (2.30 secs, 244553404 bytes)
--    ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)
--    []
--    (8.08 secs, 545043608 bytes)
--    ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)
--    []
--    (1.96 secs, 205552240 bytes)

data Direccion = N | S | E | O deriving (Show, Eq)

type Camino = [Direccion]

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

reducido1 :: Camino -> Camino

reducido1 [] = []

reducido1 (d:ds) | null ds' = [d]

| d == opuesta (head ds') = tail ds'

| otherwise = d:ds'

where ds' = reducido1 ds

opuesta :: Direccion -> Direccion

opuesta N = S

opuesta S = N

opuesta E = O

opuesta O = E

-- 2ª solución (por plegado)

reducido2 :: Camino -> Camino

reducido2 = foldr aux []

where aux N (S:xs) = xs

aux S (N:xs) = xs

aux E (O:xs) = xs

aux O (E:xs) = xs

aux x xs = x:xs

-- 3ª solución

reducido3 :: Camino -> Camino

reducido3 [] = []

reducido3 (N:S:ds) = reducido3 ds

reducido3 (S:N:ds) = reducido3 ds

reducido3 (E:O:ds) = reducido3 ds

reducido3 (O:E:ds) = reducido3 ds

reducido3 (d:ds) | null ds' = [d]

| d == opuesta (head ds') = tail ds'

| otherwise = d:ds'

where ds' = reducido3 ds

-- 4ª solución

reducido4 :: Camino -> Camino

reducido4 ds = reverse (aux ([],ds)) where

aux (N:xs, S:ys) = aux (xs,ys)

aux (S:xs, N:ys) = aux (xs,ys)

aux (E:xs, O:ys) = aux (xs,ys)

aux (O:xs, E:ys) = aux (xs,ys)

aux ( xs, y:ys) = aux (y:xs,ys)

aux ( xs, []) = xs

-- Comparación de eficiencia

-- ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (3.87 secs, 460160736 bytes)

-- ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (1.16 secs, 216582880 bytes)

-- ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (0.58 secs, 98561872 bytes)

-- ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (0.64 secs, 176154640 bytes)

-- ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))

-- []

-- (5.43 secs, 962694784 bytes)

-- ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))

-- []

-- (9.29 secs, 1722601528 bytes)

-- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])

-- 400002

-- (4.52 secs, 547004960 bytes)

-- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])

-- 400002

-- (2.17 secs, 379049224 bytes)

-- ghci> let n=10^6 in reducido1 (replicate n N ++ replicate n S)

-- []

-- (7.35 secs, 537797096 bytes)

-- ghci> let n=10^6 in reducido2 (replicate n N ++ replicate n S)

-- []

-- (2.30 secs, 244553404 bytes)

-- ghci> let n=10^6 in reducido3 (replicate n N ++ replicate n S)

-- []

-- (8.08 secs, 545043608 bytes)

-- ghci> let n=10^6 in reducido4 (replicate n N ++ replicate n S)

-- []

-- (1.96 secs, 205552240 bytes)

Con mínimo común denominador

PorJosé A. Alonso 20-abril-201527-abril-2015

Los números racionales se pueden representar como pares de enteros:

   type Racional a = (a,a)

1	type Racional a = (a,a)

Definir la función

   reducida :: Integral a => [Racional a] -> [Racional a]

1	reducida :: Integral a => [Racional a] -> [Racional a]

tal que (reducida xs) es la lista de los números racionales donde cada uno es igual al correspondiente elemento de xs y el denominador de todos los elementos de (reducida xs) es el menor número que cumple dicha condición; es decir, si xs es la lista

   [(x_1, y_1), ..., (x_n, y_n)]

1	[(x_1, y_1), ..., (x_n, y_n)]

entonces (reducida xs) es

   [(z_1, d), ..., (z_n, d)]

1	[(z_1, d), ..., (z_n, d)]

tales que

   z_1/d = x_1/y_1, ..., z_n/d = x_n/y_n

1	z_1/d = x_1/y_1, ..., z_n/d = x_n/y_n

y d es el menor posible. Por ejemplo,

   reducida [(1,2),(1,3),(1,4)]  ==  [(6,12),(4,12),(3,12)]
   reducida [(1,2),(1,3),(6,4)]  ==  [(3,6),(2,6),(9,6)]
   reducida [(-7,6),(-10,-8)]    ==  [(-14,12),(15,12)]
   reducida [(8,12)]             ==  [(2,3)]

reducida [(1,2),(1,3),(1,4)] == [(6,12),(4,12),(3,12)]

reducida [(1,2),(1,3),(6,4)] == [(3,6),(2,6),(9,6)]

reducida [(-7,6),(-10,-8)] == [(-14,12),(15,12)]

reducida [(8,12)] == [(2,3)]

Soluciones

type Racional a = (a,a) 

reducida :: Integral a => [Racional a] -> [Racional a]
reducida xs = 
    [(x * (m `div` y), m) | (x,y) <- ys]
    where ys = map fraccionReducida xs
          m  = mcm [y | (_,y) <- ys]

-- (fraccionReducida r) es el número racional igual a r con menor
-- denominador positivo. Por ejemplo,
--    fraccionReducida ( 6, 10)  ==  ( 3,5)
--    fraccionReducida (-6, 10)  ==  (-3,5)
--    fraccionReducida ( 6,-10)  ==  (-3,5)
--    fraccionReducida (-6,-10)  ==  ( 3,5)
--    fraccionReducida ( 3,  5)  ==  ( 3,5)
fraccionReducida :: Integral a => (a,a) -> (a,a)
fraccionReducida (x,y) =
    (s * x1 `div` m, y1 `div` m)
    where s  = signum x * signum y      
          x1 = abs x
          y1 = abs y
          m  = gcd x1 y1
          
-- (mcm xs) es el mínimo común múltiplo de xs. Por ejemplo,
--    mcm [2,6,10]  ==  30
mcm :: Integral a => [a] -> a
mcm = foldl lcm 1

type Racional a = (a,a)

reducida :: Integral a => [Racional a] -> [Racional a]

reducida xs =

[(x * (m `div` y), m) | (x,y) <- ys]

where ys = map fraccionReducida xs

m = mcm [y | (_,y) <- ys]

-- (fraccionReducida r) es el número racional igual a r con menor

-- denominador positivo. Por ejemplo,

-- fraccionReducida ( 6, 10) == ( 3,5)

-- fraccionReducida (-6, 10) == (-3,5)

-- fraccionReducida ( 6,-10) == (-3,5)

-- fraccionReducida (-6,-10) == ( 3,5)

-- fraccionReducida ( 3, 5) == ( 3,5)

fraccionReducida :: Integral a => (a,a) -> (a,a)

fraccionReducida (x,y) =

(s * x1 `div` m, y1 `div` m)

where s = signum x * signum y

x1 = abs x

y1 = abs y

m = gcd x1 y1

-- (mcm xs) es el mínimo común múltiplo de xs. Por ejemplo,

-- mcm [2,6,10] == 30

mcm :: Integral a => [a] -> a

mcm = foldl lcm 1

Primos hereditarios

PorJosé A. Alonso 16-abril-20151-mayo-2016

Un número primo es hereditario si todos los números obtenidos eliminando dígitos por la derecha o por la izquierda son primos. Por ejemplo, 3797 es hereditario ya que los números obtenidos eliminando dígitos por la derecha son 3797, 379, 37 y 3 y los obtenidos eliminando dígitos por la izquierda son 3797, 797, 97 y 7 y todos ellos son primos.

Definir la sucesión

   hereditarios :: [Integer]

1	hereditarios :: [Integer]

cuyos elementos son los números hereditarios. Por ejemplo,

   ghci> take 15 hereditarios
   [2,3,5,7,23,37,53,73,313,317,373,797,3137,3797,739397]

1 2	ghci> take 15 hereditarios [2,3,5,7,23,37,53,73,313,317,373,797,3137,3797,739397]

Soluciones

import Data.List (inits, tails)
import Data.Char (digitToInt)
import Data.Numbers.Primes (primes, isPrime)

hereditarios :: [Integer]
hereditarios = [n | n <- primes, hereditario n]

hereditario :: Integer -> Bool
hereditario n = 
    all odd (map digitToInt (tail ds)) &&
    all isPrime (map read (tail (inits ds))) &&
    all isPrime (map read (init (tails ds)))
    where ds = show n

import Data.List (inits, tails)

import Data.Char (digitToInt)

import Data.Numbers.Primes (primes, isPrime)

hereditarios :: [Integer]

hereditarios = [n | n <- primes, hereditario n]

hereditario :: Integer -> Bool

hereditario n =

all odd (map digitToInt (tail ds)) &&

all isPrime (map read (tail (inits ds))) &&

all isPrime (map read (init (tails ds)))

where ds = show n

Constante de Champernowne

PorJosé A. Alonso 15-abril-201525-marzo-2022

La constante de Champernowne es el número irracional

   0.12345678910111213141516171819202122232425262728293031323334 ...

1	0.12345678910111213141516171819202122232425262728293031323334 ...

cuya parte entera es 0 y la parte decimal se obtiene concatenado los números naturales a partir de 1.

Definir la función

   productoChampernowne :: [Int] -> Int

1	productoChampernowne :: [Int] -> Int

tal que (productoChampernowne ns) es el producto de los dígitos de la constante de Champernowne que ocupan las posiciones ns. Por ejemplo,

   productoChampernowne [0,1,2]                 ==  6
   productoChampernowne [8,20]                  ==  45
   productoChampernowne [10^i-1 | i <- [0..7]]  ==  1470

productoChampernowne [0,1,2] == 6

productoChampernowne [8,20] == 45

productoChampernowne [10^i-1 | i <- [0..7]] == 1470

Soluciones

import Data.Char (digitToInt)

productoChampernowne :: [Int] -> Int
productoChampernowne ns = product [champernowne !! n | n <- ns] 

-- champernowne  es la sucesión de champernowne. Por ejemplo,
--    ghci> take 20 champernowne
--    [1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,1,3,1,4,1]
champernowne :: [Int] 
champernowne = map digitToInt (concatMap show [1..])

import Data.Char (digitToInt)

productoChampernowne :: [Int] -> Int

productoChampernowne ns = product [champernowne !! n | n <- ns]

-- champernowne es la sucesión de champernowne. Por ejemplo,

-- ghci> take 20 champernowne

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

champernowne :: [Int]

champernowne = map digitToInt (concatMap show [1..])

Casas con números equilibrados

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

Continuando con los problema propuestos por alumnos, el de hoy es el propuesto por Rafael Jiménez.

Se tiene una calle en la que las casas sólo están en un lado de ésta y las casas están numeradas de 1 hasta n, donde n es el número total de casas en la calle. Se dice que el número de una casa es equilibrado si y solamente si la suma de los números de las casas anteriores es igual a la suma de los números posteriores a la casa. Por ejemplo, el número de la 6ª casa, en una calle con 8 casas, es equilibrado ya que

   1 + 2 + 3 + 4 + 5 = 7 + 8

1	1 + 2 + 3 + 4 + 5 = 7 + 8

Definir la función

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

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

tal que (soluciones x y) es la lista de pares (a,n) tales que a es el número equilibrado de una casa en una calle con n casas y n está entre x e y. Por ejemplo,

   soluciones 1 500          ==  [(1,1),(6,8),(35,49),(204,288)]
   soluciones 1000 3000      ==  [(1189,1681)]
   soluciones (10^5) (10^6)  ==  [(235416,332928)]
   soluciones (10^6) (10^7)  ==  [(1372105,1940449)]
   (fst $ head $ soluciones (10^100) (10^101))  `mod` (10^9)  ==  763728460
   (fst $ head $ soluciones (10^800) (10^1000)) `mod` (10^9)  ==  311156546

soluciones 1 500 == [(1,1),(6,8),(35,49),(204,288)]

soluciones 1000 3000 == [(1189,1681)]

soluciones (10^5) (10^6) == [(235416,332928)]

soluciones (10^6) (10^7) == [(1372105,1940449)]

(fst $ head $ soluciones (10^100) (10^101)) `mod` (10^9) == 763728460

(fst $ head $ soluciones (10^800) (10^1000)) `mod` (10^9) == 311156546

Soluciones

import Test.QuickCheck

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

soluciones1 :: Integer -> Integer -> [(Integer,Integer)]
soluciones1 x y =
    [(n,n+m) | n <- [x..y], m <- [0..y-n], 
               sum [1..n-1] == sum [n+1..n+m]]
               
-- 2ª solución
-- ===========

soluciones2 :: Integer -> Integer -> [(Integer,Integer)]
soluciones2 x y =
    [(n,n+m) | n <- [x..y], m <- [0..y-n], 
               esSolucion (n,n+m)]

esSolucion :: (Integer,Integer) -> Bool
esSolucion (n,m) = suma (n-1) == suma m - suma n
    where suma n = n*(n+1) `div` 2
    
-- 3ª solución
-- ===========

-- Con las definiciones anteriores se pueden calcular los cuatro
-- primeros números de las casas equilibradas:
--    ghci> map fst (soluciones2 1 500)
--    [1,6,35,204]
-- Conjeturando que el n-ésimo número p(n) se calcula mediante una
-- recurrencia del tipo p(n) = x*p(n-1) + y*p(n-2) se tiene   
--    p(1) =   1
--    p(2) =   6
--    p(3) =  35 =  6x +  y
--    p(4) = 204 = 35x + 6y
-- al resolverlo se obtiene x = 6 e y = -1. Por tanto,
--    p(1) = 1
--    p(2) = 6
--    p(n) = 6*p(n-1) - p(n-2)
--
-- Haciendo lo mismo con las segundas componentes, 
--    ghci> map snd (soluciones2 1 2000)
--    [1,8,49,288,1681]
-- Conjeturando que el n-ésimo número s(n) se calcula mediante una
-- recurrencia del tipo s(n) = x*s(n-1) + y*s(n-2) + z se tiene   
--    s(1) =    1
--    s(2) =    8
--    s(3) =   49 =   8x +   y + z
--    s(4) =  288 =  49x +  8y + z
--    s(5) = 1681 = 288x + 49y + z 
-- al resolverlo se obtiene x = 6, y = -1, z = 2. Por tanto,
--    s(1) = 1
--    s(2) = 8
--    s(n) = 6*s(n-1) - s(n-2) + 2

-- El número de la n-ésimo casa equilibrada, p(n), se puede calcular por
-- recursión: 
casa :: Integer -> Integer
casa 1 = 1
casa 2 = 6
casa n = 6 * (casa (n-1)) - (casa (n-2))

-- La sucesión de los números de las casas equilibradas se puede
-- calcular por programación dinámica:
casas :: [Integer]
casas = 
    1 : 6 : zipWith (\x y -> 6*x-y) (tail casas) casas

-- El número de casas en la n-ésima calle con casas equilibradas, s(n),
-- se puede calcular por recursión: 
calle :: Integer -> Integer
calle 1 = 1
calle 2 = 8
calle n = 6 * (calle (n-1)) - (calle (n-2)) + 2

-- La sucesión de los números de las casas equilibradas se puede
-- calcular por programación dinámica:
calles :: [Integer]
calles = 
    1 : 8 : zipWith (\x y -> 6*x-y+2) (tail calles) calles

-- Usando casas se obtiene la 3ª solución:
soluciones3 :: Integer -> Integer -> [(Integer,Integer)]
soluciones3 x y =
   takeWhile (<=(y,y)) (dropWhile (<(x,x)) (zip casas calles))

-- Comprobación de soluciones
-- ==========================

-- La propiedad es
prop_soluciones :: Integer -> Integer -> Property
prop_soluciones x y =
    0 < x && x <= y ==>
    all esSolucion (soluciones3 x y)

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

-- Comparación de eficiencia:
--    ghci> soluciones1 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (337.30 secs, 396493594456 bytes)
--    ghci> soluciones2 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (23.47 secs, 3859436176 bytes)
--    ghci> soluciones3 1 2000
--    [(1,1),(6,8),(35,49),(204,288),(1189,1681)]
--    (0.01 secs, 1029592 bytes)

100

101

102

103

104

105

106

107

108

109

import Test.QuickCheck

-- 1ª solución

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

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

soluciones1 x y =

[(n,n+m) | n <- [x..y], m <- [0..y-n],

sum [1..n-1] == sum [n+1..n+m]]

-- 2ª solución

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

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

soluciones2 x y =

[(n,n+m) | n <- [x..y], m <- [0..y-n],

esSolucion (n,n+m)]

esSolucion :: (Integer,Integer) -> Bool

esSolucion (n,m) = suma (n-1) == suma m - suma n

where suma n = n*(n+1) `div` 2

-- 3ª solución

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

-- Con las definiciones anteriores se pueden calcular los cuatro

-- primeros números de las casas equilibradas:

-- ghci> map fst (soluciones2 1 500)

-- [1,6,35,204]

-- Conjeturando que el n-ésimo número p(n) se calcula mediante una

-- recurrencia del tipo p(n) = x*p(n-1) + y*p(n-2) se tiene

-- p(1) = 1

-- p(2) = 6

-- p(3) = 35 = 6x + y

-- p(4) = 204 = 35x + 6y

-- al resolverlo se obtiene x = 6 e y = -1. Por tanto,

-- p(1) = 1

-- p(2) = 6

-- p(n) = 6*p(n-1) - p(n-2)

-- Haciendo lo mismo con las segundas componentes,

-- ghci> map snd (soluciones2 1 2000)

-- [1,8,49,288,1681]

-- Conjeturando que el n-ésimo número s(n) se calcula mediante una

-- recurrencia del tipo s(n) = x*s(n-1) + y*s(n-2) + z se tiene

-- s(1) = 1

-- s(2) = 8

-- s(3) = 49 = 8x + y + z

-- s(4) = 288 = 49x + 8y + z

-- s(5) = 1681 = 288x + 49y + z

-- al resolverlo se obtiene x = 6, y = -1, z = 2. Por tanto,

-- s(1) = 1

-- s(2) = 8

-- s(n) = 6*s(n-1) - s(n-2) + 2

-- El número de la n-ésimo casa equilibrada, p(n), se puede calcular por

-- recursión:

casa :: Integer -> Integer

casa 1 = 1

casa 2 = 6

casa n = 6 * (casa (n-1)) - (casa (n-2))

-- La sucesión de los números de las casas equilibradas se puede

-- calcular por programación dinámica:

casas :: [Integer]

casas =

1 : 6 : zipWith (\x y -> 6*x-y) (tail casas) casas

-- El número de casas en la n-ésima calle con casas equilibradas, s(n),

-- se puede calcular por recursión:

calle :: Integer -> Integer

calle 1 = 1

calle 2 = 8

calle n = 6 * (calle (n-1)) - (calle (n-2)) + 2

-- La sucesión de los números de las casas equilibradas se puede

-- calcular por programación dinámica:

calles :: [Integer]

calles =

1 : 8 : zipWith (\x y -> 6*x-y+2) (tail calles) calles

-- Usando casas se obtiene la 3ª solución:

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

soluciones3 x y =

takeWhile (<=(y,y)) (dropWhile (<(x,x)) (zip casas calles))

-- Comprobación de soluciones

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

-- La propiedad es

prop_soluciones :: Integer -> Integer -> Property

prop_soluciones x y =

0 < x && x <= y ==>

all esSolucion (soluciones3 x y)

-- La comprobación es

-- ghci> quickCheck prop_soluciones

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia:

-- ghci> soluciones1 1 2000

-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]

-- (337.30 secs, 396493594456 bytes)

-- ghci> soluciones2 1 2000

-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]

-- (23.47 secs, 3859436176 bytes)

-- ghci> soluciones3 1 2000

-- [(1,1),(6,8),(35,49),(204,288),(1189,1681)]

-- (0.01 secs, 1029592 bytes)

Autor: José A. Alonso

Caminos reducidos

Soluciones

Con mínimo común denominador

Soluciones

Primos hereditarios

Soluciones

Constante de Champernowne

Soluciones

Casas con números equilibrados

Soluciones

Entradas recientes

Buscar

Correo electrónico