marzo 2021 – Página 2

Mínimo número de divisiones para igualar

PorJosé A. Alonso 24-marzo-202131-marzo-2021

El mínimo número de divisiones por 2, 3 ó 5 que hay que realizar igualar 15 y 20 es 6. En efecto, 15 se reduce a 5 dividiéndolo por 3 y 20 se reduce a 5 diviéndolo dos veces por 2.

Definir la función

   minimoNumeroDivisiones :: Integer -> Integer -> Maybe Int

1	minimoNumeroDivisiones :: Integer -> Integer -> Maybe Int

tal que (minimoNumeroDivisiones x y) es justamente el mínimo número de divisiones por 2, 3 ó 5 que hay que realizar para igualar x e y, o Nothing si no se pueden igualar. Por ejemplo,

   minimoNumeroDivisiones 15 20       ==  Just 3
   minimoNumeroDivisiones 15 15       ==  Just 0
   minimoNumeroDivisiones 15 16       ==  Just 6
   minimoNumeroDivisiones 15 17       ==  Nothing
   minimoNumeroDivisiones (10^99) 21  ==  Nothing

minimoNumeroDivisiones 15 20 == Just 3

minimoNumeroDivisiones 15 15 == Just 0

minimoNumeroDivisiones 15 16 == Just 6

minimoNumeroDivisiones 15 17 == Nothing

minimoNumeroDivisiones (10^99) 21 == Nothing

Soluciones

import Data.List (group, intersect, nub, sort)
import Data.Maybe (fromJust, isNothing, listToMaybe)
import Data.Numbers.Primes (primeFactors)
import Data.Tree (Tree (Node), flatten, levels)
import Test.QuickCheck (Property, (==>), quickCheck)

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

minimoNumeroDivisiones :: Integer -> Integer -> Maybe Int
minimoNumeroDivisiones x y
  | isNothing a = Nothing
  | otherwise   = Just (fst (fromJust a))
  where a = minimoNumeroDivisionesAux x y

-- La definición anterior se puede simplificar
minimoNumeroDivisiones' :: Integer -> Integer -> Maybe Int
minimoNumeroDivisiones' x y =
  Just fst <*> minimoNumeroDivisionesAux x y

-- (minimoNumeroDivisiones x y) es justamente el par formado por el
-- mínimo número de divisiones por 2, 3 ó 5 que hay que realizar para
-- igualar x e y junto con el número al que se reducen, o Nothing si no
-- se pueden igualar. Por ejemplo,
--    minimoNumeroDivisionesAux 15 20  ==  Just (3,5)
--    minimoNumeroDivisionesAux 15 15  ==  Just (0,15)
--    minimoNumeroDivisionesAux 15 16  ==  Just (6,1)
--    minimoNumeroDivisionesAux 15 17  ==  Nothing
minimoNumeroDivisionesAux :: Integer -> Integer -> Maybe (Int,Integer)
minimoNumeroDivisionesAux x y
  | null as   = Nothing
  | otherwise = Just (head as)
  where as = sort [(m+n,z) | (z,(m,n)) <- minimasProfundidadesComunes x y]

-- La definición anterior se puede simplificar
minimoNumeroDivisionesAux2 :: Integer -> Integer -> Maybe (Int,Integer)
minimoNumeroDivisionesAux2 x y =
  listToMaybe (sort [(m+n,z) | (z,(m,n)) <- minimasProfundidadesComunes x y])

-- (arbolDivisiones x) es el árbol de las divisiones enteras de x entre
-- 2, 3 ó 5. Por ejemplo,
--    λ> putStrLn (drawTree (fmap show (arbolDivisiones 30)))
--    30
--    |
--    +- 15
--    |  |
--    |  +- 5
--    |  |  |
--    |  |  `- 1
--    |  |
--    |  `- 3
--    |     |
--    |     `- 1
--    |
--    +- 10
--    |  |
--    |  +- 5
--    |  |  |
--    |  |  `- 1
--    |  |
--    |  `- 2
--    |     |
--    |     `- 1
--    |
--    `- 6
--       |
--       +- 3
--       |  |
--       |  `- 1
--       |
--       `- 2
--          |
--          `- 1
arbolDivisiones :: Integer -> Tree Integer
arbolDivisiones x =
  Node x (map arbolDivisiones (divisiones x))

-- (divisiones x) es la lista de las divisiones enteras de x entre 2, 3
-- y 5. Por ejemplo,
--    divisiones 30  ==  [15,10,6]
--    divisiones 15  ==  [5,3]
divisiones :: Integer -> [Integer]
divisiones x =
  [x `div` y | y <- [2,3,5], x `mod` y == 0]

-- (nodos a) es el conjunto de nodos del árbol a. Por ejemplo,
--    nodos (Node 2 [Node 2 [], Node 5 []])  ==  [2,5]
--    nodos (arbolDivisiones 30)  ==  [30,15,5,1,3,10,2,6]
nodos :: Tree Integer -> [Integer]
nodos = nub . flatten

-- (divisionesComunes x y) es la lista de los nodos comunes de los
-- árboles de las divisiones de x e y entre 2, 3 ó 5. Por ejemplo,
--    divisionesComunes 15 20  ==  [5,1]
divisionesComunes :: Integer -> Integer -> [Integer]
divisionesComunes x y =
  nodos (arbolDivisiones x) `intersect` nodos (arbolDivisiones y)

-- (minimaProfundidad x ns) es justamente la mínima produndidad
-- donde aparece x en el árbol ns, si aparece y Nothing, en caso
-- contrario. Por ejemplo,minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int
--    λ> minimaProfundidad 3 (Node 1 [Node 6 [],Node 3 [Node 1 []]])
--    Just 1
--    λ> minimaProfundidad 4 (Node 1 [Node 6 [],Node 3 [Node 1 []]])
--    Nothing
minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int
minimaProfundidad x ns =
  listToMaybe [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys]

-- (minimasProfundidadesComunes x e y) es la lista de pares formadas por
-- los nodos comunes de los árboles de las divisiones de x e y entre 2,
-- 3 ó 5 junto con las mínimas profundidades en cada uno de los
-- árboles. Por ejemplo,
--    minimasProfundidadesComunes 15 20  ==  [(5,(1,2)),(1,(2,3))]
--    minimasProfundidadesComunes 15 22  ==  []
minimasProfundidadesComunes :: Integer -> Integer -> [(Integer,(Int,Int))]
minimasProfundidadesComunes x1 x2 =
  [(c,(fromJust (minimaProfundidad c a1), fromJust (minimaProfundidad c a2)))
  | c <- cs]
  where a1 = arbolDivisiones x1
        a2 = arbolDivisiones x2
        cs = divisionesComunes x1 x2

-- Propiedad
-- =========

-- El mínimo número de divisiones se alcanza en el máximo común divisor.
prop_minimoNumeroDivisiones :: Integer -> Integer -> Property
prop_minimoNumeroDivisiones x y =
  x > 0 && y > 0 ==>
  isNothing a || snd (fromJust a) == gcd x y
  where a = minimoNumeroDivisionesAux x y

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

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

minimoNumeroDivisiones2 :: Integer -> Integer -> Maybe Int
minimoNumeroDivisiones2 x y
  | as' == bs' = Just (sum [abs (a - b) | (a,b) <- zip as bs])
  | otherwise  = Nothing
  where (as,as') = factorizacion x
        (bs,bs') = factorizacion y

-- (factorización n) es la lista de pares cuya primera componente es la
-- lista de los exponentes de 2, 3 y 5 en la factorización de n y la
-- segunda esla lista delos restantes divisores primos. Por ejemplo,
--    factorizacion 15   ==  ([0,1,1],[])
--    factorizacion 20   ==  ([2,0,1],[])
--    factorizacion 17   ==  ([0,0,0],[17])
--    factorizacion 147  ==  ([0,1,0],[7,7])
factorizacion :: Integer -> ([Int],[Integer])
factorizacion n =
  (map length [bs,cs,ds], es)
  where as = primeFactors n
        (bs,bs') = span (==2) as
        (cs,cs') = span (==3) bs'
        (ds,es)  = span (==5) cs'

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

-- La propies de la equivalencia de las dos definiciones es
prop_equivalencia :: Integer -> Integer -> Property
prop_equivalencia x y =
  x > 0 && y > 0 ==>
  minimoNumeroDivisiones x y == minimoNumeroDivisiones2 x y

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

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

--    λ> minimoNumeroDivisiones (10^11) (3^10*7)
--    Nothing
--    (6.08 secs, 2,725,931,872 bytes)
--    λ> minimoNumeroDivisiones2(10^11) (3^10*7)
--    Nothing
--    (0.01 secs, 128,944 bytes)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

import Data.List (group, intersect, nub, sort)

import Data.Maybe (fromJust, isNothing, listToMaybe)

import Data.Numbers.Primes (primeFactors)

import Data.Tree (Tree (Node), flatten, levels)

import Test.QuickCheck (Property, (==>), quickCheck)

-- 1ª solución

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

minimoNumeroDivisiones :: Integer -> Integer -> Maybe Int

minimoNumeroDivisiones x y

| isNothing a = Nothing

| otherwise = Just (fst (fromJust a))

where a = minimoNumeroDivisionesAux x y

-- La definición anterior se puede simplificar

minimoNumeroDivisiones' :: Integer -> Integer -> Maybe Int

minimoNumeroDivisiones' x y =

Just fst <*> minimoNumeroDivisionesAux x y

-- (minimoNumeroDivisiones x y) es justamente el par formado por el

-- mínimo número de divisiones por 2, 3 ó 5 que hay que realizar para

-- igualar x e y junto con el número al que se reducen, o Nothing si no

-- se pueden igualar. Por ejemplo,

-- minimoNumeroDivisionesAux 15 20 == Just (3,5)

-- minimoNumeroDivisionesAux 15 15 == Just (0,15)

-- minimoNumeroDivisionesAux 15 16 == Just (6,1)

-- minimoNumeroDivisionesAux 15 17 == Nothing

minimoNumeroDivisionesAux :: Integer -> Integer -> Maybe (Int,Integer)

minimoNumeroDivisionesAux x y

| null as = Nothing

| otherwise = Just (head as)

where as = sort [(m+n,z) | (z,(m,n)) <- minimasProfundidadesComunes x y]

-- La definición anterior se puede simplificar

minimoNumeroDivisionesAux2 :: Integer -> Integer -> Maybe (Int,Integer)

minimoNumeroDivisionesAux2 x y =

listToMaybe (sort [(m+n,z) | (z,(m,n)) <- minimasProfundidadesComunes x y])

-- (arbolDivisiones x) es el árbol de las divisiones enteras de x entre

-- 2, 3 ó 5. Por ejemplo,

-- λ> putStrLn (drawTree (fmap show (arbolDivisiones 30)))

-- 30

-- |

-- +- 15

-- | |

-- | +- 5

-- | | |

-- | | `- 1

-- | |

-- | `- 3

-- | |

-- | `- 1

-- |

-- +- 10

-- | |

-- | +- 5

-- | | |

-- | | `- 1

-- | |

-- | `- 2

-- | |

-- | `- 1

-- |

-- `- 6

-- |

-- +- 3

-- | |

-- | `- 1

-- |

-- `- 2

-- |

-- `- 1

arbolDivisiones :: Integer -> Tree Integer

arbolDivisiones x =

Node x (map arbolDivisiones (divisiones x))

-- (divisiones x) es la lista de las divisiones enteras de x entre 2, 3

-- y 5. Por ejemplo,

-- divisiones 30 == [15,10,6]

-- divisiones 15 == [5,3]

divisiones :: Integer -> [Integer]

divisiones x =

[x `div` y | y <- [2,3,5], x `mod` y == 0]

-- (nodos a) es el conjunto de nodos del árbol a. Por ejemplo,

-- nodos (Node 2 [Node 2 [], Node 5 []]) == [2,5]

-- nodos (arbolDivisiones 30) == [30,15,5,1,3,10,2,6]

nodos :: Tree Integer -> [Integer]

nodos = nub . flatten

-- (divisionesComunes x y) es la lista de los nodos comunes de los

-- árboles de las divisiones de x e y entre 2, 3 ó 5. Por ejemplo,

-- divisionesComunes 15 20 == [5,1]

divisionesComunes :: Integer -> Integer -> [Integer]

divisionesComunes x y =

nodos (arbolDivisiones x) `intersect` nodos (arbolDivisiones y)

-- (minimaProfundidad x ns) es justamente la mínima produndidad

-- donde aparece x en el árbol ns, si aparece y Nothing, en caso

-- contrario. Por ejemplo,minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int

-- λ> minimaProfundidad 3 (Node 1 [Node 6 [],Node 3 [Node 1 []]])

-- Just 1

-- λ> minimaProfundidad 4 (Node 1 [Node 6 [],Node 3 [Node 1 []]])

-- Nothing

minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int

minimaProfundidad x ns =

listToMaybe [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys]

-- (minimasProfundidadesComunes x e y) es la lista de pares formadas por

-- los nodos comunes de los árboles de las divisiones de x e y entre 2,

-- 3 ó 5 junto con las mínimas profundidades en cada uno de los

-- árboles. Por ejemplo,

-- minimasProfundidadesComunes 15 20 == [(5,(1,2)),(1,(2,3))]

-- minimasProfundidadesComunes 15 22 == []

minimasProfundidadesComunes :: Integer -> Integer -> [(Integer,(Int,Int))]

minimasProfundidadesComunes x1 x2 =

[(c,(fromJust (minimaProfundidad c a1), fromJust (minimaProfundidad c a2)))

| c <- cs]

where a1 = arbolDivisiones x1

a2 = arbolDivisiones x2

cs = divisionesComunes x1 x2

-- Propiedad

-- =========

-- El mínimo número de divisiones se alcanza en el máximo común divisor.

prop_minimoNumeroDivisiones :: Integer -> Integer -> Property

prop_minimoNumeroDivisiones x y =

x > 0 && y > 0 ==>

isNothing a || snd (fromJust a) == gcd x y

where a = minimoNumeroDivisionesAux x y

-- La comprobación es

-- λ> quickCheck prop_minimoNumeroDivisiones

-- +++ OK, passed 100 tests.

-- 2ª solución

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

minimoNumeroDivisiones2 :: Integer -> Integer -> Maybe Int

minimoNumeroDivisiones2 x y

| as' == bs' = Just (sum [abs (a - b) | (a,b) <- zip as bs])

| otherwise = Nothing

where (as,as') = factorizacion x

(bs,bs') = factorizacion y

-- (factorización n) es la lista de pares cuya primera componente es la

-- lista de los exponentes de 2, 3 y 5 en la factorización de n y la

-- segunda esla lista delos restantes divisores primos. Por ejemplo,

-- factorizacion 15 == ([0,1,1],[])

-- factorizacion 20 == ([2,0,1],[])

-- factorizacion 17 == ([0,0,0],[17])

-- factorizacion 147 == ([0,1,0],[7,7])

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

factorizacion n =

(map length [bs,cs,ds], es)

where as = primeFactors n

(bs,bs') = span (==2) as

(cs,cs') = span (==3) bs'

(ds,es) = span (==5) cs'

-- Equivalencia

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

-- La propies de la equivalencia de las dos definiciones es

prop_equivalencia :: Integer -> Integer -> Property

prop_equivalencia x y =

x > 0 && y > 0 ==>

minimoNumeroDivisiones x y == minimoNumeroDivisiones2 x y

-- La comprobación es

-- λ> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> minimoNumeroDivisiones (10^11) (3^10*7)

-- Nothing

-- (6.08 secs, 2,725,931,872 bytes)

-- λ> minimoNumeroDivisiones2(10^11) (3^10*7)

-- Nothing

-- (0.01 secs, 128,944 bytes)

Nuevas soluciones

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

Mínima profundidad

PorJosé A. Alonso 23-marzo-202130-marzo-2021

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

1 2	data Tree a = Node a (Forest a) type Forest a = [Tree a]

Por ejemplo, los árboles

     1               3
    / \             /|\
   6   3           / | \
       |          5  4  7
       1          |     /\
                  3    6  5

1 3

/ \ /|\

6 3 / | \

| 5 4 7

1 | /\

3 6 5

se representan por

   ej1, ej2 :: Tree Int
   ej1 = Node 1 [Node 6 [],Node 3 [Node 1 []]]
   ej2 = Node 3 [Node 5 [Node 3 []], Node 4 [], Node 7 [Node 6 [], Node 5 []]]

ej1, ej2 :: Tree Int

ej1 = Node 1 [Node 6 [],Node 3 [Node 1 []]]

ej2 = Node 3 [Node 5 [Node 3 []], Node 4 [], Node 7 [Node 6 [], Node 5 []]]

Definir la función

    minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int

1	minimaProfundidad :: Ord a => a -> Tree a -> Maybe Int

tal que (minimaProfundidad x ns) es justamente la mínima donde aparece x en el árbol ns, si aparece y Nothing, en caso contrario. Por ejemplo,

    minimaProfundidad 1 ej1  ==  Just 0
    minimaProfundidad 3 ej1  ==  Just 1
    minimaProfundidad 2 ej1  ==  Nothing
    minimaProfundidad 3 ej2  ==  Just 0
    minimaProfundidad 4 ej2  ==  Just 1
    minimaProfundidad 6 ej2  ==  Just 2
    minimaProfundidad 9 ej2  ==  Nothing

minimaProfundidad 1 ej1 == Just 0

minimaProfundidad 3 ej1 == Just 1

minimaProfundidad 2 ej1 == Nothing

minimaProfundidad 3 ej2 == Just 0

minimaProfundidad 4 ej2 == Just 1

minimaProfundidad 6 ej2 == Just 2

minimaProfundidad 9 ej2 == Nothing

Soluciones

import Data.Tree (Tree (Node), levels)
import Data.Maybe (isNothing, fromJust, listToMaybe)

ej1, ej2 :: Tree Int
ej1 = Node 1 [Node 6 [],Node 3 [Node 1 []]]
ej2 = Node 3 [Node 5 [Node 3 []], Node 4 [], Node 7 [Node 6 [], Node 5 []]]

-- 1ª definición
minimaProfundidad1 :: Ord a => a -> Tree a -> Maybe Int
minimaProfundidad1 x (Node y ns)
  | x == y    = Just 0
  | null zs   = Nothing
  | otherwise = Just (1 + minimum zs)
  where zs = [z | Just z <- filter (/=Nothing) (map (minimaProfundidad1 x) ns)]

-- 2ª definición
minimaProfundidad2 :: Ord a => a -> Tree a -> Maybe Int
minimaProfundidad2 x (Node y ns)
  | x == y       = Just 0
  | z == Nothing = Nothing
  | otherwise    = Just (1 + fromJust z)
  where z = minimum (map (minimaProfundidad2 x) ns)

-- 3ª definición
minimaProfundidad3 :: Ord a => a -> Tree a -> Maybe Int
minimaProfundidad3 x (Node y ns)
  | x == y       = Just 0
  | otherwise    = Just (+1) <*> minimum (map (minimaProfundidad3 x) ns)

-- 4ª definición
minimaProfundidad4 :: Ord a => a -> Tree a -> Maybe Int
minimaProfundidad4 x ns
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where zs = [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys]

-- 5ª definición
minimaProfundidad5 :: Ord a => a -> Tree a -> Maybe Int
minimaProfundidad5 x ns =
  listToMaybe [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys]

import Data.Tree (Tree (Node), levels)

import Data.Maybe (isNothing, fromJust, listToMaybe)

ej1, ej2 :: Tree Int

ej1 = Node 1 [Node 6 [],Node 3 [Node 1 []]]

ej2 = Node 3 [Node 5 [Node 3 []], Node 4 [], Node 7 [Node 6 [], Node 5 []]]

-- 1ª definición

minimaProfundidad1 :: Ord a => a -> Tree a -> Maybe Int

minimaProfundidad1 x (Node y ns)

| x == y = Just 0

| null zs = Nothing

| otherwise = Just (1 + minimum zs)

where zs = [z | Just z <- filter (/=Nothing) (map (minimaProfundidad1 x) ns)]

-- 2ª definición

minimaProfundidad2 :: Ord a => a -> Tree a -> Maybe Int

minimaProfundidad2 x (Node y ns)

| x == y = Just 0

| z == Nothing = Nothing

| otherwise = Just (1 + fromJust z)

where z = minimum (map (minimaProfundidad2 x) ns)

-- 3ª definición

minimaProfundidad3 :: Ord a => a -> Tree a -> Maybe Int

minimaProfundidad3 x (Node y ns)

| x == y = Just 0

| otherwise = Just (+1) <*> minimum (map (minimaProfundidad3 x) ns)

-- 4ª definición

minimaProfundidad4 :: Ord a => a -> Tree a -> Maybe Int

minimaProfundidad4 x ns

| null zs = Nothing

| otherwise = Just (head zs)

where zs = [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys]

-- 5ª definición

minimaProfundidad5 :: Ord a => a -> Tree a -> Maybe Int

minimaProfundidad5 x ns =

listToMaybe [z | (z,ys) <- zip [0..] (levels ns), x `elem` ys]

Nuevas soluciones

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

Árbol de las divisiones por 2, 3 ó 5

PorJosé A. Alonso 22-marzo-202129-marzo-2021

En la librería Data.Tree se definen los árboles y los bosques como sigue

   data Tree a   = Node a (Forest a)
   type Forest a = [Tree a]

1 2	data Tree a = Node a (Forest a) type Forest a = [Tree a]

Se pueden definir árboles. Por ejemplo,

   ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

1	ej = Node 3 [Node 5 [Node 9 []], Node 7 []]

Y se pueden dibujar con la función drawTree. Por ejemplo,

   λ> putStrLn (drawTree (fmap show ej))
   3
   |
   +- 5
   |  |
   |  `- 9
   |
   `- 7

λ> putStrLn (drawTree (fmap show ej))

+- 5

| |

| `- 9

`- 7

Definir la función

   arbolDivisiones :: Int -> Tree Int

1	arbolDivisiones :: Int -> Tree Int

tal que (arbolDivisiones x) es el árbol de las divisiones enteras de x entre 2, 3 ó 5. Por ejemplo,

   λ> putStrLn (drawTree (fmap show (arbolDivisiones 20)))
   20
   |
   +- 10
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 2
   |     |
   |     `- 1
   |
   `- 4
      |
      `- 2
         |
         `- 1

   λ> putStrLn (drawTree (fmap show (arbolDivisiones 30)))
   30
   |
   +- 15
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 3
   |     |
   |     `- 1
   |
   +- 10
   |  |
   |  +- 5
   |  |  |
   |  |  `- 1
   |  |
   |  `- 2
   |     |
   |     `- 1
   |
   `- 6
      |
      +- 3
      |  |
      |  `- 1
      |
      `- 2
         |
         `- 1

λ> putStrLn (drawTree (fmap show (arbolDivisiones 20)))

+- 10

| |

| +- 5

| | |

| | `- 1

| |

| `- 2

| |

| `- 1

`- 4

`- 2

`- 1

λ> putStrLn (drawTree (fmap show (arbolDivisiones 30)))

+- 15

| |

| +- 5

| | |

| | `- 1

| |

| `- 3

| |

| `- 1

+- 10

| |

| +- 5

| | |

| | `- 1

| |

| `- 2

| |

| `- 1

`- 6

+- 3

| |

| `- 1

`- 2

`- 1

Soluciones

import Data.Tree (Tree (Node), drawTree)

arbolDivisiones :: Int -> Tree Int
arbolDivisiones x =
  Node x (map arbolDivisiones (divisiones x))

-- (divisiones x) es la lista de las divisiones enteras de x entre 2, 3
-- y 5. Por ejemplo,
--    divisiones 30  ==  [15,10,6]
--    divisiones 15  ==  [5,3]
divisiones :: Int -> [Int]
divisiones x =
  [x `div` y | y <- [2,3,5], x `mod` y == 0]

import Data.Tree (Tree (Node), drawTree)

arbolDivisiones :: Int -> Tree Int

arbolDivisiones x =

Node x (map arbolDivisiones (divisiones x))

-- (divisiones x) es la lista de las divisiones enteras de x entre 2, 3

-- y 5. Por ejemplo,

-- divisiones 30 == [15,10,6]

-- divisiones 15 == [5,3]

divisiones :: Int -> [Int]

divisiones x =

[x `div` y | y <- [2,3,5], x `mod` y == 0]

Nuevas soluciones

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

Cálculo de pi mediante la fórmula de Beeler

PorJosé A. Alonso 19-marzo-202126-marzo-2021

El pasado 12 de marzo se publicó en Twitter un mensaje con una fórmula de Beeler para el cálculo de pi

Los primeros valores son

   λ> 2*1
   2
   λ> 2*(1+1/3)
   2.6666666666666665
   λ> 2*(1+1/3+(1*2)/(3*5))
   2.933333333333333
   λ> 2*(1+1/3+(1*2)/(3*5)+(1*2*3)/(3*5*7))
   3.0476190476190474
   λ> 2*(1+1/3+(1*2)/(3*5)+(1*2*3)/(3*5*7)+(1*2*3*4)/(3*5*7*9))
   3.098412698412698

λ> 2*1

λ> 2*(1+1/3)

2.6666666666666665

λ> 2*(1+1/3+(1*2)/(3*5))

2.933333333333333

λ> 2*(1+1/3+(1*2)/(3*5)+(1*2*3)/(3*5*7))

3.0476190476190474

λ> 2*(1+1/3+(1*2)/(3*5)+(1*2*3)/(3*5*7)+(1*2*3*4)/(3*5*7*9))

3.098412698412698

Definir las funciones

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

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

tales que

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

     aproximacionPi 0    ==  2.0
     aproximacionPi 1    ==  2.6666666666666665
     aproximacionPi 2    ==  2.933333333333333
     aproximacionPi 3    ==  3.0476190476190474
     aproximacionPi 4    ==  3.098412698412698
     aproximacionPi 10   ==  3.141106021601377
     aproximacionPi 100  ==  3.1415926535897922
     pi                  ==  3.141592653589793

aproximacionPi 0 == 2.0

aproximacionPi 1 == 2.6666666666666665

aproximacionPi 2 == 2.933333333333333

aproximacionPi 3 == 3.0476190476190474

aproximacionPi 4 == 3.098412698412698

aproximacionPi 10 == 3.141106021601377

aproximacionPi 100 == 3.1415926535897922

pi == 3.141592653589793

(grafica xs) dibuja la gráfica de las k-ésimas aproximaciones de pi para k en xs. Por ejemplo, (grafica [0..99]) dibuja

Soluciones

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

aproximacionPi :: Int -> Double
aproximacionPi n =
  aproximacionesPi !! n

aproximacionesPi :: [Double]
aproximacionesPi =
  map (*2) (scanl1 (+) (1 : scanl1 (*) [(x/y) | (x,y) <- zip [1..] [3,5..]]))


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

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

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

aproximacionPi :: Int -> Double

aproximacionPi n =

aproximacionesPi !! n

aproximacionesPi :: [Double]

aproximacionesPi =

map (*2) (scanl1 (+) (1 : scanl1 (*) [(x/y) | (x,y) <- zip [1..] [3,5..]]))

-- Gráfica

-- =======

grafica :: [Int] -> IO ()

grafica xs =

plotList [ Key Nothing

-- , PNG "Calculo_de_pi_mediante_la_formula_de_Beeler_1.png"

]

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

Nuevas soluciones

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

Números ordenados con cuadrados ordenados

PorJosé A. Alonso 18-marzo-202125-marzo-2021

Un número es ordenado si cada uno de sus dígitos es menor o igual el siguiente dígito. Por ejemplo, 116 es un número creciente y su cuadrado es 13456, que también es ordenado. En cambio, 115 es ordenado pero su cuadrado es 13225 que no es ordenado.

Definir la lista

   numerosOrdenadosConCuadradosOrdenados :: [Integer]

1	numerosOrdenadosConCuadradosOrdenados :: [Integer]

cuyos elementos son los números ordenados cuyos cuadrados también lo son. Por ejemplo,

   λ> take 20 numerosOrdenadosConCuadradosOrdenados
   [0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117]
   λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (10^6)))
   1411
   λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (5*10^6)))
   3159

λ> take 20 numerosOrdenadosConCuadradosOrdenados

[0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117]

λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (10^6)))

1411

λ> length (show (numerosOrdenadosConCuadradosOrdenados !! (5*10^6)))

3159

Soluciones

import Data.List

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

numerosOrdenadosConCuadradosOrdenados :: [Integer]
numerosOrdenadosConCuadradosOrdenados =
  filter numeroOrdenadoConCuadradoOrdenado [0..]

-- (numeroOrdenadoConCuadradoOrdenado n) se verifica si n es un número
-- ordenado cuyo cuadrado también lo es. Por ejemplo,
--    numeroOrdenadoConCuadradoOrdenado 116  ==  True
--    numeroOrdenadoConCuadradoOrdenado 115  ==  False
numeroOrdenadoConCuadradoOrdenado :: Integer -> Bool
numeroOrdenadoConCuadradoOrdenado n =
  ordenado n && ordenado (n^2)

-- (ordenado n) se verifica si n es un número ordenado. Por ejemplo,
--    ordenado 115  ==  True
--    ordenado 151  ==  False
ordenado :: Integer -> Bool
ordenado n =
  and [x <= y | (x,y) <- zip xs (tail xs)]
  where xs = show n

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

-- Se basa en la observación de los sisuientes cálculos con la primera
-- solución
--    λ> take 30 numerosOrdenadosConCuadradosOrdenados
--    [0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117,
--     167,334,335,337,367,667,1667,3334,3335,3337]
--    λ> take 21 (dropWhile (<= 117) numerosOrdenadosConCuadradosOrdenados)
--    [167,334,335,337,367,667,
--     1667,3334,3335,3337,3367,3667,6667,
--     16667,33334,33335,33337,33367,33667,36667,66667]
--
-- Se observa que a partir del 167 todos los elementos son de 4 tipos
-- como se ve en la siguente tabla
--    |-------+--------+--------+--------+--------|
--    |       | Tipo A | Tipo B | Tipo C | Tipo D |
--    |-------+--------+--------+--------+--------|
--    |   167 | 16¹7   |        |        |        |
--    |   334 |        | 3²4    |        |        |
--    |   335 |        |        | 3²5    |        |
--    |   337 |        |        |        | 3²6⁰7  |
--    |   367 |        |        |        | 3¹6¹7  |
--    |   667 |        |        |        | 3⁰6²7  |
--    |  1667 | 16²7   |        |        |        |
--    |  3334 |        | 3³4    |        |        |
--    |  3335 |        |        | 3³5    |        |
--    |  3337 |        |        |        | 3³6⁰7  |
--    |  3367 |        |        |        | 3²6¹7  |
--    |  3667 |        |        |        | 3¹6²7  |
--    |  6667 |        |        |        | 3⁰6³7  |
--    | 16667 | 16³7   |        |        |        |
--    | 33334 |        | 3⁴4    |        |        |
--    | 33335 |        |        | 3⁴5    |        |
--    | 33337 |        |        |        | 3⁴6⁰7  |
--    | 33367 |        |        |        | 3³6¹7  |
--    | 33667 |        |        |        | 3²6²7  |
--    | 36667 |        |        |        | 3¹6³7  |
--    | 66667 |        |        |        | 3⁰6⁴7  |
--    |-------+--------+--------+--------+--------|
-- donde el exponente en cad dígito indica el número de repeticiones de
-- dicho dígito.

numerosOrdenadosConCuadradosOrdenados2 :: [Integer]
numerosOrdenadosConCuadradosOrdenados2 =
  [0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117] ++
  map read (concat [['1' : replicate n '6' ++ "7",
                     replicate (n+1) '3' ++ "4",
                     replicate (n+1) '3' ++ "5"] ++
                    [replicate a '3' ++ replicate b '6' ++ "7"
                    | b <- [0..n+1], let a = (n+1) - b]
                   | n <- [1..]])

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

-- La comparación es
--    λ> numerosOrdenadosConCuadradosOrdenados !! 50
--    1666667
--    (2.35 secs, 2,173,983,096 bytes)
--    λ> numerosOrdenadosConCuadradosOrdenados2 !! 50
--    1666667
--    (0.01 secs, 125,296 bytes)

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

-- La comprobación es
--    λ> take 50 numerosOrdenadosConCuadradosOrdenados == take 50 numerosOrdenadosConCuadradosOrdenados2
--    True

import Data.List

-- 1ª solución

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

numerosOrdenadosConCuadradosOrdenados :: [Integer]

numerosOrdenadosConCuadradosOrdenados =

filter numeroOrdenadoConCuadradoOrdenado [0..]

-- (numeroOrdenadoConCuadradoOrdenado n) se verifica si n es un número

-- ordenado cuyo cuadrado también lo es. Por ejemplo,

-- numeroOrdenadoConCuadradoOrdenado 116 == True

-- numeroOrdenadoConCuadradoOrdenado 115 == False

numeroOrdenadoConCuadradoOrdenado :: Integer -> Bool

numeroOrdenadoConCuadradoOrdenado n =

ordenado n && ordenado (n^2)

-- (ordenado n) se verifica si n es un número ordenado. Por ejemplo,

-- ordenado 115 == True

-- ordenado 151 == False

ordenado :: Integer -> Bool

ordenado n =

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

where xs = show n

-- 2ª solución

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

-- Se basa en la observación de los sisuientes cálculos con la primera

-- solución

-- λ> take 30 numerosOrdenadosConCuadradosOrdenados

-- [0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117,

-- 167,334,335,337,367,667,1667,3334,3335,3337]

-- λ> take 21 (dropWhile (<= 117) numerosOrdenadosConCuadradosOrdenados)

-- [167,334,335,337,367,667,

-- 1667,3334,3335,3337,3367,3667,6667,

-- 16667,33334,33335,33337,33367,33667,36667,66667]

-- Se observa que a partir del 167 todos los elementos son de 4 tipos

-- como se ve en la siguente tabla

-- |-------+--------+--------+--------+--------|

-- |-------+--------+--------+--------+--------|

-- | 167 | 16¹7 | | | |

-- | 334 | | 3²4 | | |

-- | 335 | | | 3²5 | |

-- | 337 | | | | 3²6⁰7 |

-- | 367 | | | | 3¹6¹7 |

-- | 667 | | | | 3⁰6²7 |

-- | 1667 | 16²7 | | | |

-- | 3334 | | 3³4 | | |

-- | 3335 | | | 3³5 | |

-- | 3337 | | | | 3³6⁰7 |

-- | 3367 | | | | 3²6¹7 |

-- | 3667 | | | | 3¹6²7 |

-- | 6667 | | | | 3⁰6³7 |

-- | 16667 | 16³7 | | | |

-- | 33334 | | 3⁴4 | | |

-- | 33335 | | | 3⁴5 | |

-- | 33337 | | | | 3⁴6⁰7 |

-- | 33367 | | | | 3³6¹7 |

-- | 33667 | | | | 3²6²7 |

-- | 36667 | | | | 3¹6³7 |

-- | 66667 | | | | 3⁰6⁴7 |

-- |-------+--------+--------+--------+--------|

-- donde el exponente en cad dígito indica el número de repeticiones de

-- dicho dígito.

numerosOrdenadosConCuadradosOrdenados2 :: [Integer]

numerosOrdenadosConCuadradosOrdenados2 =

[0,1,2,3,4,5,6,7,12,13,15,16,17,34,35,37,38,67,116,117] ++

map read (concat [['1' : replicate n '6' ++ "7",

replicate (n+1) '3' ++ "4",

replicate (n+1) '3' ++ "5"] ++

[replicate a '3' ++ replicate b '6' ++ "7"

| b <- [0..n+1], let a = (n+1) - b]

| n <- [1..]])

-- Comparación de eficiencia

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

-- La comparación es

-- λ> numerosOrdenadosConCuadradosOrdenados !! 50

-- 1666667

-- (2.35 secs, 2,173,983,096 bytes)

-- λ> numerosOrdenadosConCuadradosOrdenados2 !! 50

-- 1666667

-- (0.01 secs, 125,296 bytes)

-- Comprobación de equivalencia

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

-- La comprobación es

-- λ> take 50 numerosOrdenadosConCuadradosOrdenados == take 50 numerosOrdenadosConCuadradosOrdenados2

-- True

Nuevas soluciones

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

Meses: marzo 2021

Mínimo número de divisiones para igualar

Soluciones

Nuevas soluciones

Mínima profundidad

Soluciones

Nuevas soluciones

Árbol de las divisiones por 2, 3 ó 5

Soluciones

Nuevas soluciones

Cálculo de pi mediante la fórmula de Beeler

Soluciones

Nuevas soluciones

Números ordenados con cuadrados ordenados

Soluciones

Nuevas soluciones

Entradas recientes

Buscar

Correo electrónico