head – Página 3 – Exercitium

Números compuestos por un conjunto de primos

PorJosé A. Alonso 20-abril-201830-abril-2018

Los números compuestos por un conjunto de primos son los números cuyos factores primos pertenecen al conjunto. Por ejemplo, los primeros números compuestos por [2,5,7] son

   1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,...

1	1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70,...

El 28 es compuesto ya que sus divisores primos son 2 y 7 que están en [2,5,7].

Definir la función

   compuestos :: [Integer] -> [Integer]

1	compuestos :: [Integer] -> [Integer]

tal que (compuesto ps) es la lista de los números compuestos por el conjunto de primos ps. Por ejemplo,

   λ> take 20 (compuestos [2,5,7])
   [1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70]
   λ> take 20 (compuestos [2,5])
   [1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250]
   λ> take 20 (compuestos [2,3,5])
   [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]
   λ> take 20 (compuestos [3,5,7,11,13])
   [1,3,5,7,9,11,13,15,21,25,27,33,35,39,45,49,55,63,65,75]
   λ> take 15 (compuestos [2])
   [1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]
   λ> compuestos [2,7] !! (10^4)
   57399514149595471961908157955229677377312712667508119466382354072731648
   λ> compuestos [2,3,5] !! (10^5)
   290237644800000000000000000000000000000

λ> take 20 (compuestos [2,5,7])

[1,2,4,5,7,8,10,14,16,20,25,28,32,35,40,49,50,56,64,70]

λ> take 20 (compuestos [2,5])

[1,2,4,5,8,10,16,20,25,32,40,50,64,80,100,125,128,160,200,250]

λ> take 20 (compuestos [2,3,5])

[1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36]

λ> take 20 (compuestos [3,5,7,11,13])

[1,3,5,7,9,11,13,15,21,25,27,33,35,39,45,49,55,63,65,75]

λ> take 15 (compuestos [2])

[1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384]

λ> compuestos [2,7] !! (10^4)

57399514149595471961908157955229677377312712667508119466382354072731648

λ> compuestos [2,3,5] !! (10^5)

290237644800000000000000000000000000000

Soluciones

import Data.Numbers.Primes (primeFactors)

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

compuestos1 :: [Integer] -> [Integer]
compuestos1 ps =
  [n | n <- [1..], esCompuesto ps n]

-- (esCompuesto ps n) se verifica si los factores primos de n pertenecen
-- a ps. Por ejemplo, 
--    esCompuesto [2,3,7]    28  ==  True
--    esCompuesto [2,3,7]   140  ==  False
--    esCompuesto [2,3,5,7] 140  ==  True
esCompuesto :: [Integer] -> Integer -> Bool
esCompuesto ps n =
  subconjunto (primeFactors n) ps

-- (subconjunto xs ys) se verifica si todos los elementos de xs
-- pertenecen a ys. Por ejemplo, 
--    subconjunto [2,7,2] [7,5,2]  ==  True
--    subconjunto [2,7,3] [7,5,2]  ==  False
subconjunto :: Eq a => [a] -> [a] -> Bool
subconjunto xs ys =
  all (`elem` ys) xs

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

compuestos2 :: [Integer] -> [Integer]
compuestos2 ps =
   1 : mezclaTodas (combinaciones ps)

-- (combinaciones ps) es la lista de los productos de cada elemento de
-- ps por los números compuestos con ps. Por ejemplo,
--    λ> take 8 (compuestos4 [2,5,7])
--    [1,2,4,5,7,8,10,14]
--    λ> map (take 6) (combinaciones [2,5,7])
--    [[2,4,8,10,14,16],[5,10,20,25,35,40],[7,14,28,35,49,56]]
combinaciones :: [Integer] -> [[Integer]]
combinaciones ps =
  [[p * q | q <- compuestos2 ps] | p <- ps]

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
-- sus elementos son listas infinitas ordenadas. Por ejemplo, 
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
--    [2,3,4,5,6,7,8,9,10,11]
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
--    [2,4,6,8,9,10,12,14,16,18]
mezclaTodas :: [[Integer]] -> [Integer]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys

-- (mezcla xs ys) es la mezcla, eliminando repetidos, de las lista
-- ordenadas xs e ys. Por ejemplo,  
mezcla :: [Integer] -> [Integer] -> [Integer]
mezcla []     ys              = ys
mezcla xs     []              = xs
mezcla us@(x:xs) vs@(y:ys) | x == y     = x : mezcla xs ys
                           | x < y      = x : mezcla xs vs
                           | otherwise  = y : mezcla us ys

-- 3ª solución
-- ===========

compuestos3 :: [Integer] -> [Integer]
compuestos3 [] = [1]
compuestos3 (p:ps) =
  mezclaTodas [map (*y) (compuestos3 ps) | y <- [p^k | k <- [0..]]]

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

compuestos4 :: [Integer] -> [Integer]
compuestos4 ps = foldl aux xs (tail ps)
  where p        = head ps
        xs       = [p^k | k <- [0..]]
        aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]

-- 5ª solución
-- ===========

compuestos5 :: [Integer] -> [Integer]
compuestos5 = foldl aux [1] 
  where aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]

-- 6ª solución
-- ===========

compuestos6 :: [Integer] -> [Integer]
compuestos6 xs = aux
  where aux = 1 : mezclas xs aux
        mezclas []     _  = []
        mezclas (x:xs) zs = mezcla (map (x*) zs) (mezclas xs zs)

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

--    λ> compuestos1 [2,3,5] !! 300
--    84375
--    (5.85 secs, 2,961,101,088 bytes)
--    λ> compuestos2 [2,3,5] !! 300
--    84375
--    (3.54 secs, 311,137,952 bytes)
--    λ> compuestos2 [2,3,5] !! 400
--    312500
--    (13.01 secs, 1,229,801,184 bytes)
--    λ> compuestos3 [2,3,5] !! 400
--    312500
--    (0.02 secs, 2,066,152 bytes)
--    λ> compuestos3 [2,3,5] !! 20000
--    15441834907098675000000
--    (1.57 secs, 203,061,864 bytes)
--    λ> compuestos4 [2,3,5] !! 20000
--    15441834907098675000000
--    (0.40 secs, 53,335,080 bytes)
--    λ> compuestos4 [2,3,5] !! 50000
--    2379528690747474604574166220800
--    (1.25 secs, 170,058,496 bytes)
--    λ> compuestos5 [2,3,5] !! 50000
--    2379528690747474604574166220800
--    (1.26 secs, 170,104,648 bytes)
--    λ> compuestos6 [2,3,5] !! 50000
--    2379528690747474604574166220800
--    (0.26 secs, 40,490,280 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

import Data.Numbers.Primes (primeFactors)

-- 1ª solución

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

compuestos1 :: [Integer] -> [Integer]

compuestos1 ps =

[n | n <- [1..], esCompuesto ps n]

-- (esCompuesto ps n) se verifica si los factores primos de n pertenecen

-- a ps. Por ejemplo,

-- esCompuesto [2,3,7] 28 == True

-- esCompuesto [2,3,7] 140 == False

-- esCompuesto [2,3,5,7] 140 == True

esCompuesto :: [Integer] -> Integer -> Bool

esCompuesto ps n =

subconjunto (primeFactors n) ps

-- (subconjunto xs ys) se verifica si todos los elementos de xs

-- pertenecen a ys. Por ejemplo,

-- subconjunto [2,7,2] [7,5,2] == True

-- subconjunto [2,7,3] [7,5,2] == False

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

subconjunto xs ys =

all (`elem` ys) xs

-- 2ª solución

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

compuestos2 :: [Integer] -> [Integer]

compuestos2 ps =

1 : mezclaTodas (combinaciones ps)

-- (combinaciones ps) es la lista de los productos de cada elemento de

-- ps por los números compuestos con ps. Por ejemplo,

-- λ> take 8 (compuestos4 [2,5,7])

-- [1,2,4,5,7,8,10,14]

-- λ> map (take 6) (combinaciones [2,5,7])

-- [[2,4,8,10,14,16],[5,10,20,25,35,40],[7,14,28,35,49,56]]

combinaciones :: [Integer] -> [[Integer]]

combinaciones ps =

[[p * q | q <- compuestos2 ps] | p <- ps]

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como

-- sus elementos son listas infinitas ordenadas. Por ejemplo,

-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])

-- [2,3,4,5,6,7,8,9,10,11]

-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])

-- [2,4,6,8,9,10,12,14,16,18]

mezclaTodas :: [[Integer]] -> [Integer]

mezclaTodas = foldr1 xmezcla

where xmezcla (x:xs) ys = x : mezcla xs ys

-- (mezcla xs ys) es la mezcla, eliminando repetidos, de las lista

-- ordenadas xs e ys. Por ejemplo,

mezcla :: [Integer] -> [Integer] -> [Integer]

mezcla [] ys = ys

mezcla xs [] = xs

mezcla us@(x:xs) vs@(y:ys) | x == y = x : mezcla xs ys

| x < y = x : mezcla xs vs

| otherwise = y : mezcla us ys

-- 3ª solución

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

compuestos3 :: [Integer] -> [Integer]

compuestos3 [] = [1]

compuestos3 (p:ps) =

mezclaTodas [map (*y) (compuestos3 ps) | y <- [p^k | k <- [0..]]]

-- 4ª solución

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

compuestos4 :: [Integer] -> [Integer]

compuestos4 ps = foldl aux xs (tail ps)

where p = head ps

xs = [p^k | k <- [0..]]

aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]

-- 5ª solución

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

compuestos5 :: [Integer] -> [Integer]

compuestos5 = foldl aux [1]

where aux xs p = mezclaTodas [map (*y) xs | y <- [p^k | k <- [0..]]]

-- 6ª solución

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

compuestos6 :: [Integer] -> [Integer]

compuestos6 xs = aux

where aux = 1 : mezclas xs aux

mezclas [] _ = []

mezclas (x:xs) zs = mezcla (map (x*) zs) (mezclas xs zs)

-- Comparación de eficiencia

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

-- λ> compuestos1 [2,3,5] !! 300

-- 84375

-- (5.85 secs, 2,961,101,088 bytes)

-- λ> compuestos2 [2,3,5] !! 300

-- 84375

-- (3.54 secs, 311,137,952 bytes)

-- λ> compuestos2 [2,3,5] !! 400

-- 312500

-- (13.01 secs, 1,229,801,184 bytes)

-- λ> compuestos3 [2,3,5] !! 400

-- 312500

-- (0.02 secs, 2,066,152 bytes)

-- λ> compuestos3 [2,3,5] !! 20000

-- 15441834907098675000000

-- (1.57 secs, 203,061,864 bytes)

-- λ> compuestos4 [2,3,5] !! 20000

-- 15441834907098675000000

-- (0.40 secs, 53,335,080 bytes)

-- λ> compuestos4 [2,3,5] !! 50000

-- 2379528690747474604574166220800

-- (1.25 secs, 170,058,496 bytes)

-- λ> compuestos5 [2,3,5] !! 50000

-- 2379528690747474604574166220800

-- (1.26 secs, 170,104,648 bytes)

-- λ> compuestos6 [2,3,5] !! 50000

-- 2379528690747474604574166220800

-- (0.26 secs, 40,490,280 bytes)

Alturas primas

PorJosé A. Alonso 10-abril-201826-marzo-2022

Se considera una enumeración de los números primos:

    p(1)=2,  p(2)=3, p(3)=5, p(4)=7, p(5)=11, p(6)=13, p(7)=17,...

1	p(1)=2, p(2)=3, p(3)=5, p(4)=7, p(5)=11, p(6)=13, p(7)=17,...

Dado un entero x > 1, su altura prima es el mayor i tal que el primo p(i) aparece en la factorización de x en números primos. Por ejemplo, la altura prima de 3500 tiene longitud 4, pues 3500=2^2×5^3×7^1 y la de 34 tiene es 7, pues 34 = 2×17. Además, se define la altura prima de 1 como 0.

Definir las funciones

   alturaPrima        :: Integer -> Integer
   alturasPrimas      :: Integer -> [Integer]
   graficaAlturaPrima :: Integer -> IO ()

alturaPrima :: Integer -> Integer

alturasPrimas :: Integer -> [Integer]

graficaAlturaPrima :: Integer -> IO ()

tales que

(alturaPrima x) es la altura prima de x. Por ejemplo,

     alturaPrima 3500  ==  4
     alturaPrima 34    ==  7

1 2	alturaPrima 3500 == 4 alturaPrima 34 == 7

(alturasPrimas n) es la lista de las altura prima de los primeros n números enteros positivos. Por ejemplo,

     alturasPrimas 15  ==  [0,1,2,1,3,2,4,1,2,3,5,2,6,4,3]
     maximum (alturasPrimas 10000)  ==  1229
     maximum (alturasPrimas 20000)  ==  2262
     maximum (alturasPrimas 30000)  ==  3245
     maximum (alturasPrimas 40000)  ==  4203

alturasPrimas 15 == [0,1,2,1,3,2,4,1,2,3,5,2,6,4,3]

maximum (alturasPrimas 10000) == 1229

maximum (alturasPrimas 20000) == 2262

maximum (alturasPrimas 30000) == 3245

maximum (alturasPrimas 40000) == 4203

(graficaAlturaPrima n) dibuja las alturas primas de los números entre 2 y n. Por ejemplo, (graficaAlturaPrima 500) dibuja

Soluciones

import Data.List (genericLength)
import Data.Numbers.Primes (isPrime, primes, primeFactors)
import Data.Array
import Graphics.Gnuplot.Simple

-- 1ª definicioń de alturaPrima
-- ============================

alturaPrima :: Integer -> Integer
alturaPrima 1 = 0
alturaPrima n = indice (mayorFactorPrimo n)

-- (mayorFactorPrimo n) es el mayor factor primo de n. Por ejemplo,
--    mayorFactorPrimo 3500  ==  7
--    mayorFactorPrimo 34    ==  17
mayorFactorPrimo :: Integer -> Integer
mayorFactorPrimo = last . primeFactors

-- (indice p) es el índice de p en la sucesión de los números
-- primos. Por ejemplo,
--    indice 7   ==  4
--    indice 17  ==  7
indice :: Integer -> Integer
indice p = genericLength (takeWhile (<=p) primes)

-- 2ª definicioń de alturaPrima
-- ============================

alturaPrima2 :: Integer -> Integer
alturaPrima2 n = v ! n
  where v = array (1,n) [(i,f i) | i <- [1..n]]
        f 1 = 0
        f k | isPrime k = indice2 k
            | otherwise = v ! (k `div` (head (primeFactors k)))

indice2 :: Integer -> Integer
indice2 p = head [n | (x,n) <- indicesPrimos, x == p]

-- indicesPrimos es la suceción formada por los números primos y sus
-- índices. Por ejemplo,
--    λ> take 10 indicesPrimos
--    [(2,1),(3,2),(5,3),(7,4),(11,5),(13,6),(17,7),(19,8),(23,9),(29,10)]
indicesPrimos :: [(Integer,Integer)]
indicesPrimos = zip primes [1..]

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

alturasPrimas :: Integer -> [Integer]
alturasPrimas n = map alturaPrima [1..n]

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

alturasPrimas2 :: Integer -> [Integer]
alturasPrimas2 n = elems v 
  where v = array (1,n) [(i,f i) | i <- [1..n]]
        f 1 = 0
        f k | isPrime k = indice2 k
            | otherwise = v ! (k `div` (head (primeFactors k)))

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

--    λ> maximum (alturasPrimas 20000)
--    2262
--    (29.97 secs, 13,179,984,536 bytes)
--    λ> maximum (alturasPrimas2 20000)
--    2262
--    (2.11 secs, 455,259,448 bytes)

-- Definición de graficaAlturaPrima
-- ================================

graficaAlturaPrima :: Integer -> IO ()
graficaAlturaPrima n =
  plotList [ Key Nothing
           , PNG "Alturas_primas.png"
           ]
           (alturasPrimas2 n)

import Data.List (genericLength)

import Data.Numbers.Primes (isPrime, primes, primeFactors)

import Data.Array

import Graphics.Gnuplot.Simple

-- 1ª definicioń de alturaPrima

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

alturaPrima :: Integer -> Integer

alturaPrima 1 = 0

alturaPrima n = indice (mayorFactorPrimo n)

-- (mayorFactorPrimo n) es el mayor factor primo de n. Por ejemplo,

-- mayorFactorPrimo 3500 == 7

-- mayorFactorPrimo 34 == 17

mayorFactorPrimo :: Integer -> Integer

mayorFactorPrimo = last . primeFactors

-- (indice p) es el índice de p en la sucesión de los números

-- primos. Por ejemplo,

-- indice 7 == 4

-- indice 17 == 7

indice :: Integer -> Integer

indice p = genericLength (takeWhile (<=p) primes)

-- 2ª definicioń de alturaPrima

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

alturaPrima2 :: Integer -> Integer

alturaPrima2 n = v ! n

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

f 1 = 0

f k | isPrime k = indice2 k

| otherwise = v ! (k `div` (head (primeFactors k)))

indice2 :: Integer -> Integer

indice2 p = head [n | (x,n) <- indicesPrimos, x == p]

-- indicesPrimos es la suceción formada por los números primos y sus

-- índices. Por ejemplo,

-- λ> take 10 indicesPrimos

-- [(2,1),(3,2),(5,3),(7,4),(11,5),(13,6),(17,7),(19,8),(23,9),(29,10)]

indicesPrimos :: [(Integer,Integer)]

indicesPrimos = zip primes [1..]

-- 1ª definición de alturasPrimas

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

alturasPrimas :: Integer -> [Integer]

alturasPrimas n = map alturaPrima [1..n]

-- 2ª definición de alturasPrimas

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

alturasPrimas2 :: Integer -> [Integer]

alturasPrimas2 n = elems v

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

f 1 = 0

f k | isPrime k = indice2 k

| otherwise = v ! (k `div` (head (primeFactors k)))

-- Comparación de eficiencia

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

-- λ> maximum (alturasPrimas 20000)

-- 2262

-- (29.97 secs, 13,179,984,536 bytes)

-- λ> maximum (alturasPrimas2 20000)

-- 2262

-- (2.11 secs, 455,259,448 bytes)

-- Definición de graficaAlturaPrima

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

graficaAlturaPrima :: Integer -> IO ()

graficaAlturaPrima n =

plotList [ Key Nothing

, PNG "Alturas_primas.png"

]

(alturasPrimas2 n)

Máxima longitud de sublistas crecientes

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

Definir la función

   longitudMayorSublistaCreciente :: Ord a => [a] -> Int

1	longitudMayorSublistaCreciente :: Ord a => [a] -> Int

tal que (longitudMayorSublistaCreciente xs) es la el máximo de las longitudes de las sublistas crecientes de xs. Por ejemplo,

   λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]
   3
   λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]
   6
   λ> longitudMayorSublistaCreciente [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
   6
   λ> longitudMayorSublistaCreciente [1..2000]
   2000
   λ> longitudMayorSublistaCreciente [2000,1999..1]
   1
   λ> import System.Random
   λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
   λ> longitudMayorSublistaCreciente xs
   61

λ> longitudMayorSublistaCreciente [3,2,6,4,5,1]

λ> longitudMayorSublistaCreciente [10,22,9,33,21,50,41,60,80]

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

λ> longitudMayorSublistaCreciente [1..2000]

2000

λ> longitudMayorSublistaCreciente [2000,1999..1]

λ> import System.Random

λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]

λ> longitudMayorSublistaCreciente xs

Soluciones

import Data.List  (nub, sort)
import Data.Array (Array, (!), array, elems, listArray)

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

longitudMayorSublistaCreciente1 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente1 =
  length . head . mayoresCrecientes

-- (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs
-- de mayor longitud. Por ejemplo, 
--    λ> mayoresCrecientes [3,2,6,4,5,1]
--    [[3,4,5],[2,4,5]]
--    λ> mayoresCrecientes [3,2,3,2,3,1]
--    [[2,3],[2,3],[2,3]]
--    λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]
--    [[10,22,33,50,60,80],[10,22,33,41,60,80]]
--    λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
--    [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]
mayoresCrecientes :: Ord a => [a] -> [[a]]
mayoresCrecientes xs =
  [ys | ys <- xss
      , length ys == m]
  where xss = sublistasCrecientes xs
        m   = maximum (map length xss)

-- (sublistasCrecientes xs) es la lista de las sublistas crecientes de
-- xs. Por ejemplo,
--    λ> sublistasCrecientes [3,2,5]
--    [[3,5],[3],[2,5],[2],[5],[]]
sublistasCrecientes :: Ord a => [a] -> [[a]]
sublistasCrecientes []  = [[]]
sublistasCrecientes (x:xs) =
  [x:ys | ys <- yss, null ys || x < head ys] ++ yss
  where yss = sublistasCrecientes xs

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

longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente2 xs =
  longitudSCM xs (sort (nub xs))
  
-- (longitudSCM xs ys) es la longitud de la subsecuencia máxima de xs e
-- ys. Por ejemplo, 
--   longitudSCM "amapola" "matamoscas" == 4
--   longitudSCM "atamos" "matamoscas"  == 6
--   longitudSCM "aaa" "bbbb"           == 0
longitudSCM :: Eq a => [a] -> [a] -> Int
longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)
  where n = length xs
        m = length ys

-- (matrizLongitudSCM xs ys) es la matriz de orden (n+1)x(m+1) (donde n
-- y m son los números de elementos de xs e ys, respectivamente) tal que
-- el valor en la posición (i,j) es la longitud de la SCM de los i
-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,
--    λ> elems (matrizLongitudSCM "amapola" "matamoscas")
--    [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,
--     0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,
--     0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]
-- Gráficamente,
--       m a t a m o s c a s
--    [0,0,0,0,0,0,0,0,0,0,0,
-- a   0,0,1,1,1,1,1,1,1,1,1,
-- m   0,1,1,1,1,2,2,2,2,2,2,
-- a   0,1,2,2,2,2,2,2,2,3,3,
-- p   0,1,2,2,2,2,2,2,2,3,3,
-- o   0,1,2,2,2,2,3,3,3,3,3,
-- l   0,1,2,2,2,2,3,3,3,3,3,
-- a   0,1,2,2,3,3,3,3,3,4,4]
matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int
matrizLongitudSCM xs ys = q
  where
    n = length xs
    m = length ys
    v = listArray (1,n) xs
    w = listArray (1,m) ys
    q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]
      where f 0 _ = 0
            f _ 0 = 0
            f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)
                  | otherwise      = max (q ! (i-1,j)) (q ! (i,j-1))
  
-- 3ª solución
-- ===========

longitudMayorSublistaCreciente3 :: Ord a => [a] -> Int
longitudMayorSublistaCreciente3 xs =
  maximum (elems (vectorlongitudMayorSublistaCreciente xs))

-- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n
-- (donde n es el tamaño de xs) tal que el valor i-ésimo es la longitud
-- de la sucesión más larga que termina en el elemento i-ésimo de
-- xs. Por ejemplo,  
--    λ> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1]
--    array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)]
vectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int
vectorlongitudMayorSublistaCreciente xs = v
  where v = array (1,n) [(i,f i) | i <- [1..n]]
        n = length xs
        w = listArray (1,n) xs
        f 1 = 1
        f i | null ls   = 1
            | otherwise = 1 + maximum ls
          where ls = [v ! j | j <-[1..i-1], w ! j < w ! i]

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

--    λ> longitudMayorSublistaCreciente1 [1..20]
--    20
--    (4.60 secs, 597,014,240 bytes)
--    λ> longitudMayorSublistaCreciente2 [1..20]
--    20
--    (0.03 secs, 361,384 bytes)
--    λ> longitudMayorSublistaCreciente3 [1..20]
--    20
--    (0.03 secs, 253,944 bytes)
--    
--    λ> longitudMayorSublistaCreciente2 [1..2000]
--    2000
--    (8.00 secs, 1,796,495,488 bytes)
--    λ> longitudMayorSublistaCreciente3 [1..2000]
--    2000
--    (5.12 secs, 1,137,667,496 bytes)
--    
--    λ> longitudMayorSublistaCreciente1 [1000,999..1]
--    1
--    (0.95 secs, 97,029,328 bytes)
--    λ> longitudMayorSublistaCreciente2 [1000,999..1]
--    1
--    (7.48 secs, 1,540,857,208 bytes)
--    λ> longitudMayorSublistaCreciente3 [1000,999..1]
--    1
--    (0.86 secs, 160,859,128 bytes)
--    
--    λ> longitudMayorSublistaCreciente1 (show (2^300))
--    10
--    (7.90 secs, 887,495,368 bytes)
--    λ> longitudMayorSublistaCreciente2 (show (2^300))
--    10
--    (0.04 secs, 899,152 bytes)
--    λ> longitudMayorSublistaCreciente3 (show (2^300))
--    10
--    (0.04 secs, 1,907,936 bytes)
--    
--    λ> longitudMayorSublistaCreciente2 (show (2^6000))
--    10
--    (0.06 secs, 9,950,592 bytes)
--    λ> longitudMayorSublistaCreciente3 (show (2^6000))
--    10
--    (3.46 secs, 686,929,744 bytes)
--    
--    λ> import System.Random
--    (0.00 secs, 0 bytes)
--    λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
--    (0.02 secs, 1,993,032 bytes)
--    λ> longitudMayorSublistaCreciente2 xs
--    61
--    (7.73 secs, 1,538,771,392 bytes)
--    λ> longitudMayorSublistaCreciente3 xs
--    61
--    (1.04 secs, 212,538,648 bytes)
--    λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]
--    (0.03 secs, 1,993,032 bytes)
--    λ> longitudMayorSublistaCreciente2 xs
--    57
--    (7.56 secs, 1,538,573,680 bytes)
--    λ> longitudMayorSublistaCreciente3 xs
--    57
--    (1.05 secs, 212,293,984 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

import Data.List (nub, sort)

import Data.Array (Array, (!), array, elems, listArray)

-- 1ª solución

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

longitudMayorSublistaCreciente1 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente1 =

length . head . mayoresCrecientes

-- (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs

-- de mayor longitud. Por ejemplo,

-- λ> mayoresCrecientes [3,2,6,4,5,1]

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

-- λ> mayoresCrecientes [3,2,3,2,3,1]

-- [[2,3],[2,3],[2,3]]

-- λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]

-- [[10,22,33,50,60,80],[10,22,33,41,60,80]]

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

-- [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]

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

mayoresCrecientes xs =

[ys | ys <- xss

, length ys == m]

where xss = sublistasCrecientes xs

m = maximum (map length xss)

-- (sublistasCrecientes xs) es la lista de las sublistas crecientes de

-- xs. Por ejemplo,

-- λ> sublistasCrecientes [3,2,5]

-- [[3,5],[3],[2,5],[2],[5],[]]

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

sublistasCrecientes [] = [[]]

sublistasCrecientes (x:xs) =

[x:ys | ys <- yss, null ys || x < head ys] ++ yss

where yss = sublistasCrecientes xs

-- 2ª solución

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

longitudMayorSublistaCreciente2 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente2 xs =

longitudSCM xs (sort (nub xs))

-- (longitudSCM xs ys) es la longitud de la subsecuencia máxima de xs e

-- ys. Por ejemplo,

-- longitudSCM "amapola" "matamoscas" == 4

-- longitudSCM "atamos" "matamoscas" == 6

-- longitudSCM "aaa" "bbbb" == 0

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

longitudSCM xs ys = (matrizLongitudSCM xs ys) ! (n,m)

where n = length xs

m = length ys

-- (matrizLongitudSCM xs ys) es la matriz de orden (n+1)x(m+1) (donde n

-- y m son los números de elementos de xs e ys, respectivamente) tal que

-- el valor en la posición (i,j) es la longitud de la SCM de los i

-- primeros elementos de xs y los j primeros elementos de ys. Por ejemplo,

-- λ> elems (matrizLongitudSCM "amapola" "matamoscas")

-- [0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,2,2,2,2,2,2,

-- 0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,2,2,2,3,3,0,1,2,2,2,2,3,3,3,3,3,

-- 0,1,2,2,2,2,3,3,3,3,3,0,1,2,2,3,3,3,3,3,4,4]

-- Gráficamente,

-- m a t a m o s c a s

-- [0,0,0,0,0,0,0,0,0,0,0,

-- a 0,0,1,1,1,1,1,1,1,1,1,

-- m 0,1,1,1,1,2,2,2,2,2,2,

-- a 0,1,2,2,2,2,2,2,2,3,3,

-- p 0,1,2,2,2,2,2,2,2,3,3,

-- o 0,1,2,2,2,2,3,3,3,3,3,

-- l 0,1,2,2,2,2,3,3,3,3,3,

-- a 0,1,2,2,3,3,3,3,3,4,4]

matrizLongitudSCM :: Eq a => [a] -> [a] -> Array (Int,Int) Int

matrizLongitudSCM xs ys = q

where

n = length xs

m = length ys

v = listArray (1,n) xs

w = listArray (1,m) ys

q = array ((0,0),(n,m)) [((i,j), f i j) | i <- [0..n], j <- [0..m]]

where f 0 _ = 0

f _ 0 = 0

f i j | v ! i == w ! j = 1 + q ! (i-1,j-1)

| otherwise = max (q ! (i-1,j)) (q ! (i,j-1))

-- 3ª solución

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

longitudMayorSublistaCreciente3 :: Ord a => [a] -> Int

longitudMayorSublistaCreciente3 xs =

maximum (elems (vectorlongitudMayorSublistaCreciente xs))

-- (vectorlongitudMayorSublistaCreciente xs) es el vector de longitud n

-- (donde n es el tamaño de xs) tal que el valor i-ésimo es la longitud

-- de la sucesión más larga que termina en el elemento i-ésimo de

-- xs. Por ejemplo,

-- λ> vectorlongitudMayorSublistaCreciente [3,2,6,4,5,1]

-- array (1,6) [(1,1),(2,1),(3,2),(4,2),(5,3),(6,1)]

vectorlongitudMayorSublistaCreciente :: Ord a => [a] -> Array Int Int

vectorlongitudMayorSublistaCreciente xs = v

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

n = length xs

w = listArray (1,n) xs

f 1 = 1

f i | null ls = 1

| otherwise = 1 + maximum ls

where ls = [v ! j | j <-[1..i-1], w ! j < w ! i]

-- Comparación de eficiencia

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

-- λ> longitudMayorSublistaCreciente1 [1..20]

-- 20

-- (4.60 secs, 597,014,240 bytes)

-- λ> longitudMayorSublistaCreciente2 [1..20]

-- 20

-- (0.03 secs, 361,384 bytes)

-- λ> longitudMayorSublistaCreciente3 [1..20]

-- 20

-- (0.03 secs, 253,944 bytes)

-- λ> longitudMayorSublistaCreciente2 [1..2000]

-- 2000

-- (8.00 secs, 1,796,495,488 bytes)

-- λ> longitudMayorSublistaCreciente3 [1..2000]

-- 2000

-- (5.12 secs, 1,137,667,496 bytes)

-- λ> longitudMayorSublistaCreciente1 [1000,999..1]

-- 1

-- (0.95 secs, 97,029,328 bytes)

-- λ> longitudMayorSublistaCreciente2 [1000,999..1]

-- 1

-- (7.48 secs, 1,540,857,208 bytes)

-- λ> longitudMayorSublistaCreciente3 [1000,999..1]

-- 1

-- (0.86 secs, 160,859,128 bytes)

-- λ> longitudMayorSublistaCreciente1 (show (2^300))

-- 10

-- (7.90 secs, 887,495,368 bytes)

-- λ> longitudMayorSublistaCreciente2 (show (2^300))

-- 10

-- (0.04 secs, 899,152 bytes)

-- λ> longitudMayorSublistaCreciente3 (show (2^300))

-- 10

-- (0.04 secs, 1,907,936 bytes)

-- λ> longitudMayorSublistaCreciente2 (show (2^6000))

-- 10

-- (0.06 secs, 9,950,592 bytes)

-- λ> longitudMayorSublistaCreciente3 (show (2^6000))

-- 10

-- (3.46 secs, 686,929,744 bytes)

-- λ> import System.Random

-- (0.00 secs, 0 bytes)

-- λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]

-- (0.02 secs, 1,993,032 bytes)

-- λ> longitudMayorSublistaCreciente2 xs

-- 61

-- (7.73 secs, 1,538,771,392 bytes)

-- λ> longitudMayorSublistaCreciente3 xs

-- 61

-- (1.04 secs, 212,538,648 bytes)

-- λ> xs <- sequence [randomRIO (0,10^6) | _ <- [1..10^3]]

-- (0.03 secs, 1,993,032 bytes)

-- λ> longitudMayorSublistaCreciente2 xs

-- 57

-- (7.56 secs, 1,538,573,680 bytes)

-- λ> longitudMayorSublistaCreciente3 xs

-- 57

-- (1.05 secs, 212,293,984 bytes)

Mayores sublistas crecientes

PorJosé A. Alonso 22-marzo-201830-marzo-2018

Definir la función

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

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

tal que (mayoresCrecientes xs) es la lista de las sublistas crecientes de xs de mayor longitud. Por ejemplo,

   λ> mayoresCrecientes [3,2,6,4,5,1]
   [[3,4,5],[2,4,5]]
   λ> mayoresCrecientes [3,2,3,2,3,1]
   [[2,3],[2,3],[2,3]]
   λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]
   [[10,22,33,50,60,80],[10,22,33,41,60,80]]
   λ> mayoresCrecientes [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]
   [[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]
   λ> length (head (mayoresCrecientes (show (2^300))))
   10

λ> mayoresCrecientes [3,2,6,4,5,1]

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

λ> mayoresCrecientes [3,2,3,2,3,1]

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

λ> mayoresCrecientes [10,22,9,33,21,50,41,60,80]

[[10,22,33,50,60,80],[10,22,33,41,60,80]]

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

[[0,4,6,9,13,15],[0,2,6,9,13,15],[0,4,6,9,11,15],[0,2,6,9,11,15]]

λ> length (head (mayoresCrecientes (show (2^300))))

Soluciones

import Data.List (subsequences)

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

mayoresCrecientes1 :: Ord a => [a] -> [[a]]
mayoresCrecientes1 xs =
  [ys | ys <- xss
      , length ys == m]
  where xss = sublistasCrecientes xs
        m   = maximum (map length xss)

-- (sublistasCrecientes1 xs) es la lista de las sublistas crecientes de
-- xs. Por ejemplo,
--    λ> sublistasCrecientes [3,2,5]
--    [[],[3],[2],[5],[3,5],[2,5]]
sublistasCrecientes :: Ord a => [a] -> [[a]]
sublistasCrecientes xs =
  [ys | ys <- subsequences xs
      , esCreciente ys]

-- (esCreciente xs) se verifica si la lista xs es creciente. Por
-- ejemplo,  
--    esCreciente [2,3,5]  ==  True
--    esCreciente [2,3,1]  ==  False
--    esCreciente [2,3,3]  ==  False
esCreciente :: Ord a => [a] -> Bool
esCreciente (x:y:zs) = x < y && esCreciente (y:zs)
esCreciente _        = True

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

mayoresCrecientes2 :: Ord a => [a] -> [[a]]
mayoresCrecientes2 xs =
  [ys | ys <- xss
      , length ys == m]
  where xss = sublistasCrecientes2 xs
        m   = maximum (map length xss)

-- (sublistasCrecientes2 xs) es la lista de las sublistas crecientes de
-- xs. Por ejemplo,
--    λ> sublistasCrecientes2 [3,2,5]
--    [[3,5],[3],[2,5],[2],[5],[]]
sublistasCrecientes2 :: Ord a => [a] -> [[a]]
sublistasCrecientes2 []  = [[]]
sublistasCrecientes2 (x:xs) =
  [x:ys | ys <- yss, null ys || x < head ys] ++ yss
  where yss = sublistasCrecientes2 xs

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

--    λ> length (head (mayoresCrecientes1 (show (2^70))))
--    5
--    (10.93 secs, 1,958,822,896 bytes)
--    λ> length (head (mayoresCrecientes2 (show (2^70))))
--    5
--    (0.02 secs, 0 bytes)

import Data.List (subsequences)

-- 1ª solución

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

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

mayoresCrecientes1 xs =

[ys | ys <- xss

, length ys == m]

where xss = sublistasCrecientes xs

m = maximum (map length xss)

-- (sublistasCrecientes1 xs) es la lista de las sublistas crecientes de

-- xs. Por ejemplo,

-- λ> sublistasCrecientes [3,2,5]

-- [[],[3],[2],[5],[3,5],[2,5]]

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

sublistasCrecientes xs =

[ys | ys <- subsequences xs

, esCreciente ys]

-- (esCreciente xs) se verifica si la lista xs es creciente. Por

-- ejemplo,

-- esCreciente [2,3,5] == True

-- esCreciente [2,3,1] == False

-- esCreciente [2,3,3] == False

esCreciente :: Ord a => [a] -> Bool

esCreciente (x:y:zs) = x < y && esCreciente (y:zs)

esCreciente _ = True

-- 2ª solución

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

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

mayoresCrecientes2 xs =

[ys | ys <- xss

, length ys == m]

where xss = sublistasCrecientes2 xs

m = maximum (map length xss)

-- (sublistasCrecientes2 xs) es la lista de las sublistas crecientes de

-- xs. Por ejemplo,

-- λ> sublistasCrecientes2 [3,2,5]

-- [[3,5],[3],[2,5],[2],[5],[]]

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

sublistasCrecientes2 [] = [[]]

sublistasCrecientes2 (x:xs) =

[x:ys | ys <- yss, null ys || x < head ys] ++ yss

where yss = sublistasCrecientes2 xs

-- Comparación de eficiencia

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

-- λ> length (head (mayoresCrecientes1 (show (2^70))))

-- 5

-- (10.93 secs, 1,958,822,896 bytes)

-- λ> length (head (mayoresCrecientes2 (show (2^70))))

-- 5

-- (0.02 secs, 0 bytes)

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.

Nodos con máxima suma de hijos

PorJosé A. Alonso 1-marzo-201830-marzo-2020

Los árboles se pueden representar mediante el siguiente tipo de datos

   data Arbol a = N a [Arbol a]
                  deriving Show

1 2	data Arbol a = N a [Arbol a] deriving Show

Por ejemplo, los árboles

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

1 3

/ \ /|\

2 3 / | \

| 5 4 7

4 | /|\

6 2 8 6

se representan por

   ej1, ej2 :: Arbol Int
   ej1 = N 1 [N 2 [], N 3 [N 4 []]]
   ej2 = N 3 [N 5 [N 6 []], 
              N 4 [], 
              N 7 [N 2 [], N 8 [], N 6 []]]

ej1, ej2 :: Arbol Int

ej1 = N 1 [N 2 [], N 3 [N 4 []]]

ej2 = N 3 [N 5 [N 6 []],

N 4 [],

N 7 [N 2 [], N 8 [], N 6 []]]

Definir la función

   nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

1	nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

tal que (nodosSumaMaxima a) es la lista de los nodos del árbol a cuyos hijos tienen máxima suma. Por ejemplo,

   nodosSumaMaxima ej1  ==  [1]
   nodosSumaMaxima ej2  ==  [7,3]

1 2	nodosSumaMaxima ej1 == [1] nodosSumaMaxima ej2 == [7,3]

Soluciones

import Data.List     (groupBy, sort)
import Data.Function (on)

data Arbol a = N a [Arbol a]
  deriving Show

ej1, ej2 :: Arbol Int
ej1 = N 1 [N 2 [], N 3 [N 4 []]]
ej2 = N 3 [N 5 [N 6 []], 
           N 4 [], 
           N 7 [N 2 [], N 8 [], N 6 []]]

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

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima a =
  [x | (s,x) <- ns, s == m]
  where ns = reverse (sort (nodosSumas a))
        m  = fst (head ns)

-- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del
-- árbol x y s es la suma de sus hijos. Por ejemplo,  
--    λ> nodosSumas ej1
--    [(5,1),(0,2),(4,3),(0,4)]
--    λ> nodosSumas ej2
--    [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)]
nodosSumas :: Num t => Arbol t -> [(t,t)]
nodosSumas (N x []) = [(0,x)]
nodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as

-- (raices b) es la lista de las raíces del bosque b. Por ejemplo,
--    raices [ej1,ej2]  ==  [1,3]
raices :: [Arbol t] -> [t]
raices = map raiz

-- (raiz a) es la raíz del árbol a. Por ejemplo,
--    raiz ej1  ==  1
--    raiz ej2  ==  3
raiz :: Arbol t -> t
raiz (N x _) = x

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

nodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima2 a =
  [x | (s,x) <- ns, s == m]
  where ns = sort (nodosOpSumas a)
        m  = fst (head ns)

-- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del
-- árbol x y s es el opuesto de la suma de sus hijos. Por ejemplo,  
--    λ> nodosOpSumas ej1
--    [(-5,1),(0,2),(-4,3),(0,4)]
--    λ> nodosOpSumas ej2
--    [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)]
nodosOpSumas :: Num t => Arbol t -> [(t,t)]
nodosOpSumas (N x []) = [(0,x)]
nodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as


-- 3ª solución
-- ===========

nodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima3 a =
  [x | (s,x) <- ns, s == m]
  where ns = sort (nodosOpSumas a)
        m  = fst (head ns)

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

nodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima4 a =
  map snd (head (groupBy (\p q -> fst p == fst q)
                         (sort (nodosOpSumas a))))

-- 5ª solución
-- ===========

nodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima5 a =
  map snd (head (groupBy ((==) `on` fst)
                         (sort (nodosOpSumas a))))

-- 6ª solución
-- ===========

nodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t]
nodosSumaMaxima6 =
  map snd
  . head
  . groupBy ((==) `on` fst)
  . sort
  . nodosOpSumas

import Data.List (groupBy, sort)

import Data.Function (on)

data Arbol a = N a [Arbol a]

deriving Show

ej1, ej2 :: Arbol Int

ej1 = N 1 [N 2 [], N 3 [N 4 []]]

ej2 = N 3 [N 5 [N 6 []],

N 4 [],

N 7 [N 2 [], N 8 [], N 6 []]]

-- 1ª solución

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

nodosSumaMaxima :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima a =

[x | (s,x) <- ns, s == m]

where ns = reverse (sort (nodosSumas a))

m = fst (head ns)

-- (nodosSumas x) es la lista de los pares (s,n) donde n es un nodo del

-- árbol x y s es la suma de sus hijos. Por ejemplo,

-- λ> nodosSumas ej1

-- [(5,1),(0,2),(4,3),(0,4)]

-- λ> nodosSumas ej2

-- [(16,3),(6,5),(0,6),(0,4),(16,7),(0,2),(0,8),(0,6)]

nodosSumas :: Num t => Arbol t -> [(t,t)]

nodosSumas (N x []) = [(0,x)]

nodosSumas (N x as) = (sum (raices as),x) : concatMap nodosSumas as

-- (raices b) es la lista de las raíces del bosque b. Por ejemplo,

-- raices [ej1,ej2] == [1,3]

raices :: [Arbol t] -> [t]

raices = map raiz

-- (raiz a) es la raíz del árbol a. Por ejemplo,

-- raiz ej1 == 1

-- raiz ej2 == 3

raiz :: Arbol t -> t

raiz (N x _) = x

-- 2ª solución

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

nodosSumaMaxima2 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima2 a =

[x | (s,x) <- ns, s == m]

where ns = sort (nodosOpSumas a)

m = fst (head ns)

-- (nodosOpSumas x) es la lista de los pares (s,n) donde n es un nodo del

-- árbol x y s es el opuesto de la suma de sus hijos. Por ejemplo,

-- λ> nodosOpSumas ej1

-- [(-5,1),(0,2),(-4,3),(0,4)]

-- λ> nodosOpSumas ej2

-- [(-16,3),(-6,5),(0,6),(0,4),(-16,7),(0,2),(0,8),(0,6)]

nodosOpSumas :: Num t => Arbol t -> [(t,t)]

nodosOpSumas (N x []) = [(0,x)]

nodosOpSumas (N x as) = (-sum (raices as),x) : concatMap nodosOpSumas as

-- 3ª solución

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

nodosSumaMaxima3 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima3 a =

[x | (s,x) <- ns, s == m]

where ns = sort (nodosOpSumas a)

m = fst (head ns)

-- 4ª solución

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

nodosSumaMaxima4 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima4 a =

map snd (head (groupBy (\p q -> fst p == fst q)

(sort (nodosOpSumas a))))

-- 5ª solución

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

nodosSumaMaxima5 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima5 a =

map snd (head (groupBy ((==) `on` fst)

(sort (nodosOpSumas a))))

-- 6ª solución

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

nodosSumaMaxima6 :: (Num t, Ord t) => Arbol t -> [t]

nodosSumaMaxima6 =

map snd

. head

. groupBy ((==) `on` fst)

. sort

. nodosOpSumas

Números cuyos factoriales son divisibles por x pero no por y

PorJosé A. Alonso 28-febrero-20187-marzo-2018

Hay 3 números (el 2, 3 y 4) cuyos factoriales son divisibles por 2 pero no por 5. Análogamente, hay números 5 (el 5, 6, 7, 8, 9) cuyos factoriales son divisibles por 15 pero no por 25.

Definir la función

   nNumerosConFactorialesDivisibles :: Integer -> Integer -> Integer

1	nNumerosConFactorialesDivisibles :: Integer -> Integer -> Integer

tal que (nNumerosConFactorialesDivisibles x y) es la cantidad de números cuyo factorial es divisible por x pero no por y. Por ejemplo,

  nNumerosConFactorialesDivisibles 2   5     ==  3
  nNumerosConFactorialesDivisibles 15  25    ==  5
  nNumerosConFactorialesDivisibles 100 2000  ==  5

nNumerosConFactorialesDivisibles 2 5 == 3

nNumerosConFactorialesDivisibles 15 25 == 5

nNumerosConFactorialesDivisibles 100 2000 == 5

Soluciones

import Data.List (genericLength)

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

nNumerosConFactorialesDivisibles :: Integer -> Integer -> Integer
nNumerosConFactorialesDivisibles x y =
  genericLength (numerosConFactorialesDivisibles x y)

-- (numerosConFactorialesDivisibles x y) es la lista de números
-- divisibles por el factorial de x pero no divisibles por el 
-- factorial de y. Por ejemplo,
--   numerosConFactorialesDivisibles 2  5   ==  [2,3,4]
--   numerosConFactorialesDivisibles 15 25  ==  [5,6,7,8,9]
numerosConFactorialesDivisibles :: Integer -> Integer -> [Integer]
numerosConFactorialesDivisibles x y =
  [z | z <- [0..y-1]
     , factorial z `mod` x == 0
     , factorial z `mod` y /= 0]

-- (factorial n) es el factorial de n. Por ejemplo, 
--   factorial 4  ==  24
factorial :: Integer -> Integer
factorial n = product [1..n]

-- 2ª solución (usando la función de Smarandache)
-- ==============================================

nNumerosConFactorialesDivisibles2 :: Integer -> Integer -> Integer
nNumerosConFactorialesDivisibles2 x y =
  max 0 (smarandache y - smarandache x)

--(smarandache n) es el menor número cuyo factorial es divisible por
-- n. Por ejemplo,   
--    smarandache 8   ==  4
--    smarandache 10  ==  5
--    smarandache 16  ==  6
smarandache :: Integer -> Integer
smarandache x =
  head [n | (n,y) <- zip [0..] factoriales
          , y `mod` x == 0]

-- factoriales es la lista de los factoriales. Por ejemplo, 
--    λ> take 12 factoriales
--    [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]

-- Comparación de eficiencia
--    λ> nNumerosConFactorialesDivisibles 100 2000
--    5
--    (2.70 secs, 3,933,938,648 bytes)
--    λ> nNumerosConFactorialesDivisibles2 100 2000
--    5
--    (0.01 secs, 148,200 bytes)

import Data.List (genericLength)

-- 1ª solución

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

nNumerosConFactorialesDivisibles :: Integer -> Integer -> Integer

nNumerosConFactorialesDivisibles x y =

genericLength (numerosConFactorialesDivisibles x y)

-- (numerosConFactorialesDivisibles x y) es la lista de números

-- divisibles por el factorial de x pero no divisibles por el

-- factorial de y. Por ejemplo,

-- numerosConFactorialesDivisibles 2 5 == [2,3,4]

-- numerosConFactorialesDivisibles 15 25 == [5,6,7,8,9]

numerosConFactorialesDivisibles :: Integer -> Integer -> [Integer]

numerosConFactorialesDivisibles x y =

[z | z <- [0..y-1]

, factorial z `mod` x == 0

, factorial z `mod` y /= 0]

-- (factorial n) es el factorial de n. Por ejemplo,

-- factorial 4 == 24

factorial :: Integer -> Integer

factorial n = product [1..n]

-- 2ª solución (usando la función de Smarandache)

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

nNumerosConFactorialesDivisibles2 :: Integer -> Integer -> Integer

nNumerosConFactorialesDivisibles2 x y =

max 0 (smarandache y - smarandache x)

--(smarandache n) es el menor número cuyo factorial es divisible por

-- n. Por ejemplo,

-- smarandache 8 == 4

-- smarandache 10 == 5

-- smarandache 16 == 6

smarandache :: Integer -> Integer

smarandache x =

head [n | (n,y) <- zip [0..] factoriales

, y `mod` x == 0]

-- factoriales es la lista de los factoriales. Por ejemplo,

-- λ> take 12 factoriales

-- [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]

factoriales :: [Integer]

factoriales = 1 : scanl1 (*) [1..]

-- Comparación de eficiencia

-- λ> nNumerosConFactorialesDivisibles 100 2000

-- 5

-- (2.70 secs, 3,933,938,648 bytes)

-- λ> nNumerosConFactorialesDivisibles2 100 2000

-- 5

-- (0.01 secs, 148,200 bytes)

La función de Smarandache

PorJosé A. Alonso 27-febrero-20186-marzo-2018

La función de Smarandache, también conocida como la función de Kempner, es la función que asigna a cada número entero positivo n el menor número cuyo factorial es divisible por n y se representa por S(n). Por ejemplo, el número 8 no divide a 1!, 2!, 3!, pero sí divide 4!; por tanto, S(8) = 4.

Definir las funciones

   smarandache        :: Integer -> Integer
   graficaSmarandache :: Integer -> IO ()

1 2	smarandache :: Integer -> Integer graficaSmarandache :: Integer -> IO ()

tales que

(smarandache n) es el menor número cuyo factorial es divisible por n. Por ejemplo,

     smarandache 8   ==  4
     smarandache 10  ==  5
     smarandache 16  ==  6

smarandache 8 == 4

smarandache 10 == 5

smarandache 16 == 6

(graficaSmarandache n) dibuja la gráfica de los n primeros términos de la sucesión de Smarandache. Por ejemplo, (graficaSmarandache 100) dibuja

(graficaSmarandache 500) dibuja

Soluciones

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

smarandache :: Integer -> Integer
smarandache x =
  head [n | (n,y) <- zip [0..] factoriales
          , y `mod` x == 0]

-- factoriales es la lista de los factoriales. Por ejemplo, 
--    λ> take 12 factoriales
--    [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]
factoriales :: [Integer]
factoriales = 1 : scanl1 (*) [1..]

graficaSmarandache :: Integer -> IO ()
graficaSmarandache n =
  plotList [Key Nothing
           , PNG ("La_funcion_de_Smarandache_" ++ show n ++ ".png")
           ]
           (map smarandache [1..n])

import Data.List (genericLength)

import Graphics.Gnuplot.Simple

smarandache :: Integer -> Integer

smarandache x =

head [n | (n,y) <- zip [0..] factoriales

, y `mod` x == 0]

-- factoriales es la lista de los factoriales. Por ejemplo,

-- λ> take 12 factoriales

-- [1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800]

factoriales :: [Integer]

factoriales = 1 : scanl1 (*) [1..]

graficaSmarandache :: Integer -> IO ()

graficaSmarandache n =

plotList [Key Nothing

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

]

(map smarandache [1..n])

Dígitos iniciales

PorJosé A. Alonso 2-febrero-201819-febrero-2018

Definir las funciones

   digitosIniciales        :: [Int]
   graficaDigitosIniciales :: Int -> IO ()

1 2	digitosIniciales :: [Int] graficaDigitosIniciales :: Int -> IO ()

tales que

digitosIniciales es la lista de los dígitos iniciales de los números naturales. Por ejemplo,

     λ> take 100 digitosIniciales
     [0,1,2,3,4,5,6,7,8,9,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,
      3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,
      6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,
      9,9,9,9,9,9,9,9,9,9]

λ> take 100 digitosIniciales

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

3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,

6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,

9,9,9,9,9,9,9,9,9,9]

(graficaDigitosIniciales n) dibuja la gráfica de los primeros n términos de la sucesión digitosIniciales. Por ejemplo, (graficaDigitosIniciales 100) dibuja

y (graficaDigitosIniciales 1000) dibuja

Soluciones

import Graphics.Gnuplot.Simple

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

digitosIniciales :: [Int]
digitosIniciales = map digitoInicial [0..]

digitoInicial :: Integer -> Int
digitoInicial n = read [head (show n)]

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

digitosIniciales2 :: [Int]
digitosIniciales2 = map (read . return . head . show) [0..]

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

digitosIniciales3 :: [Int]
digitosIniciales3 = map digitoInicial3 [0..]

digitoInicial3 :: Integer -> Int
digitoInicial3 = fromInteger . until (< 10) (`div` 10)

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

digitosIniciales4 :: [Int]
digitosIniciales4 = map (fromInteger . until (< 10) (`div` 10)) [0..]

-- 5ª definición
-- =============

digitosIniciales5 :: [Int]
digitosIniciales5 =
  0 : concat [replicate k x | k <- [10^n | n <- [0..]]
                            , x <- [1..9]]

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

--    λ> digitosIniciales !! (2*10^6)
--    2
--    (0.46 secs, 320,145,984 bytes)
--    λ> digitosIniciales2 !! (2*10^6)
--    2
--    (0.46 secs, 320,143,288 bytes)
--    λ> digitosIniciales3 !! (2*10^6)
--    2
--    (0.17 secs, 320,139,216 bytes)
--    λ> digitosIniciales4 !! (2*10^6)
--    2
--    (0.55 secs, 320,139,248 bytes)
--    λ> digitosIniciales5 !! (2*10^6)
--    2
--    (0.12 secs, 224,158,992 bytes)

graficaDigitosIniciales :: Int -> IO ()
graficaDigitosIniciales n =
  plotList [ Key Nothing
           , Title ("graficaDigitosIniciales " ++ show n)
           , PNG ("Digitos_iniciales_" ++ show n ++ ".png" )
           ]
           (take n digitosIniciales)

import Graphics.Gnuplot.Simple

-- 1ª definición

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

digitosIniciales :: [Int]

digitosIniciales = map digitoInicial [0..]

digitoInicial :: Integer -> Int

digitoInicial n = read [head (show n)]

-- 2ª definición

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

digitosIniciales2 :: [Int]

digitosIniciales2 = map (read . return . head . show) [0..]

-- 3ª definición

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

digitosIniciales3 :: [Int]

digitosIniciales3 = map digitoInicial3 [0..]

digitoInicial3 :: Integer -> Int

digitoInicial3 = fromInteger . until (< 10) (`div` 10)

-- 4ª definición

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

digitosIniciales4 :: [Int]

digitosIniciales4 = map (fromInteger . until (< 10) (`div` 10)) [0..]

-- 5ª definición

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

digitosIniciales5 :: [Int]

digitosIniciales5 =

0 : concat [replicate k x | k <- [10^n | n <- [0..]]

, x <- [1..9]]

-- Comparación de eficiencia

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

-- λ> digitosIniciales !! (2*10^6)

-- 2

-- (0.46 secs, 320,145,984 bytes)

-- λ> digitosIniciales2 !! (2*10^6)

-- 2

-- (0.46 secs, 320,143,288 bytes)

-- λ> digitosIniciales3 !! (2*10^6)

-- 2

-- (0.17 secs, 320,139,216 bytes)

-- λ> digitosIniciales4 !! (2*10^6)

-- 2

-- (0.55 secs, 320,139,248 bytes)

-- λ> digitosIniciales5 !! (2*10^6)

-- 2

-- (0.12 secs, 224,158,992 bytes)

graficaDigitosIniciales :: Int -> IO ()

graficaDigitosIniciales n =

plotList [ Key Nothing

, Title ("graficaDigitosIniciales " ++ show n)

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

]

(take n digitosIniciales)

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

Terna pitagórica a partir de un lado

PorJosé A. Alonso 19-enero-201819-febrero-2018

Una terna pitagórica con primer lado x es una terna (x,y,z) tal que x^2 + y^2 = z^2. Por ejemplo, las ternas pitagóricas con primer lado 16 son (16,12,20), (16,30,34) y (16,63,65).

Definir las funciones

   ternasPitagoricas      :: Integer -> [(Integer,Integer,Integer)]
   mayorTernaPitagorica   :: Integer -> (Integer,Integer,Integer)
   graficaMayorHipotenusa :: Integer -> IO ()

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

mayorTernaPitagorica :: Integer -> (Integer,Integer,Integer)

graficaMayorHipotenusa :: Integer -> IO ()

tales que

(ternasPitgoricas x) es la lista de las ternas pitagóricas con primer lado x. Por ejemplo,

     ternasPitagoricas 16 == [(16,12,20),(16,30,34),(16,63,65)]
     ternasPitagoricas 20 == [(20,15,25),(20,21,29),(20,48,52),(20,99,101)]
     ternasPitagoricas 25 == [(25,60,65),(25,312,313)]
     ternasPitagoricas 26 == [(26,168,170)]

ternasPitagoricas 16 == [(16,12,20),(16,30,34),(16,63,65)]

ternasPitagoricas 20 == [(20,15,25),(20,21,29),(20,48,52),(20,99,101)]

ternasPitagoricas 25 == [(25,60,65),(25,312,313)]

ternasPitagoricas 26 == [(26,168,170)]

(mayorTernaPitagorica x) es la mayor de las ternas pitagóricas con primer lado x. Por ejemplo,

     mayorTernaPitagorica 16     ==  (16,63,65)
     mayorTernaPitagorica 20     ==  (20,99,101)
     mayorTernaPitagorica 25     ==  (25,312,313)
     mayorTernaPitagorica 26     ==  (26,168,170)
     mayorTernaPitagorica 2018   ==  (2018,1018080,1018082)
     mayorTernaPitagorica 2019   ==  (2019,2038180,2038181)

mayorTernaPitagorica 16 == (16,63,65)

mayorTernaPitagorica 20 == (20,99,101)

mayorTernaPitagorica 25 == (25,312,313)

mayorTernaPitagorica 26 == (26,168,170)

mayorTernaPitagorica 2018 == (2018,1018080,1018082)

mayorTernaPitagorica 2019 == (2019,2038180,2038181)

(graficaMayorHipotenusa n) dibuja la gráfica de las sucesión de las mayores hipotenusas de las ternas pitagóricas con primer lado x, para x entre 3 y n. Por ejemplo, (graficaMayorHipotenusa 100) dibuja

Soluciones

import Graphics.Gnuplot.Simple

-- Definición de ternasPitagoricas
-- ===============================

ternasPitagoricas :: Integer -> [(Integer,Integer,Integer)]
ternasPitagoricas x =
  [(x,y,z) | y <- [1..(x^ 2 - 1) `div` 2 ]
           , z <- raizCuadrada (x^2 + y^2)]

-- La justificación de la cota es
--    x > 2
--    x^2 + y^2 >= (y+1)^2
--    x^2 + y^2 >= y^2 + 2*y + 1
--    y =< (x^ 2 - 1) `div` 2 

-- (raizCuadrada x) es la lista formada por la raíz cuadrada entera de
-- x, si existe y la lista vacía, en caso contrario. Por ejemplo, 
--    raizCuadrada 25  ==  [5]
--    raizCuadrada 26  ==  []
raizCuadrada :: Integer -> [Integer]
raizCuadrada x =
  [y | y <- [(round . sqrt . fromIntegral) x]
     , y^2 == x]


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

mayorTernaPitagorica :: Integer -> (Integer,Integer,Integer)
mayorTernaPitagorica =
  last . ternasPitagoricas

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

mayorTernaPitagorica2 :: Integer -> (Integer,Integer,Integer)
mayorTernaPitagorica2 x =
  head [(x,y,z) | y <- [k, k-1 .. 1]
                , z <- raizCuadrada (x^2 + y^2)]
  where k = (x^2 - 1) `div` 2

  
-- 3ª definición de mayorTernaPitagorica
-- =====================================

-- Se supone que x > 2. Se consideran dos casos:
-- 
-- Primer caso: Supongamos que x es par. Entonces x^2 > 4 y es divisible
-- por 4. Por tanto, existe un y tal que x^2 = 4*y + 4; luego,
--    x^2 + y^2 = 4*y + 4 + y^2
--              = (y + 2)^2
-- La terna es (x,y,y+2) donde y = (x^2 - 4) / 4.
--
-- Segundo caso: Supongamos que x es impar. Entonces x^2 es impar. Por
-- tanto, existe un y tal que x^2 = 2*y + 1; luego,
--    x^2 + y^2 = 2*y + 1 + y^2
--              = (y+1)^2
-- La terna es (x,y,y+1) donde y = (x^2 - 1) / 2.

mayorTernaPitagorica3 :: Integer -> (Integer,Integer,Integer)
mayorTernaPitagorica3 x
  | even x    = (x, y1, y1 + 2)
  | otherwise = (x, y2, y2 + 1)
    where y1 = (x^2 - 4) `div` 4
          y2 = (x^2 - 1) `div` 2 

-- Comparación de eficiencia
--    λ> mayorTernaPitagorica 1006
--    (1006,253008,253010)
--    (7.36 secs, 1,407,793,992 bytes)
--    λ> mayorTernaPitagorica2 1006
--    (1006,253008,253010)
--    (3.76 secs, 704,007,456 bytes)
--    λ> mayorTernaPitagorica3 1006
--    (1006,253008,253010)
--    (0.01 secs, 157,328 bytes)

graficaMayorHipotenusa :: Integer -> IO ()
graficaMayorHipotenusa n =
  plotList [ Key Nothing
           , PNG "Terna_pitagorica_a_partir_de_un_lado.png"
           ]
           [(x,z) | x <- [3..n]
                  , let (_,_,z) = mayorTernaPitagorica3 x]

import Graphics.Gnuplot.Simple

-- Definición de ternasPitagoricas

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

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

ternasPitagoricas x =

[(x,y,z) | y <- [1..(x^ 2 - 1) `div` 2 ]

, z <- raizCuadrada (x^2 + y^2)]

-- La justificación de la cota es

-- x > 2

-- x^2 + y^2 >= (y+1)^2

-- x^2 + y^2 >= y^2 + 2*y + 1

-- y =< (x^ 2 - 1) `div` 2

-- (raizCuadrada x) es la lista formada por la raíz cuadrada entera de

-- x, si existe y la lista vacía, en caso contrario. Por ejemplo,

-- raizCuadrada 25 == [5]

-- raizCuadrada 26 == []

raizCuadrada :: Integer -> [Integer]

raizCuadrada x =

[y | y <- [(round . sqrt . fromIntegral) x]

, y^2 == x]

-- 1ª definición de mayorTernaPitagorica

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

mayorTernaPitagorica :: Integer -> (Integer,Integer,Integer)

mayorTernaPitagorica =

last . ternasPitagoricas

-- 2ª definición de mayorTernaPitagorica

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

mayorTernaPitagorica2 :: Integer -> (Integer,Integer,Integer)

mayorTernaPitagorica2 x =

head [(x,y,z) | y <- [k, k-1 .. 1]

, z <- raizCuadrada (x^2 + y^2)]

where k = (x^2 - 1) `div` 2

-- 3ª definición de mayorTernaPitagorica

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

-- Se supone que x > 2. Se consideran dos casos:

-- Primer caso: Supongamos que x es par. Entonces x^2 > 4 y es divisible

-- por 4. Por tanto, existe un y tal que x^2 = 4*y + 4; luego,

-- x^2 + y^2 = 4*y + 4 + y^2

-- = (y + 2)^2

-- La terna es (x,y,y+2) donde y = (x^2 - 4) / 4.

-- Segundo caso: Supongamos que x es impar. Entonces x^2 es impar. Por

-- tanto, existe un y tal que x^2 = 2*y + 1; luego,

-- x^2 + y^2 = 2*y + 1 + y^2

-- = (y+1)^2

-- La terna es (x,y,y+1) donde y = (x^2 - 1) / 2.

mayorTernaPitagorica3 :: Integer -> (Integer,Integer,Integer)

mayorTernaPitagorica3 x

| even x = (x, y1, y1 + 2)

| otherwise = (x, y2, y2 + 1)

where y1 = (x^2 - 4) `div` 4

y2 = (x^2 - 1) `div` 2

-- Comparación de eficiencia

-- λ> mayorTernaPitagorica 1006

-- (1006,253008,253010)

-- (7.36 secs, 1,407,793,992 bytes)

-- λ> mayorTernaPitagorica2 1006

-- (1006,253008,253010)

-- (3.76 secs, 704,007,456 bytes)

-- λ> mayorTernaPitagorica3 1006

-- (1006,253008,253010)

-- (0.01 secs, 157,328 bytes)

graficaMayorHipotenusa :: Integer -> IO ()

graficaMayorHipotenusa n =

plotList [ Key Nothing

, PNG "Terna_pitagorica_a_partir_de_un_lado.png"

]

[(x,z) | x <- [3..n]

, let (_,_,z) = mayorTernaPitagorica3 x]

Números como diferencias de potencias

PorJosé A. Alonso 17-enero-201819-febrero-2018

El número 45 se puede escribir de tres formas como diferencia de los cuadrados de dos números naturales:

   45 =  7^2 -  2^2 
      =  9^2 -  6^2
      = 23^2 - 22^2

45 = 7^2 - 2^2

= 9^2 - 6^2

= 23^2 - 22^2

Definir la función

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

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

tal que (diferencias x n) es la lista de pares tales que la diferencia de sus potencias n-ésima es x. Por ejemplo,

   diferencias 45 2    ==  [(7,2),(9,6),(23,22)]
   diferencias 50 2    ==  []
   diferencias 19 3    ==  [(3,2)]
   diferencias 8 3     ==  [(2,0)]
   diferencias 15 4    ==  [(2,1)]
   diferencias 4035 2  ==  [(142,127),(406,401),(674,671),(2018,2017)]
   head (diferencias 1161480105172255454401 5)  ==  (123456,123455)

diferencias 45 2 == [(7,2),(9,6),(23,22)]

diferencias 50 2 == []

diferencias 19 3 == [(3,2)]

diferencias 8 3 == [(2,0)]

diferencias 15 4 == [(2,1)]

diferencias 4035 2 == [(142,127),(406,401),(674,671),(2018,2017)]

head (diferencias 1161480105172255454401 5) == (123456,123455)

Soluciones

-- 1ª definición
diferencias :: Integer -> Integer -> [(Integer,Integer)]
diferencias x n = [(a,b) | b <- [0..x]
                         , a <- [b..x]
                         , x == a^n - b^n]

-- 2ª definición
diferencias2 :: Integer -> Integer -> [(Integer,Integer)]
diferencias2 x n =
  [(a,b) | a <- [1..x]
         , a^n >= x
         , let b = round ((fromIntegral (a^n - x)) ** (1/fromIntegral n))
         , x == a^n - b^n]

-- 3ª definición
diferencias3 :: Integer -> Integer -> [(Integer,Integer)]
diferencias3 x n =
  [(a,b) | a <- [0..x]
         , a^n >= x
         , b <- raizEntera n (a^n - x)]

raizEntera :: Integer -> Integer -> [Integer]
raizEntera n x 
  | y^n == x  = [y]
  | otherwise = []
  where y = head [k | k <- [0..], k^n >= x] 

-- 4ª definición
diferencias4 :: Integer -> Integer -> [(Integer,Integer)]
diferencias4 x n =
  [(a,b) | a <- [0..x]
         , a^n >= x
         , b <- raizEntera n (a^n - x)]
  where potencias = [(k,k^n) | k <- [0..]]
        raizEntera n x 
          | yn == x   = [y]
          | otherwise = []
          where (y,yn) = head [(k,kn) | (k,kn) <- potencias, kn >= x]

-- Comparación de eficiencia
--    λ> head (diferencias 7351 3)
--    (50,49)
--    (2.16 secs, 533,868,368 bytes)
--    λ> head (diferencias2 7351 3)
--    (50,49)
--    (0.01 secs, 270,040 bytes)
--    λ> head (diferencias3 7351 3)
--    (50,49)
--    (0.01 secs, 1,021,720 bytes)
--    λ> head (diferencias4 7351 3)
--    (50,49)
--    (0.01 secs, 316,536 bytes)

-- 1ª definición

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

diferencias x n = [(a,b) | b <- [0..x]

, a <- [b..x]

, x == a^n - b^n]

-- 2ª definición

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

diferencias2 x n =

[(a,b) | a <- [1..x]

, a^n >= x

, let b = round ((fromIntegral (a^n - x)) ** (1/fromIntegral n))

, x == a^n - b^n]

-- 3ª definición

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

diferencias3 x n =

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

, a^n >= x

, b <- raizEntera n (a^n - x)]

raizEntera :: Integer -> Integer -> [Integer]

raizEntera n x

| y^n == x = [y]

| otherwise = []

where y = head [k | k <- [0..], k^n >= x]

-- 4ª definición

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

diferencias4 x n =

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

, a^n >= x

, b <- raizEntera n (a^n - x)]

where potencias = [(k,k^n) | k <- [0..]]

raizEntera n x

| yn == x = [y]

| otherwise = []

where (y,yn) = head [(k,kn) | (k,kn) <- potencias, kn >= x]

-- Comparación de eficiencia

-- λ> head (diferencias 7351 3)

-- (50,49)

-- (2.16 secs, 533,868,368 bytes)

-- λ> head (diferencias2 7351 3)

-- (50,49)

-- (0.01 secs, 270,040 bytes)

-- λ> head (diferencias3 7351 3)

-- (50,49)

-- (0.01 secs, 1,021,720 bytes)

-- λ> head (diferencias4 7351 3)

-- (50,49)

-- (0.01 secs, 316,536 bytes)

De hexadecimal a decimal

PorJosé A. Alonso 1-enero-201819-febrero-2018

El sistema hexadecimal es el sistema de numeración posicional que tiene como base el 16.

En principio, dado que el sistema usual de numeración es de base decimal y, por ello, sólo se dispone de diez dígitos, se adoptó la convención de usar las seis primeras letras del alfabeto latino para suplir los dígitos que nos faltan. El conjunto de símbolos es el siguiente: {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}. En ocasiones se emplean letras minúsculas en lugar de mayúsculas. Se debe notar que A = 10, B = 11, C = 12, D = 13, E = 14 y F = 15.

Como en cualquier sistema de numeración posicional, el valor numérico de cada dígito es alterado dependiendo de su posición en la cadena de dígitos, quedando multiplicado por una cierta potencia de la base del sistema, que en este caso es 16. Por ejemplo, el valor decimal del número hexadecimal 3E0A es

     3×16^3 + E×16^2 + 0×16^1 + A×16^0
   = 3×4096 + 14×256 + 0×16   + 10×1
   = 15882

3×16^3 + E×16^2 + 0×16^1 + A×16^0

= 3×4096 + 14×256 + 0×16 + 10×1

= 15882

Definir la función

   hexAdec :: String -> Int

1	hexAdec :: String -> Int

tal que (hexAdec cs) es el valor decimal del número hexadecimal representado meiante la cadena cs. Por ejemplo,

   hexAdec "3E0A"   == 15882
   hexAdec "ABCDEF" == 11259375
   hexAdec "FEDCBA" == 16702650

hexAdec "3E0A" == 15882

hexAdec "ABCDEF" == 11259375

hexAdec "FEDCBA" == 16702650

Soluciones

import Data.Char (digitToInt)
import Numeric(readHex)
import Data.List (foldl')

-- 1ª solución
hexAdec1 :: String -> Int
hexAdec1 s =
  sum (zipWith (*) (map digitToInt (reverse s)) (iterate (*16) 1))

-- 2ª solución
hexAdec2 :: String -> Int
hexAdec2 = foldl' (\acc x -> acc * 16 + digitToInt x) 0

-- 3ª solución
hexAdec3 :: String -> Int
hexAdec3 = read . ("0x" ++)

-- 4ª solución
hexAdec4 :: String -> Int
hexAdec4 = fst . head . readHex

import Data.Char (digitToInt)

import Numeric(readHex)

import Data.List (foldl')

-- 1ª solución

hexAdec1 :: String -> Int

hexAdec1 s =

sum (zipWith (*) (map digitToInt (reverse s)) (iterate (*16) 1))

-- 2ª solución

hexAdec2 :: String -> Int

hexAdec2 = foldl' (\acc x -> acc * 16 + digitToInt x) 0

-- 3ª solución

hexAdec3 :: String -> Int

hexAdec3 = read . ("0x" ++)

-- 4ª solución

hexAdec4 :: String -> Int

hexAdec4 = fst . head . readHex

Vecino en lista circular

PorJosé A. Alonso 19-diciembre-201726-marzo-2022

En la lista circular [3,2,5,7,9]

el vecino izquierdo de 5 es 2 y su vecino derecho es 7,
el vecino izquierdo de 9 es 7 y su vecino derecho es 3,
el vecino izquierdo de 3 es 9 y su vecino derecho es 2,
el elemento 4 no tiene vecinos (porque no está en la lista).

Para indicar las direcciones se define el tipo de datos

   data Direccion = I | D deriving Eq

1	data Direccion = I \| D deriving Eq

Definir la función

   vecino :: Eq a => Direccion -> [a] -> a -> Maybe a

1	vecino :: Eq a => Direccion -> [a] -> a -> Maybe a

tal que (vecino d xs x) es el vecino de x en la lista de elementos distintos xs según la dirección d. Por ejemplo,

   vecino I [3,2,5,7,9] 5  ==  Just 2
   vecino D [3,2,5,7,9] 5  ==  Just 7
   vecino I [3,2,5,7,9] 9  ==  Just 7
   vecino D [3,2,5,7,9] 9  ==  Just 3
   vecino I [3,2,5,7,9] 3  ==  Just 9
   vecino D [3,2,5,7,9] 3  ==  Just 2
   vecino I [3,2,5,7,9] 4  ==  Nothing
   vecino D [3,2,5,7,9] 4  ==  Nothing

vecino I [3,2,5,7,9] 5 == Just 2

vecino D [3,2,5,7,9] 5 == Just 7

vecino I [3,2,5,7,9] 9 == Just 7

vecino D [3,2,5,7,9] 9 == Just 3

vecino I [3,2,5,7,9] 3 == Just 9

vecino D [3,2,5,7,9] 3 == Just 2

vecino I [3,2,5,7,9] 4 == Nothing

vecino D [3,2,5,7,9] 4 == Nothing

Soluciones

data Direccion = I | D deriving Eq

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

vecino1 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino1 d xs x = busca x (vecinos d xs)

-- (vecinos d xs) es la lista de elementos de xs y sus vecinos según la
-- direccioń d. Por ejemplo,
--    vecinos I [1..5]  ==  [(2,1),(3,2),(4,3),(5,4),(1,5)]
--    vecinos D [1..5]  ==  [(1,2),(2,3),(3,4),(4,5),(5,1)]
vecinos :: Direccion -> [a] -> [(a,a)]
vecinos I xs = zip (tail (cycle xs)) xs
vecinos D xs = zip xs (tail (cycle xs))

-- (busca x ps) es el la segunda componente de primer par de ps cuya
-- primera componente es igual a x. Por ejemplo, 
--    busca 3 [(4,1),(3,2),(3,7)]  ==  Just 2
--    busca 7 [(4,1),(3,2),(3,7)]  ==  Nothing
busca :: Eq a => a -> [(a,b)] -> Maybe b
busca x ps
  | null zs   = Nothing
  | otherwise = Just (head zs)
  where zs = [z | (x',z) <- ps, x' == x]

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

vecino2 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino2 d xs x = lookup x (vecinos d xs)

-- 3ª solución
-- ===========

vecino3 :: Eq a => Direccion -> [a] -> a -> Maybe a
vecino3 I xs x = lookup x (zip (tail (cycle xs)) xs) 
vecino3 D xs x = lookup x (zip xs (tail (cycle xs)))

data Direccion = I | D deriving Eq

-- 1ª solución

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

vecino1 :: Eq a => Direccion -> [a] -> a -> Maybe a

vecino1 d xs x = busca x (vecinos d xs)

-- (vecinos d xs) es la lista de elementos de xs y sus vecinos según la

-- direccioń d. Por ejemplo,

-- vecinos I [1..5] == [(2,1),(3,2),(4,3),(5,4),(1,5)]

-- vecinos D [1..5] == [(1,2),(2,3),(3,4),(4,5),(5,1)]

vecinos :: Direccion -> [a] -> [(a,a)]

vecinos I xs = zip (tail (cycle xs)) xs

vecinos D xs = zip xs (tail (cycle xs))

-- (busca x ps) es el la segunda componente de primer par de ps cuya

-- primera componente es igual a x. Por ejemplo,

-- busca 3 [(4,1),(3,2),(3,7)] == Just 2

-- busca 7 [(4,1),(3,2),(3,7)] == Nothing

busca :: Eq a => a -> [(a,b)] -> Maybe b

busca x ps

| null zs = Nothing

| otherwise = Just (head zs)

where zs = [z | (x',z) <- ps, x' == x]

-- 2ª solución

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

vecino2 :: Eq a => Direccion -> [a] -> a -> Maybe a

vecino2 d xs x = lookup x (vecinos d xs)

-- 3ª solución

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

vecino3 :: Eq a => Direccion -> [a] -> a -> Maybe a

vecino3 I xs x = lookup x (zip (tail (cycle xs)) xs)

vecino3 D xs x = lookup x (zip xs (tail (cycle xs)))

Menor con suma de dígitos dada

PorJosé A. Alonso 15-diciembre-201722-diciembre-2017

Definir la función

   minSumDig :: Integer -> Integer

1	minSumDig :: Integer -> Integer

tal que (minSumDig n) es el menor número x tal que la suma de los dígitos de x es n. Por ejemplo,

  minSumDig 1   ==  1
  minSumDig 12  ==  39
  minSumDig 21  ==  399
  (length . show . minSumDig) (3*10^5)  ==  33334
  (length . show . minSumDig) (3*10^6)  ==  333334
  (length . show . minSumDig) (3*10^7)  ==  3333334
  (length . show . minSumDig) (4*10^7)  ==  4444445
  (length . show . minSumDig) (5*10^7)  ==  5555556

minSumDig 1 == 1

minSumDig 12 == 39

minSumDig 21 == 399

(length . show . minSumDig) (3*10^5) == 33334

(length . show . minSumDig) (3*10^6) == 333334

(length . show . minSumDig) (3*10^7) == 3333334

(length . show . minSumDig) (4*10^7) == 4444445

(length . show . minSumDig) (5*10^7) == 5555556

Soluciones

import Data.List (genericIndex)

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

minSumDig1 :: Integer -> Integer
minSumDig1 n = head [x | x <- [0..], sumaDigitos x == n]

sumaDigitos :: Integer -> Integer
sumaDigitos n | n < 10    = n
              | otherwise = y + sumaDigitos x
  where (x, y) = divMod n 10

-- 2ª definición
minSumDig2 :: Integer -> Integer
minSumDig2 n | n < 10    = n
             | otherwise = 9 + 10 * minSumDig2 (n - 9) 

-- 3ª definición
minSumDig3 :: Integer -> Integer
minSumDig3 n = (r + 1) * 10^d - 1
  where (d,r) = divMod n 9

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

--    λ> minSumDig1 46
--    199999
--    (3.21 secs, 542,721,696 bytes)
--    λ> minSumDig2 46
--    199999
--    (0.01 secs, 142,056 bytes)
--    λ> minSumDig3 46
--    199999
--    (0.01 secs, 155,984 bytes)
--    
--    λ> (length . show . minSumDig2) (3*10^5)
--    33334
--    (1.79 secs, 492,200,376 bytes)
--    λ> (length . show . minSumDig3) (3*10^5)
--    33334
--    (0.11 secs, 50,119,840 bytes)

import Data.List (genericIndex)

-- 1ª definición

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

minSumDig1 :: Integer -> Integer

minSumDig1 n = head [x | x <- [0..], sumaDigitos x == n]

sumaDigitos :: Integer -> Integer

sumaDigitos n | n < 10 = n

| otherwise = y + sumaDigitos x

where (x, y) = divMod n 10

-- 2ª definición

minSumDig2 :: Integer -> Integer

minSumDig2 n | n < 10 = n

| otherwise = 9 + 10 * minSumDig2 (n - 9)

-- 3ª definición

minSumDig3 :: Integer -> Integer

minSumDig3 n = (r + 1) * 10^d - 1

where (d,r) = divMod n 9

-- Comparación de eficiencia

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

-- λ> minSumDig1 46

-- 199999

-- (3.21 secs, 542,721,696 bytes)

-- λ> minSumDig2 46

-- 199999

-- (0.01 secs, 142,056 bytes)

-- λ> minSumDig3 46

-- 199999

-- (0.01 secs, 155,984 bytes)

-- λ> (length . show . minSumDig2) (3*10^5)

-- 33334

-- (1.79 secs, 492,200,376 bytes)

-- λ> (length . show . minSumDig3) (3*10^5)

-- 33334

-- (0.11 secs, 50,119,840 bytes)

Menor x tal que los x múltiplos de n contienen todos los dígitos

PorJosé A. Alonso 28-noviembre-20178-diciembre-2017

Definir la función

   menorX :: Integer -> Integer

1	menorX :: Integer -> Integer

tal que (menorX n) es el menor x tal que entre los x primeros múltiplos de n (es decir, entre n, 2×n, 3×n, … y x×n) contienen todos los dígitos al menos una vez. Por ejemplo, (menorX 92) es 6 ya que

   92                                    contiene  [2,9]
   92 y 92×2                             contienen [1,2,4,8,9]
   92,  92×2 y 92×3                      contienen [1,2,4,6,7,8,9]
   92,  92×2,  92×3 y 92×4               contienen [1,2,3,4,6,7,8,9]
   92,  92×2,  92×3,  92×4 y 92×5        contienen [0,1,2,3,4,6,7,8,9]
   92,  92×2,  92×3,  92×4,  92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

92 contiene [2,9]

92 y 92×2 contienen [1,2,4,8,9]

92, 92×2 y 92×3 contienen [1,2,4,6,7,8,9]

92, 92×2, 92×3 y 92×4 contienen [1,2,3,4,6,7,8,9]

92, 92×2, 92×3, 92×4 y 92×5 contienen [0,1,2,3,4,6,7,8,9]

92, 92×2, 92×3, 92×4, 92×5 y 92×6 contienen [0,1,2,3,4,5,6,7,8,9]

Otros ejemplos

   menorX 92          ==  6
   menorX 2967        ==  3
   menorX 266         ==  4
   menorX 18          ==  5
   menorX 2           ==  45
   menorX 125         ==  72
   menorX 1234567890  ==  1
   maximum [menorX n | n <- [1..3000]]  ==  72
   minimum [menorX n | n <- [1..3000]]  ==  3

menorX 92 == 6

menorX 2967 == 3

menorX 266 == 4

menorX 18 == 5

menorX 2 == 45

menorX 125 == 72

menorX 1234567890 == 1

maximum [menorX n | n <- [1..3000]] == 72

minimum [menorX n | n <- [1..3000]] == 3

Soluciones

import Data.List ((\\))

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

menorX :: Integer -> Integer
menorX n =
  head [x | x <- [1..]
          , [0..9] `contenido` digitosMultiplos n x]

contenido :: Eq a => [a] -> [a] -> Bool
contenido xs ys =
  all (`elem` ys) xs

digitosMultiplos :: Integer -> Integer -> [Integer]
digitosMultiplos n x =
  concatMap digitos [n,2*n..x*n]

digitos :: Integer -> [Integer]
digitos n =
  [read [c] | c <- show n]

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

menorX2 :: Integer -> Integer
menorX2 n = aux [] 0
  where aux xs x
          | [0..9] `contenido` xs = x
          | otherwise             = aux (digitos (n*(x+1)) ++ xs) (x+1)

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

menorX3 :: Integer -> Integer
menorX3 n = aux ['0'..'9'] 0
  where aux xs x
          | null xs   = x
          | otherwise = aux (xs \\ show (n*(x+1))) (x+1)

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

menorX4 :: Integer -> Integer
menorX4 n = aux "0123456789" 1 n
  where aux xs x nx | null ys   = x
                    | otherwise = aux ys (1+x) (nx+n)
          where ys = xs \\ show nx

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

--    λ> maximum [menorX n | n <- [1..6000]]
--    72
--    (2.04 secs, 3,737,579,888 bytes)
--    λ> maximum [menorX2 n | n <- [1..6000]]
--    72
--    (0.52 secs, 818,602,736 bytes)
--    λ> maximum [menorX3 n | n <- [1..6000]]
--    72
--    (0.10 secs, 67,090,800 bytes)
--    λ> maximum [menorX3 n | n <- [1..6000]]
--    72
--    (0.08 secs, 67,090,800 bytes)
--    
--    λ> maximum [menorX3 n | n <- [1..10^5]]
--    72
--    (0.81 secs, 1,044,781,216 bytes)
--    λ> maximum [menorX4 n | n <- [1..10^5]]
--    72
--    (0.71 secs, 1,009,113,304 bytes)

import Data.List ((\\))

-- 1ª definición

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

menorX :: Integer -> Integer

menorX n =

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

, [0..9] `contenido` digitosMultiplos n x]

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

contenido xs ys =

all (`elem` ys) xs

digitosMultiplos :: Integer -> Integer -> [Integer]

digitosMultiplos n x =

concatMap digitos [n,2*n..x*n]

digitos :: Integer -> [Integer]

digitos n =

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

-- 2ª definición

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

menorX2 :: Integer -> Integer

menorX2 n = aux [] 0

where aux xs x

| [0..9] `contenido` xs = x

| otherwise = aux (digitos (n*(x+1)) ++ xs) (x+1)

-- 3ª definición

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

menorX3 :: Integer -> Integer

menorX3 n = aux ['0'..'9'] 0

where aux xs x

| null xs = x

| otherwise = aux (xs \\ show (n*(x+1))) (x+1)

-- 4ª definición

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

menorX4 :: Integer -> Integer

menorX4 n = aux "0123456789" 1 n

where aux xs x nx | null ys = x

| otherwise = aux ys (1+x) (nx+n)

where ys = xs \\ show nx

-- Comparación de eficiencia

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

-- λ> maximum [menorX n | n <- [1..6000]]

-- 72

-- (2.04 secs, 3,737,579,888 bytes)

-- λ> maximum [menorX2 n | n <- [1..6000]]

-- 72

-- (0.52 secs, 818,602,736 bytes)

-- λ> maximum [menorX3 n | n <- [1..6000]]

-- 72

-- (0.10 secs, 67,090,800 bytes)

-- λ> maximum [menorX3 n | n <- [1..6000]]

-- 72

-- (0.08 secs, 67,090,800 bytes)

-- λ> maximum [menorX3 n | n <- [1..10^5]]

-- 72

-- (0.81 secs, 1,044,781,216 bytes)

-- λ> maximum [menorX4 n | n <- [1..10^5]]

-- 72

-- (0.71 secs, 1,009,113,304 bytes)

Números dígito potenciales

PorJosé A. Alonso 15-noviembre-201725-noviembre-2017

Un número entero x es dígito potencial de orden n si x es la suma de los dígitos de x elevados a n. Por ejemplo,

153 es un dígito potencial de orden 3 ya que 153 = 1^3+5^3+3^3
4150 es un dígito potencial de orden 5 ya que 4150 = 4^5+1^5+5^5+0^5

Un número x es dígito auto potencial si es un dígito potencial de orden n, donde n es el número de dígitos de n. Por ejemplo, 153 es un número dígito auto potencial.

Definir las funciones

   digitosPotencialesOrden :: Integer -> [Integer]
   digitosAutoPotenciales  :: [Integer]

1 2	digitosPotencialesOrden :: Integer -> [Integer] digitosAutoPotenciales :: [Integer]

tales que

(digitosPotencialesOrden n) es la lista de los números dígito potenciales de orden n. Por ejemplo,

     take 6 (digitosPotencialesOrden 3)  ==  [0,1,153,370,371,407]
     take 5 (digitosPotencialesOrden 4)  ==  [0,1,1634,8208,9474]
     take 8 (digitosPotencialesOrden 5)  ==  [0,1,4150,4151,54748,92727,93084,194979]
     take 3 (digitosPotencialesOrden 6)  ==  [0,1,548834]

take 6 (digitosPotencialesOrden 3) == [0,1,153,370,371,407]

take 5 (digitosPotencialesOrden 4) == [0,1,1634,8208,9474]

take 8 (digitosPotencialesOrden 5) == [0,1,4150,4151,54748,92727,93084,194979]

take 3 (digitosPotencialesOrden 6) == [0,1,548834]

digitosAutoPotenciales es la lista de los números dígito auto potenciales. Por ejemplo,

     λ> take 20 digitosAutoPotenciales
     [0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

1 2	λ> take 20 digitosAutoPotenciales [0,1,2,3,4,5,6,7,8,9,153,370,371,407,1634,8208,9474,54748,92727,93084]

Soluciones

import Data.List (genericLength)
import Data.Char (digitToInt)

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

digitosPotencialesOrden :: Integer -> [Integer]
digitosPotencialesOrden n =
  [x | x <- [0..]
     , esDigitoPotencialOrden n x]

esDigitoPotencialOrden :: Integer -> Integer -> Bool
esDigitoPotencialOrden n x =
  x == sum [y^n | y <- digitos x]

digitos :: Integer -> [Integer]
digitos x = [read [d] | d <- show x] 

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

digitosPotencialesOrden2 :: Integer -> [Integer]
digitosPotencialesOrden2 n =
  filter (esDigitoPotencialOrden2 n) [0..]

esDigitoPotencialOrden2 :: Integer -> Integer -> Bool
esDigitoPotencialOrden2 n x =
  x == sum (map (^n) (digitos2 x))

digitos2 :: Integer -> [Integer]
digitos2 = map (toInteger . digitToInt) . show

-- 3ª definición de digitosPotencialesOrden
-- ========================================

--    digitosPotencialesOrden3 3  ==  [0,1,153,370,371,407]
--    digitosPotencialesOrden3 4  ==  [0,1,1634,8208,9474]
digitosPotencialesOrden3 :: Integer -> [Integer]
digitosPotencialesOrden3 n =
  filter (esDigitoPotencialOrden2 n) [0..10^d-1]
  where d = maximoNDigitosPotencialesOrden n 

-- (maximoNDigitosPotencialesOrden n) es el máximo número de dígitos de
-- los números dígitos potenciales de orden d. Por ejemplo,
--    maximoNDigitosPotencialesOrden 3  ==  5
--    maximoNDigitosPotencialesOrden 5  ==  7
maximoNDigitosPotencialesOrden :: Integer -> Integer
maximoNDigitosPotencialesOrden n =
  head (dropWhile (\d -> d*9^n >= 10^(d-1)) [1..])

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

esDigitoAutoPotencial :: Integer -> Bool
esDigitoAutoPotencial x =
  esDigitoPotencialOrden (genericLength (show x)) x

digitosAutoPotenciales :: [Integer]
digitosAutoPotenciales =
  filter esDigitoAutoPotencial [0..]

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

digitosAutoPotenciales2 :: [Integer]
digitosAutoPotenciales2 =
  0: concat [[x | x <- [10^k..10^(k+1)-1], esDigitoPotencialOrden (k+1) x]
            | k <- [0..]]

import Data.List (genericLength)

import Data.Char (digitToInt)

-- 1ª definición de digitosPotencialesOrden

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

digitosPotencialesOrden :: Integer -> [Integer]

digitosPotencialesOrden n =

[x | x <- [0..]

, esDigitoPotencialOrden n x]

esDigitoPotencialOrden :: Integer -> Integer -> Bool

esDigitoPotencialOrden n x =

x == sum [y^n | y <- digitos x]

digitos :: Integer -> [Integer]

digitos x = [read [d] | d <- show x]

-- 2ª definición de digitosPotencialesOrden

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

digitosPotencialesOrden2 :: Integer -> [Integer]

digitosPotencialesOrden2 n =

filter (esDigitoPotencialOrden2 n) [0..]

esDigitoPotencialOrden2 :: Integer -> Integer -> Bool

esDigitoPotencialOrden2 n x =

x == sum (map (^n) (digitos2 x))

digitos2 :: Integer -> [Integer]

digitos2 = map (toInteger . digitToInt) . show

-- 3ª definición de digitosPotencialesOrden

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

-- digitosPotencialesOrden3 3 == [0,1,153,370,371,407]

-- digitosPotencialesOrden3 4 == [0,1,1634,8208,9474]

digitosPotencialesOrden3 :: Integer -> [Integer]

digitosPotencialesOrden3 n =

filter (esDigitoPotencialOrden2 n) [0..10^d-1]

where d = maximoNDigitosPotencialesOrden n

-- (maximoNDigitosPotencialesOrden n) es el máximo número de dígitos de

-- los números dígitos potenciales de orden d. Por ejemplo,

-- maximoNDigitosPotencialesOrden 3 == 5

-- maximoNDigitosPotencialesOrden 5 == 7

maximoNDigitosPotencialesOrden :: Integer -> Integer

maximoNDigitosPotencialesOrden n =

head (dropWhile (\d -> d*9^n >= 10^(d-1)) [1..])

-- 1ª definición de esDigitoAutoPotencial

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

esDigitoAutoPotencial :: Integer -> Bool

esDigitoAutoPotencial x =

esDigitoPotencialOrden (genericLength (show x)) x

digitosAutoPotenciales :: [Integer]

digitosAutoPotenciales =

filter esDigitoAutoPotencial [0..]

-- 2ª definición de esDigitoAutoPotencial

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

digitosAutoPotenciales2 :: [Integer]

digitosAutoPotenciales2 =

0: concat [[x | x <- [10^k..10^(k+1)-1], esDigitoPotencialOrden (k+1) x]

| k <- [0..]]

Números oblongos

PorJosé A. Alonso 13-noviembre-201725-marzo-2022

Un número oblongo es un número que es el producto de dos números naturales consecutivos; es decir, n es un número oblongo si existe un número natural x tal que n = x(x+1). Por ejemplo, 42 es un número oblongo porque 42 = 6 x 7.

Definir las funciones

   esOblongo :: Integer -> Bool
   oblongos  :: [Integer]

1 2	esOblongo :: Integer -> Bool oblongos :: [Integer]

tales que

(esOblongo n) se verifica si n es oblongo. Por ejemplo,

     esOblongo 42               ==  True
     esOblongo 40               ==  False
     esOblongo 100000010000000  ==  True

esOblongo 42 == True

esOblongo 40 == False

esOblongo 100000010000000 == True

oblongos es la suceción de los números oblongos. Por ejemplo,

     take 15 oblongos   == [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210]
     oblongos !! 50     == 2550
     oblongos !! (10^7) == 100000010000000

take 15 oblongos == [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210]

oblongos !! 50 == 2550

oblongos !! (10^7) == 100000010000000

Soluciones

-- 1ª definición de esOblongo
esOblongo1 :: Integer -> Bool
esOblongo1 n =
  n == x * (x+1)
  where x = round (sqrt (fromIntegral n))

-- 2ª definición de esOblongo
esOblongo2 :: Integer -> Bool
esOblongo2 n =
  n `pertenece` oblongos3

pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (< x) ys)

-- 1ª definición de oblongos
oblongos1 :: [Integer]
oblongos1 = [n | n <- [0..]
               , esOblongo1 n]

-- 2ª definición de oblongos
oblongos2 :: [Integer]
oblongos2 = filter esOblongo1 [0..]

-- 3ª definición de oblongos
oblongos3 :: [Integer]
oblongos3 = zipWith (*) [0..] [1..]

-- 1ª definición de esOblongo

esOblongo1 :: Integer -> Bool

esOblongo1 n =

n == x * (x+1)

where x = round (sqrt (fromIntegral n))

-- 2ª definición de esOblongo

esOblongo2 :: Integer -> Bool

esOblongo2 n =

n `pertenece` oblongos3

pertenece :: Integer -> [Integer] -> Bool

pertenece x ys =

x == head (dropWhile (< x) ys)

-- 1ª definición de oblongos

oblongos1 :: [Integer]

oblongos1 = [n | n <- [0..]

, esOblongo1 n]

-- 2ª definición de oblongos

oblongos2 :: [Integer]

oblongos2 = filter esOblongo1 [0..]

-- 3ª definición de oblongos

oblongos3 :: [Integer]

oblongos3 = zipWith (*) [0..] [1..]

Rotaciones divisibles por 4

PorJosé A. Alonso 3-abril-201710-abril-2017

Las rotaciones de 928160 son 928160, 281609, 816092, 160928, 609281 y 92816. De las cuales, las divisibles por 4 son 928160, 816092, 160928 y 92816.

Definir la función

   nRotacionesDivisibles :: Integer -> Int

1	nRotacionesDivisibles :: Integer -> Int

tal que (nRotacionesDivisibles n) es el número de rotaciones del número n divisibles por 4. Por ejemplo,

   nRotacionesDivisibles 928160          ==  4
   nRotacionesDivisibles 44              ==  2
   nRotacionesDivisibles (1234^50000)    ==  38684
   nRotacionesDivisibles (1234^300000)   ==  231853

nRotacionesDivisibles 928160 == 4

nRotacionesDivisibles 44 == 2

nRotacionesDivisibles (1234^50000) == 38684

nRotacionesDivisibles (1234^300000) == 231853

Soluciones

import Data.Char (digitToInt)

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

nRotacionesDivisibles :: Integer -> Int
nRotacionesDivisibles n =
  length [x | x <- rotacionesNumero n, x `mod` 4 == 0]


-- (rotacionesNumero) es la lista de la rotaciones del número n. Por
-- ejemplo,
--    rotacionesNumero 235  ==  [235,352,523]
rotacionesNumero :: Integer -> [Integer]
rotacionesNumero = map read . rotaciones . show

-- (rotaciones xs) es la lista de las rotaciones obtenidas desplazando
-- el primer elemento xs al final. Por ejemplo,
--    rotaciones [2,3,5]  ==  [[2,3,5],[3,5,2],[5,2,3]]
rotaciones :: [a] -> [[a]]
rotaciones xs = take (length xs) (iterate rota xs)

-- (rota xs) es la lista añadiendo el primer elemento de xs al
-- final. Por ejemplo, 
--    rota [3,2,5,7]  ==  [2,5,7,3]
rota :: [a] -> [a]
rota (x:xs) = xs ++ [x]

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

nRotacionesDivisibles2 :: Integer -> Int
nRotacionesDivisibles2 n = 
  length [x | x <- pares n, x `mod` 4 == 0]

-- (pares n) es la lista de pares de elementos consecutivos, incluyendo
-- el último con el primero. Por ejemplo,
--    pares 928160  ==  [9,92,28,81,16,60]
pares :: Integer -> [Int]
pares n =
  read [last ns,head ns] : [read [a,b] | (a,b) <- zip ns (tail ns)]
  where ns = show n

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

nRotacionesDivisibles3 :: Integer -> Int
nRotacionesDivisibles3 n =
  ( length
  . filter (0 ==)
  . map (`mod` 4)
  . zipWith (\x y -> 2*x + y) d
  . tail
  . (++[i])) d
  where
    d@(i:dn) = (map digitToInt . show) n

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

--    λ> nRotacionesDivisibles (123^1500)
--    803
--    (8.15 secs, 7,109,852,800 bytes)
--    λ> nRotacionesDivisibles2 (123^1500)
--    803
--    (0.05 secs, 0 bytes)
--    λ> nRotacionesDivisibles3 (123^1500)
--    803
--    (0.02 secs, 0 bytes)
--
--    λ> nRotacionesDivisibles2 (1234^50000)
--    38684
--    (2.24 secs, 1,160,467,472 bytes)
--    λ> nRotacionesDivisibles3 (1234^50000)
--    38684
--    (0.31 secs, 68,252,040 bytes)

import Data.Char (digitToInt)

-- 1ª definición

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

nRotacionesDivisibles :: Integer -> Int

nRotacionesDivisibles n =

length [x | x <- rotacionesNumero n, x `mod` 4 == 0]

-- (rotacionesNumero) es la lista de la rotaciones del número n. Por

-- ejemplo,

-- rotacionesNumero 235 == [235,352,523]

rotacionesNumero :: Integer -> [Integer]

rotacionesNumero = map read . rotaciones . show

-- (rotaciones xs) es la lista de las rotaciones obtenidas desplazando

-- el primer elemento xs al final. Por ejemplo,

-- rotaciones [2,3,5] == [[2,3,5],[3,5,2],[5,2,3]]

rotaciones :: [a] -> [[a]]

rotaciones xs = take (length xs) (iterate rota xs)

-- (rota xs) es la lista añadiendo el primer elemento de xs al

-- final. Por ejemplo,

-- rota [3,2,5,7] == [2,5,7,3]

rota :: [a] -> [a]

rota (x:xs) = xs ++ [x]

-- 2ª definición

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

nRotacionesDivisibles2 :: Integer -> Int

nRotacionesDivisibles2 n =

length [x | x <- pares n, x `mod` 4 == 0]

-- (pares n) es la lista de pares de elementos consecutivos, incluyendo

-- el último con el primero. Por ejemplo,

-- pares 928160 == [9,92,28,81,16,60]

pares :: Integer -> [Int]

pares n =

read [last ns,head ns] : [read [a,b] | (a,b) <- zip ns (tail ns)]

where ns = show n

-- 3ª definición

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

nRotacionesDivisibles3 :: Integer -> Int

nRotacionesDivisibles3 n =

( length

. filter (0 ==)

. map (`mod` 4)

. zipWith (\x y -> 2*x + y) d

. tail

. (++[i])) d

where

d@(i:dn) = (map digitToInt . show) n

-- Comparación de eficiencia

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

-- λ> nRotacionesDivisibles (123^1500)

-- 803

-- (8.15 secs, 7,109,852,800 bytes)

-- λ> nRotacionesDivisibles2 (123^1500)

-- 803

-- (0.05 secs, 0 bytes)

-- λ> nRotacionesDivisibles3 (123^1500)

-- 803

-- (0.02 secs, 0 bytes)

-- λ> nRotacionesDivisibles2 (1234^50000)

-- 38684

-- (2.24 secs, 1,160,467,472 bytes)

-- λ> nRotacionesDivisibles3 (1234^50000)

-- 38684

-- (0.31 secs, 68,252,040 bytes)

Representación de conjuntos mediante intervalos

PorJosé A. Alonso 22-marzo-201725-abril-2021

Un conjunto de números enteros se pueden representar mediante una lista ordenada de intervalos tales que la diferencia entre el menor elemento de un intervalo y el mayor elemento de su intervalo anterior es mayor que uno.

Por ejemplo, el conjunto {2, 7, 4, 3, 9, 6} se puede representar mediante la lista de intervalos [(2,4),(6,7),(9,9)] de forma que en el primer intervalo se agrupan los números 2, 3 y 4; en el segundo, los números 6 y 7 y el tercero, el número 9.

Definir la función

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

1	intervalos :: [Int] -> [(Int,Int)]

tal que (intervalos xs) es lista ordenada de intervalos que representa al conjunto xs. Por ejemplo,

   intervalos [2,7,4,3,9,6]  ==  [(2,4),(6,7),(9,9)]

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

Nota: Este ejercicio está basado en el problema Bus numbers de Kattis

Soluciones

import Data.List (sort)

intervalos :: [Int] -> [(Int,Int)]
intervalos = map intervalo . segmentos

-- (segmentos xs) es la lista de segmentos formados por elementos
-- consecutivos de xs. Por ejemplo,
--    segmentos [2,7,4,3,9,6]  ==  [[2,3,4],[6,7],[9]]
segmentos :: [Int] -> [[Int]]
segmentos xs = aux as [[a]]
  where aux [] zs = zs
        aux (y:ys) ((a:as):zs) | y == a-1  = aux ys ((y:a:as):zs)
                               | otherwise = aux ys ([y]:(a:as):zs)
        (a:as) = reverse (sort xs)

-- (intervalo xs) es el intervalo correspondiente al segmento xs. Por
-- ejemplo, 
--    intervalo [2,3,4]  ==  (2,4)
--    intervalo [6,7]    ==  (6,7)
--    intervalo [9]      ==  (9,9)
intervalo :: [Int] -> (Int,Int)
intervalo xs = (head xs, last xs)

import Data.List (sort)

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

intervalos = map intervalo . segmentos

-- (segmentos xs) es la lista de segmentos formados por elementos

-- consecutivos de xs. Por ejemplo,

-- segmentos [2,7,4,3,9,6] == [[2,3,4],[6,7],[9]]

segmentos :: [Int] -> [[Int]]

segmentos xs = aux as [[a]]

where aux [] zs = zs

aux (y:ys) ((a:as):zs) | y == a-1 = aux ys ((y:a:as):zs)

| otherwise = aux ys ([y]:(a:as):zs)

(a:as) = reverse (sort xs)

-- (intervalo xs) es el intervalo correspondiente al segmento xs. Por

-- ejemplo,

-- intervalo [2,3,4] == (2,4)

-- intervalo [6,7] == (6,7)

-- intervalo [9] == (9,9)

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

intervalo xs = (head xs, last xs)

Reducción de repeticiones consecutivas

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

Definir la función

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

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

tal que (reducida xs) es la lista obtenida a partir de xs de forma que si hay dos o más elementos idénticos consecutivos, borra las repeticiones y deja sólo el primer elemento. Por ejemplo,

   ghci> reducida "eesssooo essss   toodddooo"
   "eso es todo"

1 2	ghci> reducida "eesssooo essss toodddooo" "eso es todo"

Nota: Basado en el ejercicio Apaxiaaaaaaaaaaaans! de Kattis.

Soluciones

import Data.List (group)

-- 1ª solución (por recursión):
reducida1 :: Eq a => [a] -> [a]
reducida1 []     = []
reducida1 (x:xs) = x : reducida1 (dropWhile (==x) xs)

-- 2ª solución (por comprensión):
reducida2 :: Eq a => [a] -> [a]
reducida2 xs = [x | (x:_) <- group xs]

-- 3ª solución (sin argumentos):
reducida3 :: Eq a => [a] -> [a]
reducida3 = map head . group

import Data.List (group)

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

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

reducida1 [] = []

reducida1 (x:xs) = x : reducida1 (dropWhile (==x) xs)

-- 2ª solución (por comprensión):

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

reducida2 xs = [x | (x:_) <- group xs]

-- 3ª solución (sin argumentos):

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

reducida3 = map head . group

Por 3 o más 5

PorJosé A. Alonso 16-marzo-201720-enero-2019

El enunciado del problema Por 3 o más 5 de ¡Acepta el reto! es el siguiente

Cuenta la leyenda que un famoso matemático, tras aprender a sumar y multiplicar a la tierna edad de 3 años en apenas 5 días, se dio cuenta de que, empezando por 1, podía generar un montón de números sin más que multiplicar por 3 o sumar 5 a alguno de los que ya hubiera generado antes.

Por ejemplo, el 23 (edad a la que se casaría) lo obtuvo así: ((1 + 5) × 3) + 5
Por su parte el 77 (edad a la que tendría su primer bisnieto) lo consiguió: (((1 × 3 + 5) × 3) × 3) + 5

Por mucho que lo intentó, algunos números, sin embargo, resultaron ser imposibles de obtener, como por ejemplo el 5, el 7 o el 15.

Se dice que un número es generable si se puede escribir como una sucesión (quizá vacía) de multiplicaciones por 3 y sumas de 5 al número 1.

Definir las siguientes funciones

   generables     :: [Integer]
   generable      :: Integer -> Bool
   arbolGenerable :: Integer -> Tree Integer

generables :: [Integer]

generable :: Integer -> Bool

arbolGenerable :: Integer -> Tree Integer

tales que

generables es la sucesión de los números generables. Por ejemplo,

     λ> take 20 generables
     [1,3,6,8,9,11,13,14,16,18,19,21,23,24,26,27,28,29,31,32]
     λ> generables !! (10^6)
     1250008

λ> take 20 generables

[1,3,6,8,9,11,13,14,16,18,19,21,23,24,26,27,28,29,31,32]

λ> generables !! (10^6)

1250008

(generable x) se verifica si x es generable. Por ejemplo,

     generable 23       ==  True
     generable 77       ==  True
     generable 15       ==  False
     generable 1250008  ==  True
     generable 1250010  ==  False

generable 23 == True

generable 77 == True

generable 15 == False

generable 1250008 == True

generable 1250010 == False

(arbolGenerable x) es el árbol de los números generables menores o iguales a x. Por ejemplo,

     λ> putStrLn (drawTree (fmap show (arbolGenerable 11)))
     1
     |
     +- 3
     |  |
     |  +- 9
     |  |
     |  `- 8
     |
     `- 6
        |
        `- 11

λ> putStrLn (drawTree (fmap show (arbolGenerable 11)))

+- 3

| |

| +- 9

| |

| `- 8

`- 6

`- 11

Soluciones

import Graphics.Gnuplot.Simple

generables :: [Integer]
generables = 1 : mezcla [3 * x | x <- generables]
                        [5 + x | x <- generables]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas
-- ordenadas xs e ys, suponiendo que ambas son infinitas. 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
  | x == y    = x : mezcla xs ys
  | otherwise = y : mezcla us ys

generable :: Integer -> Bool
generable x =
  x == head (dropWhile (<x) generables)

-- 2ª definición
generable2 :: Integer -> Bool
generable2 1 = True
generable2 x =    (x `mod` 3 == 0 && generable2 (x `div` 3))
               || (x > 5 && generable2 (x - 5))

generables2 :: [Integer] 
generables2 = filter generable2 [1..]

arbolGenerable :: Integer -> Tree Integer
arbolGenerable n = aux 1
  where aux x
          | 3*x <= n && 5+x <= n = Node x [aux (3*x), aux (5+x)] 
          | 3*x <= n             = Node x [aux (3*x)]
          | 5+x <= n             = Node x [aux (5+x)]
          | otherwise            = Node x [] 

-- 3ª definición
generable3 :: Integer -> Bool
generable3 x =
  x `elem` arbolGenerable x

import Graphics.Gnuplot.Simple

generables :: [Integer]

generables = 1 : mezcla [3 * x | x <- generables]

[5 + x | x <- generables]

-- (mezcla xs ys) es la lista ordenada obtenida mezclando las dos listas

-- ordenadas xs e ys, suponiendo que ambas son infinitas. 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

| x == y = x : mezcla xs ys

| otherwise = y : mezcla us ys

generable :: Integer -> Bool

generable x =

x == head (dropWhile (<x) generables)

-- 2ª definición

generable2 :: Integer -> Bool

generable2 1 = True

generable2 x = (x `mod` 3 == 0 && generable2 (x `div` 3))

|| (x > 5 && generable2 (x - 5))

generables2 :: [Integer]

generables2 = filter generable2 [1..]

arbolGenerable :: Integer -> Tree Integer

arbolGenerable n = aux 1

where aux x

| 3*x <= n && 5+x <= n = Node x [aux (3*x), aux (5+x)]

| 3*x <= n = Node x [aux (3*x)]

| 5+x <= n = Node x [aux (5+x)]

| otherwise = Node x []

-- 3ª definición

generable3 :: Integer -> Bool

generable3 x =

x `elem` arbolGenerable x

Números cubifinitos

PorJosé A. Alonso 15-marzo-201721-enero-2020

El enunciado del problema Números cubifinitos de ¡Acepta el reto! es el siguiente

Se dice que un número es cubifinito cuando al elevar todos sus dígitos al cubo y sumarlos el resultado o bien es 1 o bien es un número cubifinito.

Por ejemplo, el número 1243 es cubifinito, pues al elevar todos sus dígitos al cubo obtenemos 100 que es cubifinito.

Por su parte, el 513 no es cubifinito, pues al elevar al cubo sus dígitos conseguimos el 153 que nunca podrá ser cubifinito, pues la suma de los cubos de sus dígitos vuelve a dar 153.

Definir las funciones

   esCubifinito :: Int -> Bool
   grafica :: Int -> IO ()

1 2	esCubifinito :: Int -> Bool grafica :: Int -> IO ()

tales que

(esCubifinito n) se verifica si n es un número cubifinito. Por ejemplo,

     esCubifinito 1      ==  True
     esCubifinito 10     ==  True
     esCubifinito 1243   ==  True
     esCubifinito 87418  ==  True
     esCubifinito 513    ==  False

esCubifinito 1 == True

esCubifinito 10 == True

esCubifinito 1243 == True

esCubifinito 87418 == True

esCubifinito 513 == False

(grafica n) dibuja la gráfica de la sucesión de los primeros n números cubifinitos. Por ejemplo, al evaluar (grafica 50) se dibuja

Soluciones

import Graphics.Gnuplot.Simple

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

esCubifinito :: Int -> Bool
esCubifinito n = aux [n]
  where aux (n:ns) | n == 1      = True
                   | n `elem` ns = False
                   | otherwise   = aux (sumaCubosDigitos n : n : ns)

-- (sumaCubosDigitos b) es la suma de los cubos de los dígitos de n. Por
-- ejemplo, 
--    sumaCubosDigitos 513  ==  153
sumaCubosDigitos :: Int -> Int
sumaCubosDigitos = sum . map (^3) . digitos

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 513  ==  [5,1,3]
digitos :: Int -> [Int]
digitos n = [read [c] | c <- show n]

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

esCubifinito2 :: Int -> Bool
esCubifinito2 n = primerRepetido (orbita n) == 1

-- (orbita n) es la lista cuyo primer elemento es n y los siguientes se
-- obtienen sumando los cubos de los digitos del elemento anterior. Por
-- ejemplo,  
--    take 9 (orbita 2)  ==  [2,8,512,134,92,737,713,371,371]
orbita :: Int -> [Int]
orbita n = iterate sumaCubosDigitos n

-- (primerRepetido xs) es el primer elemento repetido de la lista
--  xs. Por ejemplo, 
--    primerRepetido [3,7,5,7,2]  ==  7
primerRepetido :: Eq a => [a] -> a
primerRepetido xs = aux xs []
  where
    aux (x:xs') ys | x `elem` ys = x
                   | otherwise   = aux xs' (x:ys) 

grafica :: Int -> IO ()
grafica n = 
    plotList [Key Nothing, PNG "Numeros_cubifinitos.png"]
             (zip [1..n] [x | x <- [1..], esCubifinito x])

import Graphics.Gnuplot.Simple

-- 1ª solución

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

esCubifinito :: Int -> Bool

esCubifinito n = aux [n]

where aux (n:ns) | n == 1 = True

| n `elem` ns = False

| otherwise = aux (sumaCubosDigitos n : n : ns)

-- (sumaCubosDigitos b) es la suma de los cubos de los dígitos de n. Por

-- ejemplo,

-- sumaCubosDigitos 513 == 153

sumaCubosDigitos :: Int -> Int

sumaCubosDigitos = sum . map (^3) . digitos

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

-- digitos 513 == [5,1,3]

digitos :: Int -> [Int]

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

-- 2ª solución

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

esCubifinito2 :: Int -> Bool

esCubifinito2 n = primerRepetido (orbita n) == 1

-- (orbita n) es la lista cuyo primer elemento es n y los siguientes se

-- obtienen sumando los cubos de los digitos del elemento anterior. Por

-- ejemplo,

-- take 9 (orbita 2) == [2,8,512,134,92,737,713,371,371]

orbita :: Int -> [Int]

orbita n = iterate sumaCubosDigitos n

-- (primerRepetido xs) es el primer elemento repetido de la lista

-- xs. Por ejemplo,

-- primerRepetido [3,7,5,7,2] == 7

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

primerRepetido xs = aux xs []

where

aux (x:xs') ys | x `elem` ys = x

| otherwise = aux xs' (x:ys)

grafica :: Int -> IO ()

grafica n =

plotList [Key Nothing, PNG "Numeros_cubifinitos.png"]

(zip [1..n] [x | x <- [1..], esCubifinito x])

Generadores de números de Gabonacci

PorJosé A. Alonso 9-marzo-201720-marzo-2017

Los números de Gabonacci generados por (a,b) son los elementos de la sucesión de Gabonacci definida por

   G(0) = a
   G(1) = b
   G(n) = G(n-2) + G(n-1), si n > 1

G(0) = a

G(1) = b

G(n) = G(n-2) + G(n-1), si n > 1

Por ejemplo, la sucesión de Gabonacci generada por (2,5) es 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, …

Un número pertenece a distintas sucesiones de Gabonacci. Por ejemplo, el 9 pertenece a las sucesiones de Gabonacci generados por (3,3), (1,4) y (4,5).

El menor generador de Gabonacci de un número x es el par (a,b), con 1 ≤ a ≤ b, tal que (a,b) es un generador de Gabonacci de x y no existe ningún generador de Gabonacci de x (a’,b’) tal que b’ < b ó b’ = b y a’ < a. Por ejemplo, el menor generador de Gabonacci de 9 es (3,3).

Definir la función

   menorGenerador :: Integer -> (Integer,Integer)

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

tal que (menorGenerador x) es el menor generador de Gabonacci de x. Por ejemplo,

   menorGenerador 9          ==  (3,3)
   menorGenerador 7          ==  (1,3)
   menorGenerador 5          ==  (1,1)
   menorGenerador 27         ==  (3,7)
   menorGenerador 57         ==  (4,9)
   menorGenerador 218        ==  (10,21)
   menorGenerador 1121       ==  (20,41)
   menorGenerador 89         ==  (1,1)
   menorGenerador 123        ==  (1,3)
   menorGenerador 1000       ==  (2,10)
   menorGenerador 842831057  ==  (2,7)
   menorGenerador 1573655    ==  (985,1971)

menorGenerador 9 == (3,3)

menorGenerador 7 == (1,3)

menorGenerador 5 == (1,1)

menorGenerador 27 == (3,7)

menorGenerador 57 == (4,9)

menorGenerador 218 == (10,21)

menorGenerador 1121 == (20,41)

menorGenerador 89 == (1,1)

menorGenerador 123 == (1,3)

menorGenerador 1000 == (2,10)

menorGenerador 842831057 == (2,7)

menorGenerador 1573655 == (985,1971)

Soluciones

menorGenerador :: Integer -> (Integer,Integer)
menorGenerador = head . generadores

generadores :: Integer -> [(Integer,Integer)]
generadores x = [(a,b) | b <- [1..x]
                       , a <- [1..b]
                       , pertenece x (gabonacci a b)]

gabonacci :: Integer -> Integer -> [Integer]
gabonacci a b = aux
  where aux = a : scanl (+) b aux

pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)

menorGenerador :: Integer -> (Integer,Integer)

menorGenerador = head . generadores

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

generadores x = [(a,b) | b <- [1..x]

, a <- [1..b]

, pertenece x (gabonacci a b)]

gabonacci :: Integer -> Integer -> [Integer]

gabonacci a b = aux

where aux = a : scanl (+) b aux

pertenece :: Integer -> [Integer] -> Bool

pertenece x ys =

x == head (dropWhile (<x) ys)

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

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

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

Definir las funciones

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

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

tales que

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

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

aproximacionPi 5 == 3.140331156954753

aproximacionPi 10 == 3.1415914215112

aproximacionPi 15 == 3.141592652386592

aproximacionPi 20 == 3.1415926535886207

aproximacionPi 25 == 3.141592653589795

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

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

errorPi 0.1 == 2

errorPi 0.01 == 4

errorPi 0.001 == 6

errorPi 0.0001 == 7

errorPi 1e-4 == 7

errorPi 1e-14 == 24

pi == 3.141592653589793

aproximacionPi 24 == 3.1415926535897913

Soluciones

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

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

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

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

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

-- 1ª definición de aproximacionPi

aproximacionPi :: Int -> Double

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

where

aux 0 = 1

aux 1 = sqrt 2

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

-- 2ª definición de aproximacionPi

aproximacionPi2 :: Int -> Double

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

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

-- 3ª definición de aproximaxionPi

aproximacionPi3 :: Int -> Double

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

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

-- 1ª definición de errorPi

errorPi :: Double -> Int

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

, abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi

errorPi2 :: Double -> Int

errorPi2 x = until aceptable (+1) 1

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

Cálculo de pi usando el producto de Wallis

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

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

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

π 2 2 4 4 6 6 8 8

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

2 1 3 3 5 5 7 7 9

Definir las funciones

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

factoresWallis :: [Rational]

productosWallis :: [Rational]

aproximacionPi :: Int -> Double

errorPi :: Double -> Int

tales que

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

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

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

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

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

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

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

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

aproximacionPi 20 == 3.2137849402931895

aproximacionPi 200 == 3.1493784731686008

aproximacionPi 2000 == 3.142377365093878

aproximacionPi 20000 == 3.141671186534396

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

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

errorPi 0.1 == 14

errorPi 0.01 == 155

errorPi 0.001 == 1569

errorPi 0.0001 == 15707

Soluciones

import Data.Ratio

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

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

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

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

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

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

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

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

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

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

import Data.Ratio

factoresWallis :: [Rational]

factoresWallis =

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

productosWallis :: [Rational]

productosWallis = scanl1 (*) factoresWallis

aproximacionPi :: Int -> Double

aproximacionPi n =

fromRational (2 * productosWallis !! n)

errorPi :: Double -> Int

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

, abs (pi - aproximacionPi n) < x]

-- 2ª definición de errorPi

errorPi2 :: Double -> Int

errorPi2 x =

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

| y <- productosWallis])

-- 2ª definición de aproximacionPi

aproximacionPi2 :: Int -> Double

aproximacionPi2 n =

2 * productosWallis2 !! n

productosWallis2 :: [Double]

productosWallis2 = scanl1 (*) factoresWallis2

factoresWallis2 :: [Double]

factoresWallis2 =

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

-- 3ª definición de errorPi

errorPi3 :: Double -> Int

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

, abs (pi - aproximacionPi2 n) < x]

-- Comparación de eficiencia

-- λ> errorPi 0.001

-- 1569

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

-- λ> errorPi2 0.001

-- 1569

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

-- λ> errorPi3 0.001

-- 1569

-- (0.04 secs, 0 bytes)

Máximo producto de pares en la lista

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

Definir la función

  maximoProducto :: [Int] -> Maybe Int

1	maximoProducto :: [Int] -> Maybe Int

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

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

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

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

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

maximoProducto [2,4] == Nothing

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

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

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

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

Soluciones

import Data.List (delete, nub, sort)

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

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

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

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

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

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

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

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

import Data.List (delete, nub, sort)

-- 1ª solución

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

maximoProducto1 :: [Int] -> Maybe Int

maximoProducto1 xs

| null zs = Nothing

| otherwise = Just (head zs)

where

ys = reverse (sort xs)

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

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

-- elementos de xs. Por ejemplo,

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

productos :: [Int] -> [Int]

productos xs =

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

-- 2ª solución

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

maximoProducto2 :: [Int] -> Maybe Int

maximoProducto2 xs = aux (reverse (sort xs))

where aux [] = Nothing

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

| otherwise = aux ys

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

esProducto y [] = False

esProducto y (x:xs) =

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

where (d,m) = divMod y x

-- Comparación de eficiencia

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

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

-- Just 10000

-- (2.60 secs, 0 bytes)

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

-- Just 10000

-- (0.01 secs, 0 bytes)

Suma minimal de productos de pares de elementos consecutivos

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

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

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

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

Definir las funciones

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

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

tales que

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

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

minimaSumaProductos [1..4] == 10

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

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

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

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

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

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

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

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

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

Soluciones

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

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

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

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

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

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

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

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

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

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

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

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

import Data.List (sort, permutations)

import Test.QuickCheck

-- 1ª definición

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

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

minimaSumaProductos xs =

minimum [sumaProductos ys | ys <- permutations xs]

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

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

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

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

sumaProductos [] = 0

sumaProductos [x] = x

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

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

permutacionMinimal xs =

head [ys | ys <- yss

, sumaProductos ys == m]

where yss = permutations xs

m = minimaSumaProductos xs

-- 2ª definición

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

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

permutacionMinimal2 xs =

intercala ys (reverse zs)

where n = length xs

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

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

intercala xs ys =

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

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

minimaSumaProductos2 =

sumaProductos . permutacionMinimal2

-- Equivalencia

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

prop_equivalencia :: [Int] -> Property

prop_equivalencia xs =

even (length xs) ==>

minimaSumaProductos xs == minimaSumaProductos2 xs

-- La comprobación es

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

-- +++ OK, passed 100 tests.

Máxima potencia que divide al factorial

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

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

Definir la función

   maxPotDivFact :: Integer -> Integer -> Integer

1	maxPotDivFact :: Integer -> Integer -> Integer

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

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

maxPotDivFact 2 5 == 3

maxPotDivFact 3 6 == 2

maxPotDivFact 2 10 == 8

maxPotDivFact 3 10 == 4

maxPotDivFact 2 (10^2) == 97

maxPotDivFact 2 (10^3) == 994

maxPotDivFact 2 (10^4) == 9995

maxPotDivFact 2 (10^5) == 99994

maxPotDivFact 2 (10^6) == 999993

maxPotDivFact 3 (10^5) == 49995

maxPotDivFact 3 (10^6) == 499993

maxPotDivFact 7 (10^5) == 16662

maxPotDivFact 7 (10^6) == 166664

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

Soluciones

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

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

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

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

import Data.List (genericIndex, genericTake)

import Data.Numbers.Primes (primes)

import Test.QuickCheck

-- 1ª definición

maxPotDivFact :: Integer -> Integer -> Integer

maxPotDivFact p n =

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

where f = product [1..n]

-- 1ª definición

maxPotDivFact2 :: Integer -> Integer -> Integer

maxPotDivFact2 p n

| n < p = 0

| otherwise = m + maxPotDivFact2 p m

where m = n `div` p

-- 3ª definición

maxPotDivFact3 :: Integer -> Integer -> Integer

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

-- Comparación de eficiencia

-- λ> maxPotDivFact 2 (10^4)

-- 9995

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

-- λ> maxPotDivFact2 2 (10^4)

-- 9995

-- (0.01 secs, 0 bytes)

-- λ> maxPotDivFact2 2 (10^4)

-- 9995

-- (0.01 secs, 0 bytes)

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

-- 20000

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

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

-- 20000

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

La sucesión «Mira y di»

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

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

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

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

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

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

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

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

Definir la función

  sucMiraYDi :: Integer -> [Integer]

1	sucMiraYDi :: Integer -> [Integer]

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

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

λ> take 9 (sucMiraYdi 1)

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

λ> take 5 (sucMiraYdi 2017)

[2017,12101117,111211103117,31123110132117,1321121321101113122117]

λ> take 7 (sucMiraYDi 22)

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

λ> (sucMiraYDi 1) !! 11

3113112221232112111312211312113211

λ> (sucMiraYDi 1) !! 12

1321132132111213122112311311222113111221131221

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

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

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

Definir la función

   aproximacionConway :: Integer -> Double -> Int

1	aproximacionConway :: Integer -> Double -> Int

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

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

aproximacionConway 1 0.3 == 3

aproximacionConway 1 0.1 == 5

aproximacionConway 1 0.01 == 9

aproximacionConway 1 0.001 == 24

aproximacionConway 1 0.0001 == 43

aproximacionConway 2 0.0001 == 47

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

Soluciones

import Data.List (genericLength, group)

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

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

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

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

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

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

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

constanteConway :: Double
constanteConway = 1.303577269

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

import Data.List (genericLength, group)

-- 1ª solución

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

sucMiraYdi :: Integer -> [Integer]

sucMiraYdi = iterate di

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

-- di 1 == 11

-- di 11 == 21

-- di 21 == 1211

-- di 1211 == 111221

-- di 111221 == 312211

-- di 312211 == 13112221

di :: Integer -> Integer

di = read . concatMap aux . group . show

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

-- 2ª solución

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

sucMiraYdi2 :: Integer -> [Integer]

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

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

-- Constante de Conway

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

aproximacionConway :: Integer -> Double -> Int

aproximacionConway n e =

length (takeWhile aux (razonesMiraYdi n))

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

constanteConway :: Double

constanteConway = 1.303577269

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

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

-- anterior. Por ejemplo,

-- λ> take 10 (razonesMiraYdi 1)

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

-- λ> take 7 (razonesMiraYdi 10)

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

razonesMiraYdi :: Integer -> [Double]

razonesMiraYdi n =

zipWith (/) (tail xs) xs

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

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Soluciones

Entradas recientes

Buscar

Correo electrónico