febrero 2016 – Exercitium

Particiones en sumas de cuadrados

PorJosé A. Alonso 26-febrero-20161-mayo-2016

Definir las funciones

   particionesCuadradas        :: Integer -> [[Integer]]
   nParticionesCuadradas       :: Integer -> Integer
   graficaParticionesCuadradas :: Integer -> IO ()

particionesCuadradas :: Integer -> [[Integer]]

nParticionesCuadradas :: Integer -> Integer

graficaParticionesCuadradas :: Integer -> IO ()

tales que

(particionesCuadradas n) es la listas de conjuntos de cuadrados cuya suma es n. Por ejemplo,

      particionesCuadradas 3  ==  [[1,1,1]]
      particionesCuadradas 4  ==  [[4],[1,1,1,1]]
      particionesCuadradas 9  ==  [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]]

particionesCuadradas 3 == [[1,1,1]]

particionesCuadradas 4 == [[4],[1,1,1,1]]

particionesCuadradas 9 == [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]]

(nParticionesCuadradas n) es el número de conjuntos de cuadrados cuya suma es n. Por ejemplo,

      nParticionesCuadradas 3    ==  1
      nParticionesCuadradas 4    ==  2
      nParticionesCuadradas 9    ==  4
      nParticionesCuadradas 50   ==  104
      nParticionesCuadradas 100  ==  1116
      nParticionesCuadradas 200  ==  27482

nParticionesCuadradas 3 == 1

nParticionesCuadradas 4 == 2

nParticionesCuadradas 9 == 4

nParticionesCuadradas 50 == 104

nParticionesCuadradas 100 == 1116

nParticionesCuadradas 200 == 27482

(graficaParticionesCuadradas n) dibuja la gráfica de la sucesión

      [nParticionesCuadradas k | k <- [0..n]]

1	[nParticionesCuadradas k \| k <- [0..n]]

Por ejemplo, con (graficaParticionesCuadradas 100) se obtiene

Soluciones

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

-- Definición de particiones cuadradas
-- ===================================

particionesCuadradas :: Integer -> [[Integer]]
particionesCuadradas n = 
    particiones n (reverse $ takeWhile (<=n) cuadrados)

-- cuadrados es la lista de los cuadrados. Por ejemplo,
--    take 12 cuadrados  ==  [1,4,9,16,25,36,49,64,81,100,121,144]
cuadrados :: [Integer]
cuadrados = map (^2) [1..]

-- (particiones n xs) es la lista de las particiones de n como suma de
-- elementos de xs, donde xs es una lista no creciente. Por ejemplo,
--    particiones 10 [7,4,2]  ==  [[4,4,2],[4,2,2,2],[2,2,2,2,2]]
--    particiones 11 [7,4,2]  ==  [[7,4],[7,2,2]]
--    particiones  5 [7,4,2]  ==  []
particiones:: Integer -> [Integer] -> [[Integer]]
particiones _ [] = []
particiones n (x:xs)
    | x >  n    = particiones n xs
    | x == n    = [n] : particiones n xs
    | otherwise = map (x:) (particiones (n-x) (x:xs)) ++ particiones n xs

-- 1ª definición de nParticionesCuadradas       
nParticionesCuadradas1 :: Integer -> Integer
nParticionesCuadradas1 = genericLength . particionesCuadradas

-- 2ª definición nParticionesCuadradas   
nParticionesCuadradas2 :: Integer -> Integer
nParticionesCuadradas2 n = aux n (reverse $ takeWhile (<=n) cuadrados) where
    aux _ [] = 0
    aux n ys@(x:xs) | x >  n    = aux n xs
                    | x == n    = 1 + aux n xs
                    | otherwise = aux (n-x) ys + aux n xs

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

--    λ> nParticionesCuadradas1 250
--    94987
--    (4.21 secs, 3,256,031,528 bytes)
--    λ> nParticionesCuadradas2 250
--    94987
--    (2.93 secs, 1,714,701,504 bytes)

-- Definición de graficaParticionesCuadradas
-- =========================================
                                  
graficaParticionesCuadradas :: Integer  -> IO ()
graficaParticionesCuadradas n = 
    plotList [Key Nothing] [nParticionesCuadradas2 k | k <- [0..n]]

import Data.List (genericLength)

import Graphics.Gnuplot.Simple

-- Definición de particiones cuadradas

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

particionesCuadradas :: Integer -> [[Integer]]

particionesCuadradas n =

particiones n (reverse $ takeWhile (<=n) cuadrados)

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

-- take 12 cuadrados == [1,4,9,16,25,36,49,64,81,100,121,144]

cuadrados :: [Integer]

cuadrados = map (^2) [1..]

-- (particiones n xs) es la lista de las particiones de n como suma de

-- elementos de xs, donde xs es una lista no creciente. Por ejemplo,

-- particiones 10 [7,4,2] == [[4,4,2],[4,2,2,2],[2,2,2,2,2]]

-- particiones 11 [7,4,2] == [[7,4],[7,2,2]]

-- particiones 5 [7,4,2] == []

particiones:: Integer -> [Integer] -> [[Integer]]

particiones _ [] = []

particiones n (x:xs)

| x > n = particiones n xs

| x == n = [n] : particiones n xs

| otherwise = map (x:) (particiones (n-x) (x:xs)) ++ particiones n xs

-- 1ª definición de nParticionesCuadradas

nParticionesCuadradas1 :: Integer -> Integer

nParticionesCuadradas1 = genericLength . particionesCuadradas

-- 2ª definición nParticionesCuadradas

nParticionesCuadradas2 :: Integer -> Integer

nParticionesCuadradas2 n = aux n (reverse $ takeWhile (<=n) cuadrados) where

aux _ [] = 0

aux n ys@(x:xs) | x > n = aux n xs

| x == n = 1 + aux n xs

| otherwise = aux (n-x) ys + aux n xs

-- Comparación de eficiencia

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

-- λ> nParticionesCuadradas1 250

-- 94987

-- (4.21 secs, 3,256,031,528 bytes)

-- λ> nParticionesCuadradas2 250

-- 94987

-- (2.93 secs, 1,714,701,504 bytes)

-- Definición de graficaParticionesCuadradas

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

graficaParticionesCuadradas :: Integer -> IO ()

graficaParticionesCuadradas n =

plotList [Key Nothing] [nParticionesCuadradas2 k | k <- [0..n]]

Referencias

Sucesión A001156 de OEIS.

Números automórficos

PorJosé A. Alonso 25-febrero-20163-marzo-2016

Un número n es automórfico si los últimos dígitos de su cuadrado son los dígitos de n. Por ejemplo, 5, 6, 76 y 890625 son números automórficos ya que 5² = 25, 6² = 36, 76² = 5776 y 890625² = 793212890625.

Definir la sucesión

   automorficos :: [Integer]

1	automorficos :: [Integer]

tal que sus elementos son los números automórficos. Por ejemplo,

   λ> take 11 automorficos
   [1,5,6,25,76,376,625,9376,90625,109376,890625]
   λ> automorficos !! 30
   56259918212890625

λ> take 11 automorficos

[1,5,6,25,76,376,625,9376,90625,109376,890625]

λ> automorficos !! 30

56259918212890625

Soluciones

import Data.List (isSuffixOf, nub, sort)

automorficos :: [Integer] 
automorficos = filter esAutomorfico [1..]

esAutomorfico :: Integer -> Bool 
esAutomorfico n = show n `isSuffixOf` show (n*n)

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

automorficos2 :: [Integer] 
automorficos2 = nub (1 : concat [sort [a,b] |
                                 k <- [1..], 
                                 let a = 5^(2^k) `mod` 10^k, 
                                 let b = 10^k - a + 1])

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

-- λ> automorficos !! 12 
-- 7109376 
-- (16.64 secs, 6,759,638,824 bytes)
-- λ> automorficos2 !! 12 
-- 7109376 
-- (0.00 secs, 0 bytes)

import Data.List (isSuffixOf, nub, sort)

automorficos :: [Integer]

automorficos = filter esAutomorfico [1..]

esAutomorfico :: Integer -> Bool

esAutomorfico n = show n `isSuffixOf` show (n*n)

-- 2ª definición

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

automorficos2 :: [Integer]

automorficos2 = nub (1 : concat [sort [a,b] |

k <- [1..],

let a = 5^(2^k) `mod` 10^k,

let b = 10^k - a + 1])

-- Comparación de eficiencia

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

-- λ> automorficos !! 12

-- 7109376

-- (16.64 secs, 6,759,638,824 bytes)

-- λ> automorficos2 !! 12

-- 7109376

-- (0.00 secs, 0 bytes)

Referencias

J.D. Cook, Curious numbers.
Wikipedia, Automorphic number.
E.W. Weisstein, Automorphic number en MathWorld.
N.J.A. Sloane Sucesion A003226 en OEIS.

Sumas de potencias de 3 primos

PorJosé A. Alonso 24-febrero-201625-marzo-2022

Los primeros números de la forma p²+q³+r⁴, con p, q y r primos son

   28 = 2² + 2³ + 2⁴
   33 = 3² + 2³ + 2⁴
   47 = 2² + 3³ + 2⁴
   49 = 5² + 2³ + 2⁴

28 = 2² + 2³ + 2⁴

33 = 3² + 2³ + 2⁴

47 = 2² + 3³ + 2⁴

49 = 5² + 2³ + 2⁴

Definir la sucesión

   sumas3potencias :: [Integer]

1	sumas3potencias :: [Integer]

cuyos elementos son los números que se pueden escribir de la forma p²+q³+r⁴, con p, q y r primos. Por ejemplo,

   λ> take 15 sumas3potencias
   [28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]
   λ> sumas3potencias !! 234567
   8953761

λ> take 15 sumas3potencias

[28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]

λ> sumas3potencias !! 234567

8953761

Soluciones

import Data.Numbers.Primes (primes)

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

sumas3potencias1 :: [Integer]
sumas3potencias1 = filter esTripleSuma [1..]
 
-- (esTripleSuma n) se verifica si n se puede escribir de la forma
-- p²+q³+r⁴, con p, q y r primos. Por ejemplo, 
--    esTripleSuma 33  ==  True
--    esTripleSuma 45  ==  False
esTripleSuma :: Integer -> Bool
esTripleSuma = not . null . triplesSumas  

-- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales
-- que p²+q³+r⁴ = n. Por ejemplo,
--    triplesSumas 33   ==  [(3,2,2)]
--    triplesSumas 145  ==  [(11,2,2),(2,5,2)]
--    triplesSumas 45   ==  []
triplesSumas :: Integer -> [(Integer,Integer,Integer)]
triplesSumas n =  
    [(p,q,r) 
    | r <- xs, 
      q <- xs, 
      let p2 = n - q^3 - r^4,
      let p = (floor . sqrt . fromIntegral) p2,
      p*p == p2,
      isPrime p]
    where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes

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

sumas3potencias2 :: [Integer]
sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs)

sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer]
sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
    where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys
 
as = map (^2) primes
bs = map (^3) primes
cs = map (^4) primes

import Data.Numbers.Primes (primes)

-- 1ª solución

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

sumas3potencias1 :: [Integer]

sumas3potencias1 = filter esTripleSuma [1..]

-- (esTripleSuma n) se verifica si n se puede escribir de la forma

-- p²+q³+r⁴, con p, q y r primos. Por ejemplo,

-- esTripleSuma 33 == True

-- esTripleSuma 45 == False

esTripleSuma :: Integer -> Bool

esTripleSuma = not . null . triplesSumas

-- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales

-- que p²+q³+r⁴ = n. Por ejemplo,

-- triplesSumas 33 == [(3,2,2)]

-- triplesSumas 145 == [(11,2,2),(2,5,2)]

-- triplesSumas 45 == []

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

triplesSumas n =

[(p,q,r)

| r <- xs,

q <- xs,

let p2 = n - q^3 - r^4,

let p = (floor . sqrt . fromIntegral) p2,

p*p == p2,

isPrime p]

where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes

-- 2ª solución

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

sumas3potencias2 :: [Integer]

sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs)

sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer]

sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs]

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

mezclaTodas = foldr1 xmezcla

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

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

mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)

| x == y = x : mezcla xs ys

| x > y = y : mezcla (x:xs) ys

as = map (^2) primes

bs = map (^3) primes

cs = map (^4) primes

Múltiplos con ceros y unos

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

Se observa que todos los primeros números naturales tienen al menos un múltiplo no nulo que está formado solamente por ceros y unos. Por ejemplo, 1×10=10, 2×5=10, 3×37=111, 4×25=100, 5×2=10, 6×185=1110; 7×143=1001; 8X125=1000; 9×12345679=111111111.

Definir la función

   multiplosCon1y0 :: Integer -> [Integer]

1	multiplosCon1y0 :: Integer -> [Integer]

tal que (multiplosCon1y0 n) es la lista de los múltiplos de n cuyos dígitos son 1 ó 0. Por ejemplo,

   take 4 (multiplosCon1y0 3)      ==  [111,1011,1101,1110]
   take 3 (multiplosCon1y0 23)     ==  [110101,1011011,1101010]
   head (multiplosCon1y0 1234658)  ==  110101101101000000110

take 4 (multiplosCon1y0 3) == [111,1011,1101,1110]

take 3 (multiplosCon1y0 23) == [110101,1011011,1101010]

head (multiplosCon1y0 1234658) == 110101101101000000110

Comprobar con QuickCheck que todo entero positivo tiene algún múltiplo cuyos dígitos son 1 ó 0.

Soluciones

import Test.QuickCheck

multiplosCon1y0 :: Integer -> [Integer] 
multiplosCon1y0 n = 
    [x | x <- numerosCon1y0, 
         x `rem` n == 0] 

-- numerosCon1y0 es la lista de los números cuyos dígitos son 1 ó 0. Por
-- ejemplo,  
--    ghci> take 15 numerosCon1y0
--    [1,10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111]
numerosCon1y0 :: [Integer]
numerosCon1y0 = 1 : concat [[10*x,10*x+1] | x <- numerosCon1y0]

-- La propiedad es
prop_existe_multiplosCon1y0 :: Integer -> Property
prop_existe_multiplosCon1y0 n = 
    n > 0 ==> multiplosCon1y0 n /= []

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

import Test.QuickCheck

multiplosCon1y0 :: Integer -> [Integer]

multiplosCon1y0 n =

[x | x <- numerosCon1y0,

x `rem` n == 0]

-- numerosCon1y0 es la lista de los números cuyos dígitos son 1 ó 0. Por

-- ejemplo,

-- ghci> take 15 numerosCon1y0

-- [1,10,11,100,101,110,111,1000,1001,1010,1011,1100,1101,1110,1111]

numerosCon1y0 :: [Integer]

numerosCon1y0 = 1 : concat [[10*x,10*x+1] | x <- numerosCon1y0]

-- La propiedad es

prop_existe_multiplosCon1y0 :: Integer -> Property

prop_existe_multiplosCon1y0 n =

n > 0 ==> multiplosCon1y0 n /= []

-- La comprobación es

-- ghci> quickCheck prop_existe_multiplosCon1y0

-- +++ OK, passed 100 tests.

Regresión lineal

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

Dadas dos listas de valores

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

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

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

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

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

Definir la función

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

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

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

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

ejX, ejY :: [Double]

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

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

se tiene

   λ> regresionLineal ejX ejY
   (5.195045748716805,0.9218924347243919)

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

Definir el procedimiento

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

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

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

Soluciones

import Graphics.Gnuplot.Simple

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

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

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

import Graphics.Gnuplot.Simple

ejX, ejY :: [Double]

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

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

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

regresionLineal xs ys = (a,b)

where n = fromIntegral (length xs)

sumX = sum xs

sumY = sum ys

sumX2 = sum (zipWith (*) xs xs)

sumY2 = sum (zipWith (*) ys ys)

sumXY = sum (zipWith (*) xs ys)

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

a = (sumY - b*sumX) / n

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

grafica xs ys =

plotPathsStyle

[YRange (0,10+mY)]

[(defaultStyle {plotType = Points,

lineSpec = CustomStyle [LineTitle "Datos",

PointType 2,

PointSize 2.5]},

zip xs ys),

(defaultStyle {plotType = Lines,

lineSpec = CustomStyle [LineTitle "Ajuste",

LineWidth 2]},

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

where (a,b) = regresionLineal xs ys

mX = maximum xs

mY = maximum ys

Dígitos en la factorización

PorJosé A. Alonso 19-febrero-20162-marzo-2016

El enunciado del problema 652 de Números y algo más es el siguiente

Si factorizamos los factoriales de un número en función de sus divisores primos y sus potencias, ¿Cuál es el menor número n tal que entre los factores primos y los exponentes de estos, n! contiene los dígitos del cero al nueve? Por ejemplo

6! = 2⁴x3²x5¹, le faltan los dígitos 0,6,7,8 y 9

12! = 2¹⁰x3⁵x5²x7¹x11¹, le faltan los dígitos 4,6,8 y 9

Definir la función

   digitosDeFactorizacion :: Integer -> [Integer]

1	digitosDeFactorizacion :: Integer -> [Integer]

tal que (digitosDeFactorizacion n) es el conjunto de los dígitos que aparecen en la factorización de n. Por ejemplo,

   digitosDeFactorizacion (factorial 6)   ==  [1,2,3,4,5]
   digitosDeFactorizacion (factorial 12)  ==  [0,1,2,3,5,7]

1 2	digitosDeFactorizacion (factorial 6) == [1,2,3,4,5] digitosDeFactorizacion (factorial 12) == [0,1,2,3,5,7]

Usando la función anterior, calcular la solución del problema.

Comprobar con QuickCheck que si n es mayor que 100, entonces

   digitosDeFactorizacion (factorial n) == [0..9]

1	digitosDeFactorizacion (factorial n) == [0..9]

Soluciones

import Data.List (genericLength, group, nub, sort)
import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck

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

digitosDeFactorizacion1 :: Integer -> [Integer]
digitosDeFactorizacion1 n =
   sort (nub (concat [digitos x | x <- numerosDeFactorizacion n]))

-- (digitos n) es la lista de los digitos del número n. Por ejemplo, 
--    digitos 320274  ==  [3,2,0,2,7,4]
digitos :: Integer -> [Integer]
digitos n = [read [x] | x <- show n]

-- (numerosDeFactorizacion n) es el conjunto de los números en la
-- factorización de n. Por ejemplo,
--    numerosDeFactorizacion 60  ==  [1,2,3,5]
numerosDeFactorizacion :: Integer -> [Integer]
numerosDeFactorizacion n = 
   sort (nub (aux (factorizacion n)))
   where aux [] = []
         aux ((x,y):zs) = x : y : aux zs

-- (factorización n) es la factorización de n. Por ejemplo,
--    factorizacion 300  ==  [(2,2),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n = 
    [(head xs, genericLength xs) | xs <- group (factorizacion' n)]

-- (factorizacion' n) es la lista de todos los factores primos de n; es
-- decir, es una lista de números primos cuyo producto es n. Por ejemplo,
--    factorizacion 300  ==  [2,2,3,5,5]
factorizacion' :: Integer -> [Integer]
factorizacion' n | n == 1    = []
                 | otherwise = x : factorizacion' (div n x)
                 where x = menorFactor n

-- (menorFactor n) es el menor factor primo de n. Por ejemplo,
--    menorFactor 15  ==  3
menorFactor :: Integer -> Integer
menorFactor n = head [x | x <- [2..], rem n x == 0]

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

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

digitosDeFactorizacion2 :: Integer -> [Integer]
digitosDeFactorizacion2 n =
   sort (nub (concat [digitos x | x <- numerosDeFactorizacion2 n]))

-- (numerosDeFactorizacion2 n) es el conjunto de los números en la
-- factorización de n. Por ejemplo,
--    numerosDeFactorizacion2 60  ==  [1,2,3,5]
numerosDeFactorizacion2 :: Integer -> [Integer]
numerosDeFactorizacion2 n = 
    sort (nub (aux (factorizacion2 n)))
    where aux xs = concat [[a,b] | (a,b) <- xs]

-- (factorización2 n) es la factorización de n. Por ejemplo,
--    factorizacion2 300  ==  [(2,2),(3,1),(5,2)]
factorizacion2 :: Integer -> [(Integer,Integer)]
factorizacion2 n =
    [(head xs, genericLength xs) | xs <- group (primeFactors n)]

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

digitosDeFactorizacion3 :: Integer -> [Integer]
digitosDeFactorizacion3 n =
    sort (nub (concat [digitos x | x <- aux (group (primeFactors n))]))
    where aux  []            = []
          aux (ys@(y:_):xss) = y : genericLength ys : aux xss

-- Definición
-- ==========

digitosDeFactorizacion :: Integer -> [Integer]
digitosDeFactorizacion = digitosDeFactorizacion3

-- Solución
-- ========

-- Para calcular la solución, se define la constante
solucion :: Integer
solucion = 
    head [n | n <- [1..], digitosDeFactorizacion (factorial n) == [0..9]]

-- El cálculo de la solución es
--    ghci> solucion2
--    49

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

-- La propiedad es
prop_completa :: Integer -> Bool
prop_completa n =
    digitosDeFactorizacion (factorial n1) == [0..9]
    where n1 = 101 + abs n

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

100

101

102

103

104

105

106

107

108

109

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

import Data.Numbers.Primes (primeFactors)

import Test.QuickCheck

-- 1ª definición

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

digitosDeFactorizacion1 :: Integer -> [Integer]

digitosDeFactorizacion1 n =

sort (nub (concat [digitos x | x <- numerosDeFactorizacion n]))

-- (digitos n) es la lista de los digitos del número n. Por ejemplo,

-- digitos 320274 == [3,2,0,2,7,4]

digitos :: Integer -> [Integer]

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

-- (numerosDeFactorizacion n) es el conjunto de los números en la

-- factorización de n. Por ejemplo,

-- numerosDeFactorizacion 60 == [1,2,3,5]

numerosDeFactorizacion :: Integer -> [Integer]

numerosDeFactorizacion n =

sort (nub (aux (factorizacion n)))

where aux [] = []

aux ((x,y):zs) = x : y : aux zs

-- (factorización n) es la factorización de n. Por ejemplo,

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

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

factorizacion n =

[(head xs, genericLength xs) | xs <- group (factorizacion' n)]

-- (factorizacion' n) es la lista de todos los factores primos de n; es

-- decir, es una lista de números primos cuyo producto es n. Por ejemplo,

-- factorizacion 300 == [2,2,3,5,5]

factorizacion' :: Integer -> [Integer]

factorizacion' n | n == 1 = []

| otherwise = x : factorizacion' (div n x)

where x = menorFactor n

-- (menorFactor n) es el menor factor primo de n. Por ejemplo,

-- menorFactor 15 == 3

menorFactor :: Integer -> Integer

menorFactor n = head [x | x <- [2..], rem n x == 0]

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

-- factorial 5 == 120

factorial :: Integer -> Integer

factorial n = product [1..n]

-- 2ª definición

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

digitosDeFactorizacion2 :: Integer -> [Integer]

digitosDeFactorizacion2 n =

sort (nub (concat [digitos x | x <- numerosDeFactorizacion2 n]))

-- (numerosDeFactorizacion2 n) es el conjunto de los números en la

-- factorización de n. Por ejemplo,

-- numerosDeFactorizacion2 60 == [1,2,3,5]

numerosDeFactorizacion2 :: Integer -> [Integer]

numerosDeFactorizacion2 n =

sort (nub (aux (factorizacion2 n)))

where aux xs = concat [[a,b] | (a,b) <- xs]

-- (factorización2 n) es la factorización de n. Por ejemplo,

-- factorizacion2 300 == [(2,2),(3,1),(5,2)]

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

factorizacion2 n =

[(head xs, genericLength xs) | xs <- group (primeFactors n)]

-- 3ª definición

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

digitosDeFactorizacion3 :: Integer -> [Integer]

digitosDeFactorizacion3 n =

sort (nub (concat [digitos x | x <- aux (group (primeFactors n))]))

where aux [] = []

aux (ys@(y:_):xss) = y : genericLength ys : aux xss

-- Definición

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

digitosDeFactorizacion :: Integer -> [Integer]

digitosDeFactorizacion = digitosDeFactorizacion3

-- Solución

-- ========

-- Para calcular la solución, se define la constante

solucion :: Integer

solucion =

head [n | n <- [1..], digitosDeFactorizacion (factorial n) == [0..9]]

-- El cálculo de la solución es

-- ghci> solucion2

-- 49

-- Propiedad

-- =========

-- La propiedad es

prop_completa :: Integer -> Bool

prop_completa n =

digitosDeFactorizacion (factorial n1) == [0..9]

where n1 = 101 + abs n

-- La comprobación es

-- λ> quickCheck prop_completa

-- +++ OK, passed 100 tests.

La solución en Maxima

/* digitos(n) es la lista de los digitos del número n. Por ejemplo, 
      digitos (320274) == [3,2,0,2,7,4]
*/      
digitos (n) := charlist (string (n))$

digitosDeFactorizacion (n) :=
   unique (apply (append, map (digitos, apply (append, ifactors (n))))) $

solucion () := block ([n:1],
  while length (digitosDeFactorizacion (n!)) < 10 do
     n : n+1,
  n)$   

/*
   (%i5) digitosDeFactorizacion (6!);
   (%o5) [1, 2, 3, 4, 5]

   (%i6) solucion ();
   (%o6) 49
*/

/* digitos(n) es la lista de los digitos del número n. Por ejemplo,

digitos (320274) == [3,2,0,2,7,4]

digitos (n) := charlist (string (n))$

digitosDeFactorizacion (n) :=

unique (apply (append, map (digitos, apply (append, ifactors (n))))) $

solucion () := block ([n:1],

while length (digitosDeFactorizacion (n!)) < 10 do

n : n+1,

n)$

(%i5) digitosDeFactorizacion (6!);

(%o5) [1, 2, 3, 4, 5]

(%i6) solucion ();

(%o6) 49

Cantidad de números Pentanacci impares

PorJosé A. Alonso 18-febrero-20162-mayo-2016

Los números de Pentanacci se definen mediante las ecuaciones

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

P(0) = 0

P(1) = 1

P(2) = 1

P(3) = 2

P(4) = 4

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

Los primeros números de Pentanacci son

  0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

1	0, 1, 1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, ...

Se obseeva que

hasta P(5) hay 1 impar: el 1 (aunque aparece dos veces);
hasta P(7) hay 2 impares distintos: 1 y 31;
hasta P(10) hay 3 impares distintos: 1, 31 y 61;
hasta P(15) hay 5 impares distintos: 1, 31 y 61, 1793 y 3525.

Definir la función

   nPentanacciImpares :: Integer -> Integer

1	nPentanacciImpares :: Integer -> Integer

tal que (nPentanacciImpares n) es la cantidad de números impares distintos desde P(0) hasta P(n). Por ejemplo,

   nPentanacciImpares 5                             ==  1
   nPentanacciImpares 7                             ==  2
   nPentanacciImpares 10                            ==  3
   nPentanacciImpares 15                            ==  5
   nPentanacciImpares 100                           ==  33
   nPentanacciImpares 1000                          ==  333
   nPentanacciImpares 10000                         ==  3333
   nPentanacciImpares (10^(10^6)) `mod` (10^9)      ==  333333333
   length (show (nPentanacciImpares2 (10^(10^6))))  ==  1000000

nPentanacciImpares 5 == 1

nPentanacciImpares 7 == 2

nPentanacciImpares 10 == 3

nPentanacciImpares 15 == 5

nPentanacciImpares 100 == 33

nPentanacciImpares 1000 == 333

nPentanacciImpares 10000 == 3333

nPentanacciImpares (10^(10^6)) `mod` (10^9) == 333333333

length (show (nPentanacciImpares2 (10^(10^6)))) == 1000000

Soluciones

import Data.List (genericLength, genericTake)

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

nPentanacciImpares1 :: Integer -> Integer
nPentanacciImpares1 0 = 0
nPentanacciImpares1 1 = 1
nPentanacciImpares1 n = 
    genericLength (filter odd (genericTake (n+1) pentanacci)) - 1

pentanacci :: [Integer]
pentanacci = p (0, 1, 1, 2, 4)
    where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)

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

-- λ> map nPentanacciImpares1 [1..31]
-- [1,1,1,1,1,1,2,3,3,3,3,3,4,5,5,5,5,5,6,7,7,7,7,7,8,9,9,9,9,9,10]
-- λ> [(head xs, length xs) | xs <- group (map nPentanacciImpares1 [1..37])]
-- [(1,6),(2,1),(3,5),(4,1),(5,5),(6,1),(7,5),(8,1),(9,5),(10,1),(11,5),(12,1)]

nPentanacciImpares2 :: Integer -> Integer
nPentanacciImpares2 0 = 0
nPentanacciImpares2 1 = 1
nPentanacciImpares2 n = 2 * q + min r 2 - 1
    where (q,r) = n `quotRem` 6

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

nPentanacciImpares3 :: Integer -> Integer
nPentanacciImpares3 0 = 0
nPentanacciImpares3 1 = 1
nPentanacciImpares3 n | r == 5    = 2*q + 2 
                      | otherwise = 2*q + 1 
    where (q,r) = divMod (n-2) 6

import Data.List (genericLength, genericTake)

-- 1ª definición

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

nPentanacciImpares1 :: Integer -> Integer

nPentanacciImpares1 0 = 0

nPentanacciImpares1 1 = 1

nPentanacciImpares1 n =

genericLength (filter odd (genericTake (n+1) pentanacci)) - 1

pentanacci :: [Integer]

pentanacci = p (0, 1, 1, 2, 4)

where p (a, b, c, d, e) = a : p (b, c, d, e, a + b + c + d + e)

-- 2ª definición

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

-- λ> map nPentanacciImpares1 [1..31]

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

-- λ> [(head xs, length xs) | xs <- group (map nPentanacciImpares1 [1..37])]

-- [(1,6),(2,1),(3,5),(4,1),(5,5),(6,1),(7,5),(8,1),(9,5),(10,1),(11,5),(12,1)]

nPentanacciImpares2 :: Integer -> Integer

nPentanacciImpares2 0 = 0

nPentanacciImpares2 1 = 1

nPentanacciImpares2 n = 2 * q + min r 2 - 1

where (q,r) = n `quotRem` 6

-- 3ª definición

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

nPentanacciImpares3 :: Integer -> Integer

nPentanacciImpares3 0 = 0

nPentanacciImpares3 1 = 1

nPentanacciImpares3 n | r == 5 = 2*q + 2

| otherwise = 2*q + 1

where (q,r) = divMod (n-2) 6

Diagonales de matrices como listas

PorJosé A. Alonso 16-febrero-201623-febrero-2016

Las matrices se pueden representar como listas de listas de la misma longitud, donde cada uno de sus elementos representa una fila de la matriz.

Definir la función

   diagonal :: [[a]] -> [a]

1	diagonal :: [[a]] -> [a]

tal que (diagonal xss) es la diagonal de la matriz xss. Por ejemplo,

   diagonal [[3,5,2],[4,7,1],[6,9,0]]           ==  [3,7,0]
   diagonal [[3,5],[4,7],[6,9]]                 ==  [3,7]
   diagonal [[3,5,2],[4,7,1]]                   ==  [3,7]
   sum (diagonal (replicate 20000 [1..20000]))  ==  200010000

diagonal [[3,5,2],[4,7,1],[6,9,0]] == [3,7,0]

diagonal [[3,5],[4,7],[6,9]] == [3,7]

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

sum (diagonal (replicate 20000 [1..20000])) == 200010000

Soluciones

import Data.Array  ((!), listArray)
import Data.Matrix (fromLists, getDiag)
import Data.Vector (toList)

-- 1ª definición (por recursión):
diagonal1 :: [[a]] -> [a]
diagonal1 ((x:_):xss) = x : diagonal1 [tail xs | xs <- xss]
diagonal1 _           = []

-- 2ª definición (por comprensión):
diagonal2 :: [[a]] -> [a]
diagonal2 xss = [xs!!k | (xs,k) <- zip xss [0..n]]
    where n = length (head xss) - 1

-- 3ª definición (con Data.Matrix)
diagonal3 :: [[a]] -> [a]
diagonal3 = toList . getDiag . fromLists

-- 4ª definición (con Data.Array)
diagonal4 :: [[a]] -> [a]
diagonal4 xss = [p!(i,i) | i <- [1..k]] 
    where m = length xss
          n = length (head xss)
          k = min m n
          p = listArray ((1,1),(m,n)) (concat xss)

-- Comparación de eficiencia
--    λ> let n = 3000 in sum (diagonal1 (replicate n [1..n]))
--    4501500
--    (2.08 secs, 754,089,992 bytes)
--    λ> let n = 3000 in sum (diagonal2 (replicate n [1..n]))
--    4501500
--    (0.06 secs, 0 bytes)
--    λ> let n = 3000 in sum (diagonal3 (replicate n [1..n]))
--    4501500
--    (1.22 secs, 1,040,787,360 bytes)
--    λ> let n = 3000 in sum (diagonal4 (replicate n [1..n]))
--    4501500
--    (0.96 secs, 624,463,632 bytes)

import Data.Array ((!), listArray)

import Data.Matrix (fromLists, getDiag)

import Data.Vector (toList)

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

diagonal1 :: [[a]] -> [a]

diagonal1 ((x:_):xss) = x : diagonal1 [tail xs | xs <- xss]

diagonal1 _ = []

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

diagonal2 :: [[a]] -> [a]

diagonal2 xss = [xs!!k | (xs,k) <- zip xss [0..n]]

where n = length (head xss) - 1

-- 3ª definición (con Data.Matrix)

diagonal3 :: [[a]] -> [a]

diagonal3 = toList . getDiag . fromLists

-- 4ª definición (con Data.Array)

diagonal4 :: [[a]] -> [a]

diagonal4 xss = [p!(i,i) | i <- [1..k]]

where m = length xss

n = length (head xss)

k = min m n

p = listArray ((1,1),(m,n)) (concat xss)

-- Comparación de eficiencia

-- λ> let n = 3000 in sum (diagonal1 (replicate n [1..n]))

-- 4501500

-- (2.08 secs, 754,089,992 bytes)

-- λ> let n = 3000 in sum (diagonal2 (replicate n [1..n]))

-- 4501500

-- (0.06 secs, 0 bytes)

-- λ> let n = 3000 in sum (diagonal3 (replicate n [1..n]))

-- 4501500

-- (1.22 secs, 1,040,787,360 bytes)

-- λ> let n = 3000 in sum (diagonal4 (replicate n [1..n]))

-- 4501500

-- (0.96 secs, 624,463,632 bytes)

Solución con Maxima

diagonal (xss) := block ([A],
  A : apply (matrix, xss),
  [m,n] : matrix_size (A),
  k : min (m,n),
  makelist (A[i,i],i,k))$

diagonal (xss) := block ([A],

A : apply (matrix, xss),

[m,n] : matrix_size (A),

k : min (m,n),

makelist (A[i,i],i,k))$

Números como suma de N sumandos

PorJosé A. Alonso 15-febrero-201622-febrero-2016

Definir la función

   sumas :: Int -> [Int] -> [Int]

1	sumas :: Int -> [Int] -> [Int]

tal que (sumas n xs) es la lista de los números que se pueden obtener como suma de n, o menos, elementos de xs. Por ejemplo,

   sumas 0 [2,5]              ==  [0]
   sumas 1 [2,5]              ==  [0,2,5]
   sumas 2 [2,5]              ==  [0,2,4,5,7,10]
   sumas 3 [2,5]              ==  [0,2,4,5,6,7,9,10,12,15]
   sumas 2 [2,3,5]            ==  [0,2,3,4,5,6,7,8,10]
   sumas 3 [2,3,5]            ==  [0,2,3,4,5,6,7,8,9,10,11,12,13,15]
   length (sumas 8 [1..200])  ==  1601

sumas 0 [2,5] == [0]

sumas 1 [2,5] == [0,2,5]

sumas 2 [2,5] == [0,2,4,5,7,10]

sumas 3 [2,5] == [0,2,4,5,6,7,9,10,12,15]

sumas 2 [2,3,5] == [0,2,3,4,5,6,7,8,10]

sumas 3 [2,3,5] == [0,2,3,4,5,6,7,8,9,10,11,12,13,15]

length (sumas 8 [1..200]) == 1601

Soluciones

import Data.List (nub, sort)

sumas :: Int -> [Int] -> [Int]
sumas 0 _  = [0]
sumas n xs = nub (sort (ys ++ [x+y | x <- xs, y <- ys]))
    where ys = sumas (n-1) xs

import Data.List (nub, sort)

sumas :: Int -> [Int] -> [Int]

sumas 0 _ = [0]

sumas n xs = nub (sort (ys ++ [x+y | x <- xs, y <- ys]))

where ys = sumas (n-1) xs

Solución con Maxima

sumas (n,xs) := block ([ys],
  if n > 0
  then ( ys : sumas (n-1, xs),
         unique (append (ys, create_list (x+y,x,xs,y,ys))) )
  else [0])$

sumas (n,xs) := block ([ys],

if n > 0

then ( ys : sumas (n-1, xs),

unique (append (ys, create_list (x+y,x,xs,y,ys))) )

else [0])$

Anotación de la profundidad de los nodos

PorJosé A. Alonso 12-febrero-201619-febrero-2016

Los árboles binarios con datos en los nodos y hojas se definen por

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

data Arbol a = H

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

Por ejemplo, el árbol

          3
         / \
        /   \
       4     7
      / \   / \
     5   0 0   3
    / \
   2   0

/ \

4 7

/ \ / \

5 0 0 3

/ \

2 0

se representa por

   ejArbol :: Arbol Integer
   ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

1 2	ejArbol :: Arbol Integer ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

Anotando cada elemento del árbol anterior con su profundidad, se obtiene el árbol siguiente

          3-0
          / \
         /   \
        /     \
      4-1     7-1
      / \     / \
    5-2 0-2 0-2 3-0
    / \
  2-3 0-3

3-0

/ \

4-1 7-1

/ \ / \

5-2 0-2 0-2 3-0

/ \

2-3 0-3

Definir la función

   anotado :: Arbol a -> Arbol (a,Int)

1	anotado :: Arbol a -> Arbol (a,Int)

tal que (anotado x) es el árbol obtenido anotando los elementos de x con su profundidad. Por ejemplo,

   λ> anotado ejArbol
   N (3,0) 
     (N (4,1) 
        (N (5,2) (H (2,3)) (H (0,3))) 
        (H (0,2))) 
     (N (7,1) (H (0,2)) (H (3,2)))

λ> anotado ejArbol

N (3,0)

(N (4,1)

(N (5,2) (H (2,3)) (H (0,3)))

(H (0,2)))

(N (7,1) (H (0,2)) (H (3,2)))

Soluciones

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

ejArbol :: Arbol Integer
ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

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

anotado1 :: Arbol a -> Arbol (a,Int)
anotado1 (H x)     = H (x,0)
anotado1 (N x i d) = aux (N x i d) 0
    where aux (H x)     n = H (x,n)
          aux (N x i d) n = N (x,n) (aux i (n+1)) (aux d (n+1))  

-- 2ª solución
anotado2 :: Arbol a -> Arbol (a, Int)
anotado2 a = aux a [0..]
    where aux (H a)     (n:_ ) = H (a,n)
          aux (N a i d) (n:ns) = N (a,n) (aux i ns) (aux d ns)

data Arbol a = H a

| N a (Arbol a) (Arbol a)

deriving (Eq, Show)

ejArbol :: Arbol Integer

ejArbol = N 3 (N 4 (N 5 (H 2)(H 0)) (H 0)) (N 7 (H 0) (H 3))

-- 1ª solución

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

anotado1 :: Arbol a -> Arbol (a,Int)

anotado1 (H x) = H (x,0)

anotado1 (N x i d) = aux (N x i d) 0

where aux (H x) n = H (x,n)

aux (N x i d) n = N (x,n) (aux i (n+1)) (aux d (n+1))

-- 2ª solución

anotado2 :: Arbol a -> Arbol (a, Int)

anotado2 a = aux a [0..]

where aux (H a) (n:_ ) = H (a,n)

aux (N a i d) (n:ns) = N (a,n) (aux i ns) (aux d ns)

Compactación de listas

PorJosé A. Alonso 11-febrero-201626-marzo-2022

Definir la función

   compactada :: [Maybe Int] -> [Int]

1	compactada :: [Maybe Int] -> [Int]

tal que (compacta xs) es la lista obtenida al compactar xs con las siguientes reglas:

se eliminan los elementos Nothing;
si dos elementos consecutivos tienen el mismo valor, se sustituyen por el sucesor de su valor y
los restantes elementos no se cambian.

Por ejemplo,

    λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6]
    [2,5,3,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6]
    [2,1,4,3,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6]
    [2,1,5,6]
    λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4]
    [2,1,4,3,4]
    λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]
    [2,2,4,3,4]

λ> compactada [Just 1,Nothing,Just 1,Just 4,Just 4,Just 3,Just 6]

[2,5,3,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 6]

[2,1,4,3,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 4,Just 6]

[2,1,5,6]

λ> compactada [Just 1,Nothing,Just 1,Just 1,Just 4,Just 3,Just 4]

[2,1,4,3,4]

λ> compactada [Just 1,Nothing,Just 1,Just 2,Just 4,Just 3,Just 4]

[2,2,4,3,4]

Soluciones

-- 1ª definición
compactada1 :: [Maybe Int] -> [Int]
compactada1 xs = aux (valores xs)
    where aux (x:y:xs) | x == y    = x+1 : aux xs
                       | otherwise = x : aux (y:xs)
          aux xs                   = xs

-- (valores vs) es la lista de los valores de vs. Por ejemplo,
--    ghci> valores [Just 1,Nothing,Just 1,Nothing,Just 3,Just 6]
--    [1,1,3,6]
valores :: [Maybe Int] -> [Int]
valores xs = [x | Just x <- xs]

-- 2ª definición de valores (por recursión):
valores2 :: [Maybe Int] -> [Int]
valores2 []            = []
valores2 ((Just v):vs) = v: valores2 vs
valores2 (Nothing:vs)  = valores2 vs

-- 1ª definición

compactada1 :: [Maybe Int] -> [Int]

compactada1 xs = aux (valores xs)

where aux (x:y:xs) | x == y = x+1 : aux xs

| otherwise = x : aux (y:xs)

aux xs = xs

-- (valores vs) es la lista de los valores de vs. Por ejemplo,

-- ghci> valores [Just 1,Nothing,Just 1,Nothing,Just 3,Just 6]

-- [1,1,3,6]

valores :: [Maybe Int] -> [Int]

valores xs = [x | Just x <- xs]

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

valores2 :: [Maybe Int] -> [Int]

valores2 [] = []

valores2 ((Just v):vs) = v: valores2 vs

valores2 (Nothing:vs) = valores2 vs

Eliminación de espacios extremos

PorJosé A. Alonso 10-febrero-201617-febrero-2016

Definir la función

   sinEspaciosExtremos :: String -> String

1	sinEspaciosExtremos :: String -> String

tal que (sinEspaciosExtremos cs) es la cadena obtenida eliminando los espacios blancos de los extremos de la cadena cs. Por ejemplo,

   λ> sinEspaciosExtremos "   El lunes a las 12:30.     "
   "El lunes a las 12:30."

1 2	λ> sinEspaciosExtremos " El lunes a las 12:30. " "El lunes a las 12:30."

Soluciones

import Data.Char (isSpace)

sinEspaciosExtremos :: String -> String
sinEspaciosExtremos = f . f
    where f = reverse . dropWhile isSpace

import Data.Char (isSpace)

sinEspaciosExtremos :: String -> String

sinEspaciosExtremos = f . f

where f = reverse . dropWhile isSpace

Números primos de Hilbert

PorJosé A. Alonso 4-febrero-20161-mayo-2016

Un número de Hilbert es un entero positivo de la forma 4n+1. Los primeros números de Hilbert son 1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, …

Un primo de Hilbert es un número de Hilbert n que no es divisible por ningún número de Hilbert menor que n (salvo el 1). Los primeros primos de Hilbert son 5, 9, 13, 17, 21, 29, 33, 37, 41, 49, 53, 57, 61, 69, 73, 77, 89, 93, 97, 101, 109, 113, 121, 129, 133, 137, …

Definir la sucesión

   primosH :: [Integer]

1	primosH :: [Integer]

tal que sus elementos son los primos de Hilbert. Por ejemplo,

   take 15 primosH  == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73]
   primosH !! 20000 == 203221

1 2	take 15 primosH == [5,9,13,17,21,29,33,37,41,49,53,57,61,69,73] primosH !! 20000 == 203221

Soluciones

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

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,
--    take 15 numerosH  ==  [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]
numerosH :: [Integer]
numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a
-- n. Por ejemplo,
--   divisoresH 117  ==  [1,9,13,117]
--   divisoresH  21  ==  [1,21]
divisoresH :: Integer -> [Integer]
divisoresH n = [x | x <- takeWhile (<=n) numerosH,
                    n `mod` x == 0]

primosH1 :: [Integer]
primosH1 = [n | n <- tail numerosH,
                divisoresH n == [1,n]]

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

primosH2 :: [Integer]
primosH2 = filter esPrimoH (tail numerosH) 
    where esPrimoH n = all noDivideAn [5,9..m]
              where noDivideAn x = n `mod` x /= 0
                    m            = ceiling (sqrt (fromIntegral n))

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

--    λ> primosH1 !! 2000
--    16957
--    (6.93 secs, 750,291,352 bytes)
--    λ> primosH2 !! 2000
--    16957
--    (0.13 secs, 18,066,288 bytes)

-- 1ª definición

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

-- numerosH es la sucesión de los números de Hilbert. Por ejemplo,

-- take 15 numerosH == [1,5,9,13,17,21,25,29,33,37,41,45,49,53,57]

numerosH :: [Integer]

numerosH = [1,5..]

-- (divisoresH n) es la lista de los números de Hilbert que dividen a

-- n. Por ejemplo,

-- divisoresH 117 == [1,9,13,117]

-- divisoresH 21 == [1,21]

divisoresH :: Integer -> [Integer]

divisoresH n = [x | x <- takeWhile (<=n) numerosH,

n `mod` x == 0]

primosH1 :: [Integer]

primosH1 = [n | n <- tail numerosH,

divisoresH n == [1,n]]

-- 2ª definición

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

primosH2 :: [Integer]

primosH2 = filter esPrimoH (tail numerosH)

where esPrimoH n = all noDivideAn [5,9..m]

where noDivideAn x = n `mod` x /= 0

m = ceiling (sqrt (fromIntegral n))

-- Comparación de eficiencia

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

-- λ> primosH1 !! 2000

-- 16957

-- (6.93 secs, 750,291,352 bytes)

-- λ> primosH2 !! 2000

-- 16957

-- (0.13 secs, 18,066,288 bytes)

Ordenación por frecuencia

PorJosé A. Alonso 2-febrero-201625-abril-2021

Definir la función

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

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

tal que (ordPorFrecuencia xs) es la lista obtenidas ordenando los elementos de xs por su frecuencia, de los que aparecen menos a los que aparecen más. Por ejemplo,

   ordPorFrecuencia "canalDePanama"  ==  "DPcelmnnaaaaa"
   ordPorFrecuencia "20012016"       ==  "61122000"

1 2	ordPorFrecuencia "canalDePanama" == "DPcelmnnaaaaa" ordPorFrecuencia "20012016" == "61122000"

Soluciones

import Data.List (group, sort)

ordPorFrecuencia :: Ord a => [a] -> [a]
ordPorFrecuencia xs =
    concatMap snd (sort [(length xs,xs) | xs <- group (sort xs)])

import Data.List (group, sort)

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

ordPorFrecuencia xs =

concatMap snd (sort [(length xs,xs) | xs <- group (sort xs)])

El algoritmo binario del mcd

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

El máximo común divisor (mcd) de dos números enteros no negativos se puede calcular mediante un algoritmo binario basado en las siguientes propiedades:

Si a,b son pares, entonces mcd(a,b) = 2*mcd(a/2,b/2)
Si a es par y b impar, entonces mcd(a,b) = mcd(a/2,b)
Si a es impar y b par, entonces mcd(a,b) = mcd(a,b/2)
Si a y b son impares y a > b, entonces mcd(a,b) = mcd((a-b)/2,b)
Si a y b son impares y a < b, entonces mcd(a,b) = mcd(a,(b-a)/2)
mcd(a,0) = a
mcd(0,b) = b
mcd(a,a) = a

Por ejemplo, el cálculo del mcd(660,420) es

   mcd(660,420)
   = 2*mcd(330,210)    [por 1]
   = 2*2*mcd(165,105)  [por 1]
   = 2*2*mcd(30,105)   [por 4]
   = 2*2*mcd(15,105)   [por 2]
   = 2*2*mcd(15,45)    [por 4]
   = 2*2*mcd(15,15)    [por 4]
   = 2*2*15            [por 8]
   = 60

mcd(660,420)

= 2*mcd(330,210) [por 1]

= 2*2*mcd(165,105) [por 1]

= 2*2*mcd(30,105) [por 4]

= 2*2*mcd(15,105) [por 2]

= 2*2*mcd(15,45) [por 4]

= 2*2*mcd(15,15) [por 4]

= 2*2*15 [por 8]

= 60

Definir la función

   mcd :: Integer -> Integer -> Integer

1	mcd :: Integer -> Integer -> Integer

Definir la función

tal que (mcd a b) es el máximo común divisor de a y b calculado mediante el algoritmo binario del mcd. Por ejemplo,

   mcd 660 420  ==  60
   mcd 3 0      ==  3
   mcd 0 3      ==  3

mcd 660 420 == 60

mcd 3 0 == 3

mcd 0 3 == 3

Comprobar con QuickCheck que, para los enteros no negativos, las funciones mcd y gcd son equivalentes.

Soluciones

import Test.QuickCheck

mcd :: Integer -> Integer -> Integer
mcd a 0 = a
mcd 0 b = b
mcd a b | a == b           = a
        | even a && even b = 2 * mcd (a `div` 2) (b `div` 2)
        | even a           = mcd (a `div` 2)     b
        | even b           = mcd a               (b `div` 2)
        | a > b            = mcd ((a-b) `div` 2) b
        | otherwise        = mcd a               ((b-a) `div` 2)

-- Propiedad de equivalencia 
prop_mcd :: Integer -> Integer -> Bool
prop_mcd a b = mcd a1 b1 == gcd a1 b1
    where a1 = abs a
          b1 = abs b

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

import Test.QuickCheck

mcd :: Integer -> Integer -> Integer

mcd a 0 = a

mcd 0 b = b

mcd a b | a == b = a

| even a && even b = 2 * mcd (a `div` 2) (b `div` 2)

| even a = mcd (a `div` 2) b

| even b = mcd a (b `div` 2)

| a > b = mcd ((a-b) `div` 2) b

| otherwise = mcd a ((b-a) `div` 2)

-- Propiedad de equivalencia

prop_mcd :: Integer -> Integer -> Bool

prop_mcd a b = mcd a1 b1 == gcd a1 b1

where a1 = abs a

b1 = abs b

-- La comprobación es

-- λ> quickCheck prop_mcd

-- +++ OK, passed 100 tests.

Meses: febrero 2016

Particiones en sumas de cuadrados

Soluciones

Referencias

Números automórficos

Soluciones

Referencias

Sumas de potencias de 3 primos

Soluciones

Múltiplos con ceros y unos

Soluciones

Regresión lineal

Soluciones

Cantidad de números Pentanacci impares

Soluciones

Diagonales de matrices como listas

Soluciones

Solución con Maxima

Números como suma de N sumandos

Soluciones

Solución con Maxima

Anotación de la profundidad de los nodos

Soluciones

Compactación de listas

Soluciones

Eliminación de espacios extremos

Soluciones

Números primos de Hilbert

Soluciones

El algoritmo binario del mcd

Soluciones

Entradas recientes

Buscar

Correo electrónico