Recursión – Página 4

Las conjeturas de Catalan y de Pillai

PorJosé A. Alonso 15-enero-202022-enero-2020

La conjetura de Catalan, enunciada en 1844 por Eugène Charles Catalan y demostrada 2002 por Preda Mihăilescu1, afirma que

Las únicas dos potencias de números enteros consecutivos son 8 y 9 (que son respectivamente 2³ y 3²).

En otras palabras, la única solución entera de la ecuación

   x^a - y^b = 1

1	x^a - y^b = 1

para x, a, y, b > 1 es x = 3, a = 2, y = 2, b = 3.

La conjetura de Pillai, propuesta por S.S. Pillai en 1942, generaliza este resultado y es un problema abierto. Afirma que cada entero se puede escribir sólo un número finito de veces como una diferencia de dos potencias perfectas. En otras palabras, para todo entero positivo n, el conjunto de soluciones de

   x^a - y^b = n

1	x^a - y^b = n

para x, a, y, b > 1 es finito.

Por ejemplo, para n = 4, hay 3 soluciones

   (2,3, 2,2) ya que 2³ -  2² =   8 -   4 = 4
   (6,2, 2,5) ya que 6² -  2⁵ =  36 -  32 = 4
   (5,3,11,2) ya que 5³ - 11² = 125 - 121 = 4

(2,3, 2,2) ya que 2³ - 2² = 8 - 4 = 4

(6,2, 2,5) ya que 6² - 2⁵ = 36 - 32 = 4

(5,3,11,2) ya que 5³ - 11² = 125 - 121 = 4

Las soluciones se pueden representar por la menor potencia (en el caso anterior, por 4, 32 y 121) ya que dado n (en el caso anterior es 4), la potencia mayor es la menor más n.

Definir las funciones

   potenciasPerfectas :: [Integer]
   solucionesPillati :: Integer -> [Integer]
   solucionesPillatiAcotadas :: Integer -> Integer -> [Integer]

potenciasPerfectas :: [Integer]

solucionesPillati :: Integer -> [Integer]

solucionesPillatiAcotadas :: Integer -> Integer -> [Integer]

tales que

potenciasPerfectas es la lista de las potencias perfectas (es decir, de los números de la forma x^a con x y a mayores que 1). Por ejemplo,

     take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]
     potenciasPerfectas !! 200   ==  28224

1 2	take 10 potenciasPerfectas == [4,8,9,16,25,27,32,36,49,64] potenciasPerfectas !! 200 == 28224

(solucionesPillati n) es la lista de las menores potencias de las soluciones de la ecuación de Pillati x^a – y^b = n; es decir, es la lista de los u tales que u y u+n son potencias perfectas. Por ejemplo,

     take 3 (solucionesPillati 4)  ==  [4,32,121]
     take 2 (solucionesPillati 5)  ==  [4,27]
     take 4 (solucionesPillati 7)  ==  [9,25,121,32761]

take 3 (solucionesPillati 4) == [4,32,121]

take 2 (solucionesPillati 5) == [4,27]

take 4 (solucionesPillati 7) == [9,25,121,32761]

(solucionesPillatiAcotadas c n) es la lista de elementos de (solucionesPillati n) menores que n. Por ejemplo,

     solucionesPillatiAcotadas (10^3) 1  ==  [8]
     solucionesPillatiAcotadas (10^3) 2  ==  [25]
     solucionesPillatiAcotadas (10^3) 3  ==  [125]
     solucionesPillatiAcotadas (10^3) 4  ==  [4,32,121]
     solucionesPillatiAcotadas (10^3) 5  ==  [4,27]
     solucionesPillatiAcotadas (10^3) 6  ==  []
     solucionesPillatiAcotadas (10^3) 7  ==  [9,25,121]
     solucionesPillatiAcotadas (10^5) 7  ==  [9,25,121,32761]

solucionesPillatiAcotadas (10^3) 1 == [8]

solucionesPillatiAcotadas (10^3) 2 == [25]

solucionesPillatiAcotadas (10^3) 3 == [125]

solucionesPillatiAcotadas (10^3) 4 == [4,32,121]

solucionesPillatiAcotadas (10^3) 5 == [4,27]

solucionesPillatiAcotadas (10^3) 6 == []

solucionesPillatiAcotadas (10^3) 7 == [9,25,121]

solucionesPillatiAcotadas (10^5) 7 == [9,25,121,32761]

Soluciones

import Data.List (group)
import Data.Numbers.Primes (primeFactors)

-- Definiciones de potenciasPerfectas
-- ==================================

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

potenciasPerfectas1 :: [Integer]
potenciasPerfectas1 = filter esPotenciaPerfecta [4..]

-- (esPotenciaPerfecta x) se verifica si x es una potencia perfecta. Por
-- ejemplo, 
--    esPotenciaPerfecta 36  ==  True
--    esPotenciaPerfecta 72  ==  False
esPotenciaPerfecta :: Integer -> Bool
esPotenciaPerfecta = not . null. potenciasPerfectasDe 

-- (potenciasPerfectasDe x) es la lista de pares (a,b) tales que 
-- x = a^b. Por ejemplo,
--    potenciasPerfectasDe 64  ==  [(2,6),(4,3),(8,2)]
--    potenciasPerfectasDe 72  ==  []
potenciasPerfectasDe :: Integer -> [(Integer,Integer)]
potenciasPerfectasDe n = 
    [(m,k) | m <- takeWhile (\x -> x*x <= n) [2..]
           , k <- takeWhile (\x -> m^x <= n) [2..]
           , m^k == n]

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

potenciasPerfectas2 :: [Integer]
potenciasPerfectas2 = [x | x <- [4..], esPotenciaPerfecta2 x]

-- (esPotenciaPerfecta2 x) se verifica si x es una potencia perfecta. Por
-- ejemplo, 
--    esPotenciaPerfecta2 36  ==  True
--    esPotenciaPerfecta2 72  ==  False
esPotenciaPerfecta2 :: Integer -> Bool
esPotenciaPerfecta2 x = mcd (exponentes x) > 1

-- (exponentes x) es la lista de los exponentes de l factorización prima
-- de x. Por ejemplos,
--    exponentes 36  ==  [2,2]
--    exponentes 72  ==  [3,2]
exponentes :: Integer -> [Int]
exponentes x = [length ys | ys <- group (primeFactors x)] 

-- (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 :: [Int] -> Int
mcd = foldl1 gcd

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

potenciasPerfectas3 :: [Integer]
potenciasPerfectas3 = mezclaTodas potencias

-- potencias es la lista las listas de potencias de todos los números
-- mayores que 1 con exponentes mayores que 1. Por ejemplo,
--    λ> map (take 3) (take 4 potencias)
--    [[4,8,16],[9,27,81],[16,64,256],[25,125,625]]
potencias :: [[Integer]]
potencias = [[n^k | k <- [2..]] | n <- [2..]]

-- (mezclaTodas xss) es la mezcla ordenada sin repeticiones de las
-- listas ordenadas xss. Por ejemplo,
--    take 7 (mezclaTodas potencias)  ==  [4,8,9,16,25,27,32]
mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys

-- (mezcla xs ys) es la mezcla ordenada sin repeticiones de las
-- listas ordenadas xs e ys. Por ejemplo,
--    take 7 (mezcla [2,5..] [4,6..])  ==  [2,4,5,6,8,10,11]
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

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

--    λ> potenciasPerfectas1 !! 200
--    28224
--    (7.24 secs, 9,245,991,160 bytes)
--    λ> potenciasPerfectas2 !! 200
--    28224
--    (0.30 secs, 814,597,152 bytes)
--    λ> potenciasPerfectas3 !! 200
--    28224
--    (0.01 secs, 7,061,120 bytes)

-- En lo que sigue se usa la 3ª definición
potenciasPerfectas :: [Integer]
potenciasPerfectas = potenciasPerfectas3

-- Definición de solucionesPillati
-- ===============================

solucionesPillati :: Integer -> [Integer]
solucionesPillati n =
  [x | x <- potenciasPerfectas
     , esPotenciaPerfecta2 (x+n)]

-- Definición de solucionesPillatiAcotadas
-- =======================================

solucionesPillatiAcotadas :: Integer -> Integer -> [Integer]
solucionesPillatiAcotadas c n =
  [x | x <- takeWhile (< (c-n)) potenciasPerfectas
     , esPotenciaPerfecta2 (x+n)]

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

import Data.List (group)

import Data.Numbers.Primes (primeFactors)

-- Definiciones de potenciasPerfectas

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

-- 1ª definición

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

potenciasPerfectas1 :: [Integer]

potenciasPerfectas1 = filter esPotenciaPerfecta [4..]

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

-- ejemplo,

-- esPotenciaPerfecta 36 == True

-- esPotenciaPerfecta 72 == False

esPotenciaPerfecta :: Integer -> Bool

esPotenciaPerfecta = not . null. potenciasPerfectasDe

-- (potenciasPerfectasDe x) es la lista de pares (a,b) tales que

-- x = a^b. Por ejemplo,

-- potenciasPerfectasDe 64 == [(2,6),(4,3),(8,2)]

-- potenciasPerfectasDe 72 == []

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

potenciasPerfectasDe n =

[(m,k) | m <- takeWhile (\x -> x*x <= n) [2..]

, k <- takeWhile (\x -> m^x <= n) [2..]

, m^k == n]

-- 2ª definición

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

potenciasPerfectas2 :: [Integer]

potenciasPerfectas2 = [x | x <- [4..], esPotenciaPerfecta2 x]

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

-- ejemplo,

-- esPotenciaPerfecta2 36 == True

-- esPotenciaPerfecta2 72 == False

esPotenciaPerfecta2 :: Integer -> Bool

esPotenciaPerfecta2 x = mcd (exponentes x) > 1

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

-- de x. Por ejemplos,

-- exponentes 36 == [2,2]

-- exponentes 72 == [3,2]

exponentes :: Integer -> [Int]

exponentes x = [length ys | ys <- group (primeFactors x)]

-- (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 :: [Int] -> Int

mcd = foldl1 gcd

-- 3ª definición

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

potenciasPerfectas3 :: [Integer]

potenciasPerfectas3 = mezclaTodas potencias

-- potencias es la lista las listas de potencias de todos los números

-- mayores que 1 con exponentes mayores que 1. Por ejemplo,

-- λ> map (take 3) (take 4 potencias)

-- [[4,8,16],[9,27,81],[16,64,256],[25,125,625]]

potencias :: [[Integer]]

potencias = [[n^k | k <- [2..]] | n <- [2..]]

-- (mezclaTodas xss) es la mezcla ordenada sin repeticiones de las

-- listas ordenadas xss. Por ejemplo,

-- take 7 (mezclaTodas potencias) == [4,8,9,16,25,27,32]

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

mezclaTodas = foldr1 xmezcla

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

-- (mezcla xs ys) es la mezcla ordenada sin repeticiones de las

-- listas ordenadas xs e ys. Por ejemplo,

-- take 7 (mezcla [2,5..] [4,6..]) == [2,4,5,6,8,10,11]

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

-- Comparación de eficiencia

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

-- λ> potenciasPerfectas1 !! 200

-- 28224

-- (7.24 secs, 9,245,991,160 bytes)

-- λ> potenciasPerfectas2 !! 200

-- 28224

-- (0.30 secs, 814,597,152 bytes)

-- λ> potenciasPerfectas3 !! 200

-- 28224

-- (0.01 secs, 7,061,120 bytes)

-- En lo que sigue se usa la 3ª definición

potenciasPerfectas :: [Integer]

potenciasPerfectas = potenciasPerfectas3

-- Definición de solucionesPillati

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

solucionesPillati :: Integer -> [Integer]

solucionesPillati n =

[x | x <- potenciasPerfectas

, esPotenciaPerfecta2 (x+n)]

-- Definición de solucionesPillatiAcotadas

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

solucionesPillatiAcotadas :: Integer -> Integer -> [Integer]

solucionesPillatiAcotadas c n =

[x | x <- takeWhile (< (c-n)) potenciasPerfectas

, esPotenciaPerfecta2 (x+n)]

Referencia

Catalan’s conjecture en Wikipedia.

Pensamiento

Y te enviaré mi canción:
«Se canta lo que se pierde»,
con un papagayo verde
que la diga en tu balcón.

Antonio Machado

Teorema de Hilbert-Waring

PorJosé A. Alonso 9-enero-202016-enero-2020

El problema de Waring, propuesto por Edward Waring consiste en déterminar si, para cada número entero k mayor que 1, existe un número n tal que todo entero positivo se puede escribir como una suma de k-potencias de números positivos con n sumandos como máximo.

La respuesta afirmativa al problema, aportada por David Hilbert, se conoce como el teorema de Hilbert-Waring. Su enunciado es

Para cada número entero k, con k ≥ 2, existe un entero positivo g(k) tal que todo entero positivo se puede expresar como una suma de a lo más g(k) k-ésimas potencias.

Definir las funciones

   descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]
   orden :: Integer -> Integer -> Integer

1 2	descomposiciones :: Integer -> Integer -> Integer -> [[Integer]] orden :: Integer -> Integer -> Integer

tales que

(descomposiciones x k n) es la lista de descomposiciones de x como suma de n potencias con exponente k de números enteros positivos.

     descomposiciones 9   2 1  ==  [[9]]
     descomposiciones 9   3 1  ==  []
     descomposiciones 9   3 2  ==  [[1,8]]
     descomposiciones 9   4 9  ==  [[1,1,1,1,1,1,1,1,1]]
     descomposiciones 25  2 2  ==  [[9,16]]
     descomposiciones 133 2 3  ==  [[8,125]]
     descomposiciones 38  3 2  ==  [[1,1,36],[4,9,25]]

descomposiciones 9 2 1 == [[9]]

descomposiciones 9 3 1 == []

descomposiciones 9 3 2 == [[1,8]]

descomposiciones 9 4 9 == [[1,1,1,1,1,1,1,1,1]]

descomposiciones 25 2 2 == [[9,16]]

descomposiciones 133 2 3 == [[8,125]]

descomposiciones 38 3 2 == [[1,1,36],[4,9,25]]

(orden x k) es el menor número de sumandos necesario para expresar x como suma de k-ésimas potencias. Por ejemplo,

     orden 9  2  ==  1
     orden 9  3  ==  2
     orden 9  4  ==  9
     orden 10 2  ==  2
     orden 10 3  ==  3
     orden 10 4  ==  10
     [maximum [orden x k | x <- [1..1000]] | k <- [1..6]] == [1,4,9,19,37,73]

orden 9 2 == 1

orden 9 3 == 2

orden 9 4 == 9

orden 10 2 == 2

orden 10 3 == 3

orden 10 4 == 10

[maximum [orden x k | x <- [1..1000]] | k <- [1..6]] == [1,4,9,19,37,73]

Comprobar el teorema de Hilbert-Waring para k hasta 7; es decir, para todo número x positivo se verifica que

   orden x 2 <= 4   
   orden x 3 <= 9   
   orden x 4 <= 19  
   orden x 5 <= 37  
   orden x 6 <= 73  
   orden x 7 <= 143

orden x 2 <= 4

orden x 3 <= 9

orden x 4 <= 19

orden x 5 <= 37

orden x 6 <= 73

orden x 7 <= 143

y, en general,

   orden x k <= 2^k + floor ((3/2)^k) - 2

1	orden x k <= 2^k + floor ((3/2)^k) - 2

Soluciones

import Test.QuickCheck

descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]
descomposiciones x k n =
  sumas x (takeWhile (<= x) (potencias k)) n

-- (potencias n) es la lista de las potencias de n
--    take 7 (potencias 2)  ==  [1,4,9,16,25,36,49]
--    take 7 (potencias 3)  ==  [1,8,27,64,125,216,343]
potencias :: Integer -> [Integer]
potencias n = map (^n) [1..]

-- (sumas n ys x) es la lista de las descomposiciones de x como
-- sumas de n sumandos de la lista creciente ys. Por ejemplo,
--    sumas 3 [1,2] 2  ==  [[1,2]]
--    sumas 4 [1,2] 2  ==  [[2,2]]
--    sumas 5 [1,2] 2  ==  []
--    sumas 5 [1,2] 3  ==  [[1,2,2]]
--    sumas 6 [1,2] 3  ==  [[2,2,2]]
--    sumas 6 [1,2,5] 2  ==  [[1,5]]
sumas :: Integer -> [Integer] -> Integer -> [[Integer]]
sumas _ [] _                   = []
sumas x ys 1     | x `elem` ys = [[x]]
                 | otherwise   = []
sumas x (y:ys) n | y > x       = []
                 | otherwise   = map (y:) (sumas (x-y) (y:ys) (n-1)) ++
                                 sumas x ys n

orden :: Integer -> Integer -> Integer
orden x k = head [n | n <- [1..]
                    , not (null (descomposiciones x k n))]

-- El teorema es                                 
teorema_Hilbert_Waring :: Integer -> Integer -> Property
teorema_Hilbert_Waring x k =
  x > 0 && k >= 2
  ==>
  orden x 2 <= 4   &&
  orden x 3 <= 9   &&
  orden x 4 <= 19  &&
  orden x 5 <= 37  &&
  orden x 6 <= 73  &&
  orden x 7 <= 143 &&
  orden x k <= 2^k + floor ((3/2)^k) - 2

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

import Test.QuickCheck

descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]

descomposiciones x k n =

sumas x (takeWhile (<= x) (potencias k)) n

-- (potencias n) es la lista de las potencias de n

-- take 7 (potencias 2) == [1,4,9,16,25,36,49]

-- take 7 (potencias 3) == [1,8,27,64,125,216,343]

potencias :: Integer -> [Integer]

potencias n = map (^n) [1..]

-- (sumas n ys x) es la lista de las descomposiciones de x como

-- sumas de n sumandos de la lista creciente ys. Por ejemplo,

-- sumas 3 [1,2] 2 == [[1,2]]

-- sumas 4 [1,2] 2 == [[2,2]]

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

-- sumas 5 [1,2] 3 == [[1,2,2]]

-- sumas 6 [1,2] 3 == [[2,2,2]]

-- sumas 6 [1,2,5] 2 == [[1,5]]

sumas :: Integer -> [Integer] -> Integer -> [[Integer]]

sumas _ [] _ = []

sumas x ys 1 | x `elem` ys = [[x]]

| otherwise = []

sumas x (y:ys) n | y > x = []

| otherwise = map (y:) (sumas (x-y) (y:ys) (n-1)) ++

sumas x ys n

orden :: Integer -> Integer -> Integer

orden x k = head [n | n <- [1..]

, not (null (descomposiciones x k n))]

-- El teorema es

teorema_Hilbert_Waring :: Integer -> Integer -> Property

teorema_Hilbert_Waring x k =

x > 0 && k >= 2

==>

orden x 2 <= 4 &&

orden x 3 <= 9 &&

orden x 4 <= 19 &&

orden x 5 <= 37 &&

orden x 6 <= 73 &&

orden x 7 <= 143 &&

orden x k <= 2^k + floor ((3/2)^k) - 2

-- La comprobación es

-- λ> quickCheck teorema_Hilbert_Waring

-- +++ OK, passed 100 tests.

Referencia

Basado en Hilbert-Waring theorem de ProofWiki.

Pensamiento

¡Y en la tersa arena,
cerca de la mar,
tu carne rosa y morena,
súbitamente Guiomar!

Antonio Machado

Factorizaciones de 4n+1

PorJosé A. Alonso 6-enero-202013-enero-2020

Sea S el conjunto

   S = {1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, ...}

1	S = {1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, ...}

de los enteros positivos congruentes con 1 módulo 4; es decir,

   S = {4n+1 | n ∈ N}

1	S = {4n+1 \| n ∈ N}

Un elemento n de S es irreducible si sólo es divisible por dos elementos de S: 1 y n. Por ejemplo, 9 es irreducible; pero 45 no lo es (ya que es el proctos de 5 y 9 que son elementos de S).

Definir las funciones

   esIrreducible :: Integer -> Bool
   factorizaciones :: Integer -> [[Integer]]
   conFactorizacionNoUnica :: [Integer]

esIrreducible :: Integer -> Bool

factorizaciones :: Integer -> [[Integer]]

conFactorizacionNoUnica :: [Integer]

tales que

(esIrreducible n) se verifica si n es irreducible. Por ejemplo,

     esIrreducible 9   ==  True
     esIrreducible 45  ==  False

1 2	esIrreducible 9 == True esIrreducible 45 == False

(factorizaciones n) es la lista de conjuntos de elementos irreducibles de S cuyo producto es n. Por ejemplo,

     factorizaciones 9     ==  [[9]]
     factorizaciones 693   ==  [[9,77],[21,33]]
     factorizaciones 4389  ==  [[21,209],[33,133],[57,77]]
     factorizaciones 2205  ==  [[5,9,49],[5,21,21]]

factorizaciones 9 == [[9]]

factorizaciones 693 == [[9,77],[21,33]]

factorizaciones 4389 == [[21,209],[33,133],[57,77]]

factorizaciones 2205 == [[5,9,49],[5,21,21]]

conFactorizacionNoUnica es la lista de elementos de S cuya factorización no es única. Por ejemplo,

     λ> take 10 conFactorizacionNoUnica
     [441,693,1089,1197,1449,1617,1881,1953,2205,2277]

1 2	λ> take 10 conFactorizacionNoUnica [441,693,1089,1197,1449,1617,1881,1953,2205,2277]

Soluciones

esIrreducible :: Integer -> Bool
esIrreducible n = divisores n == [1,n]

-- (divisores n) es el conjunto de elementos de S que dividen a n. Por
-- ejemplo, 
--    divisores 9    ==  [9]
--    divisores 693  ==  [9,21,33,77,693]
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1,5..n], n `mod` x == 0] 
  
factorizaciones :: Integer -> [[Integer]]
factorizaciones 1 = [[1]]
factorizaciones n
  | esIrreducible n = [[n]]
  | otherwise       = [d:ds | d <- divisores n
                            , esIrreducible d
                            , ds@(e:_) <- factorizaciones (n `div` d)
                            , d <= e]

conFactorizacionNoUnica :: [Integer]
conFactorizacionNoUnica =
  [n | n <- [1,5..], length (factorizaciones n) > 1]

esIrreducible :: Integer -> Bool

esIrreducible n = divisores n == [1,n]

-- (divisores n) es el conjunto de elementos de S que dividen a n. Por

-- ejemplo,

-- divisores 9 == [9]

-- divisores 693 == [9,21,33,77,693]

divisores :: Integer -> [Integer]

divisores n = [x | x <- [1,5..n], n `mod` x == 0]

factorizaciones :: Integer -> [[Integer]]

factorizaciones 1 = [[1]]

factorizaciones n

| esIrreducible n = [[n]]

| otherwise = [d:ds | d <- divisores n

, esIrreducible d

, ds@(e:_) <- factorizaciones (n `div` d)

, d <= e]

conFactorizacionNoUnica :: [Integer]

conFactorizacionNoUnica =

[n | n <- [1,5..], length (factorizaciones n) > 1]

Pensamiento

¡Qué bien los nombres ponía
quien puso Sierra Morena
a esta serranía!

Antonio Machado

Conjetura de Grimm

PorJosé A. Alonso 2-enero-202015-enero-2020

La conjetura de Grimm establece que a cada elemento de un conjunto de números compuestos consecutivos se puede asignar un número primo que lo divide, de forma que cada uno de los números primos elegidos es distinto de todos los demás. Más formalmente, si n+1, n+2, …, n+k son números compuestos, entonces existen números primos p(i), distintos entre sí, tales que p(i) divide a n+i para 1 ≤ i ≤ k.

Diremos que la lista ps = [p(1),…,p(k)] es una sucesión de Grim para la lista xs = [x(1),…,x(k)] si p(i) son números primos distintos y p(i) divide a x(i), para 1 ≤ i ≤ k. Por ejemplo, 2, 5, 13, 3, 7 es una sucesión de Grim de 24, 25, 26, 27, 28.

Definir las funciones

   compuestos :: Integer -> [Integer]
   sucesionesDeGrim :: [Integer] -> [[Integer]]

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

tales que

(compuestos n) es la mayor lista de números enteros consecutivos empezando en n. Por ejemplo,

     compuestos 24  ==  [24,25,26,27,28]
     compuestos  8  ==  [8,9,10]
     compuestos 15  ==  [15,16]
     compuestos 16  ==  [16]
     compuestos 17  ==  []

compuestos 24 == [24,25,26,27,28]

compuestos 8 == [8,9,10]

compuestos 15 == [15,16]

compuestos 16 == [16]

compuestos 17 == []

(sucesionesDeGrim xs) es la lista de las sucesiones de Grim de xs. Por ejemplo,

     sucesionesDeGrim [15,16]          == [[3,2],[5,2]]
     sucesionesDeGrim [8,9,10]         == [[2,3,5]]
     sucesionesDeGrim [9,10]           == [[3,2],[3,5]]
     sucesionesDeGrim [24,25,26,27,28] == [[2,5,13,3,7]]
     sucesionesDeGrim [25,26,27,28]    == [[5,2,3,7],[5,13,3,2],[5,13,3,7]]

sucesionesDeGrim [15,16] == [[3,2],[5,2]]

sucesionesDeGrim [8,9,10] == [[2,3,5]]

sucesionesDeGrim [9,10] == [[3,2],[3,5]]

sucesionesDeGrim [24,25,26,27,28] == [[2,5,13,3,7]]

sucesionesDeGrim [25,26,27,28] == [[5,2,3,7],[5,13,3,2],[5,13,3,7]]

Comprobar con QuickCheck la conjetura de Grim; es decir, para todo número n > 1, (sucesionesDeGrim (compuestos n)) es una lista no vacía.

Soluciones

import Data.List (nub)
import Data.Numbers.Primes (isPrime, primeFactors)
import Test.QuickCheck

compuestos :: Integer -> [Integer]
compuestos n = takeWhile (not . isPrime) [n..]

sucesionesDeGrim :: [Integer] -> [[Integer]]
sucesionesDeGrim [] = [[]]
sucesionesDeGrim (x:xs) =
  [y:ys | y <- divisoresPrimos x
        , ys <- sucesionesDeGrim xs
        , y `notElem` ys]

-- (divisoresPrimos n) es la lista de los divisores primos de n. Por
-- ejemplo, 
--    divisoresPrimos 60  ==  [2,3,5]
divisoresPrimos :: Integer -> [Integer]
divisoresPrimos = nub . primeFactors

-- La propiedad es
conjeturaDeGrim :: Integer -> Property
conjeturaDeGrim n =
  n > 1 ==> not (null (sucesionesDeGrim (compuestos n))) 

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

import Data.List (nub)

import Data.Numbers.Primes (isPrime, primeFactors)

import Test.QuickCheck

compuestos :: Integer -> [Integer]

compuestos n = takeWhile (not . isPrime) [n..]

sucesionesDeGrim :: [Integer] -> [[Integer]]

sucesionesDeGrim [] = [[]]

sucesionesDeGrim (x:xs) =

[y:ys | y <- divisoresPrimos x

, ys <- sucesionesDeGrim xs

, y `notElem` ys]

-- (divisoresPrimos n) es la lista de los divisores primos de n. Por

-- ejemplo,

-- divisoresPrimos 60 == [2,3,5]

divisoresPrimos :: Integer -> [Integer]

divisoresPrimos = nub . primeFactors

-- La propiedad es

conjeturaDeGrim :: Integer -> Property

conjeturaDeGrim n =

n > 1 ==> not (null (sucesionesDeGrim (compuestos n)))

-- La comprobación es

-- λ> quickCheck conjeturaDeGrim

-- +++ OK, passed 100 tests.

Pensamiento

De encinar en encinar
se va fatigando el día.

Antonio Machado

Derivada aritmética

PorJosé A. Alonso 31-diciembre-20197-enero-2020

La derivada aritmética es una función definida sobre los números naturales por analogía con la regla del producto para el cálculo de las derivadas usada en análisis.

Para un número natural n su derivada D(n) se define por

   D(0)  = 0
   D(1)  = 0
   D(p)  = 1, si p es primo
   D(ab) = D(a)b + aD(b) (regla de Leibniz para derivar productos)

D(0) = 0

D(1) = 0

D(p) = 1, si p es primo

D(ab) = D(a)b + aD(b) (regla de Leibniz para derivar productos)

Por ejemplo,

   D(6)  = D(2*3) = D(2)*3 + 2*D(3) = 1*3 + 2*1 =  5
   D(12) = D(2*6) = D(2)*6 + 2*D(6) = 1*6 + 2*5 = 16

1 2	D(6) = D(23) = D(2)3 + 2D(3) = 13 + 21 = 5 D(12) = D(26) = D(2)6 + 2D(6) = 16 + 25 = 16

Definir la función

   derivada :: Integer -> Integer

1	derivada :: Integer -> Integer

tal que (derivada n) es la derivada aritmética de n. Por ejemplo,

   derivada  6  ==  5
   derivada 12  ==  16
   maximum [derivada n | n <- [1..60000]]  ==  380928

derivada 6 == 5

derivada 12 == 16

maximum [derivada n | n <- [1..60000]] == 380928

Comprobar con QuickCheck que si x es un número entero positivo y su descomposición en factores primos es

   x = p(1)^e(1) + p(2)^e(2) +...+ p(n)^e(n)

1	x = p(1)^e(1) + p(2)^e(2) +...+ p(n)^e(n)

entonces la derivada de x es

   x * [e(1)/p(1) + e(2)/p(2) +...+ e(n)/p(n)]

1	x * [e(1)/p(1) + e(2)/p(2) +...+ e(n)/p(n)]

Nota: No usar en la definición la propiedad que hay que comprobar.

Soluciones

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

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

derivada :: Integer -> Integer
derivada 0 = 0
derivada 1 = 0
derivada n | esPrimo n = 1
           | otherwise = (derivada a) * b + a * (derivada b)
  where a = menorFactor n
        b = n `div` a

-- (esPrimo n) se verifica si n es primo. Por ejemplo,
--    esPrimo 5  ==  True
--    esPrimo 6  ==  False
esPrimo :: Integer -> Bool
esPrimo 0 = False
esPrimo 1 = False
esPrimo n = n == menorFactor n

-- (menorFactor n) es el menor divisor primo de n (con n >= 2). Por
-- ejemplo, 
--    menorFactor 6   ==  2
--    menorFactor 7   ==  7
--    menorFactor 15  ==  3
menorFactor :: Integer -> Integer
menorFactor n
  | even n = 2
  | otherwise = head [x | x <- [3,5..]
                        , n `mod` x == 0]

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

derivada2 :: Integer -> Integer
derivada2 0 = 0
derivada2 1 = 0
derivada2 n | isPrime n = 1
            | otherwise = (derivada2 a) * b + a * (derivada2 b)
  where (a:_) = primeFactors n
        b     = n `div` a

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

--    λ> maximum [derivada n | n <- [1..10000]]
--    53248
--    (1.59 secs, 1,091,452,552 bytes)
--    λ> maximum [derivada2 n | n <- [1..10000]]
--    53248
--    (0.17 secs, 457,819,120 bytes)

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

-- La propiedad es
prop_derivada :: Integer -> Property
prop_derivada x =
  x > 0 ==>
  derivada x == sum [(x * e) `div` p | (p,e) <- factorizacion x]

-- (factorizacion x) es la lista de las bases y exponentes de
-- la descomposición prima de x. Por ejemplo,
--    factorizacion 600  ==  [(2,3),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  [(head xs,genericLength xs) | xs <- group (primeFactors n)]

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

import Data.List (genericLength, group)

import Data.Numbers.Primes (isPrime, primeFactors)

import Test.QuickCheck

-- 1ª solución

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

derivada :: Integer -> Integer

derivada 0 = 0

derivada 1 = 0

derivada n | esPrimo n = 1

| otherwise = (derivada a) * b + a * (derivada b)

where a = menorFactor n

b = n `div` a

-- (esPrimo n) se verifica si n es primo. Por ejemplo,

-- esPrimo 5 == True

-- esPrimo 6 == False

esPrimo :: Integer -> Bool

esPrimo 0 = False

esPrimo 1 = False

esPrimo n = n == menorFactor n

-- (menorFactor n) es el menor divisor primo de n (con n >= 2). Por

-- ejemplo,

-- menorFactor 6 == 2

-- menorFactor 7 == 7

-- menorFactor 15 == 3

menorFactor :: Integer -> Integer

menorFactor n

| even n = 2

| otherwise = head [x | x <- [3,5..]

, n `mod` x == 0]

-- 2ª solución

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

derivada2 :: Integer -> Integer

derivada2 0 = 0

derivada2 1 = 0

derivada2 n | isPrime n = 1

| otherwise = (derivada2 a) * b + a * (derivada2 b)

where (a:_) = primeFactors n

b = n `div` a

-- Comparación de eficiencia

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

-- λ> maximum [derivada n | n <- [1..10000]]

-- 53248

-- (1.59 secs, 1,091,452,552 bytes)

-- λ> maximum [derivada2 n | n <- [1..10000]]

-- 53248

-- (0.17 secs, 457,819,120 bytes)

-- Propiedad

-- =========

-- La propiedad es

prop_derivada :: Integer -> Property

prop_derivada x =

x > 0 ==>

derivada x == sum [(x * e) `div` p | (p,e) <- factorizacion x]

-- (factorizacion x) es la lista de las bases y exponentes de

-- la descomposición prima de x. Por ejemplo,

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

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

factorizacion n =

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

-- Su comprobación es

-- λ> quickCheck prop_derivada

-- +++ OK, passed 100 tests.

Referencias

Arithmetic derivative en Wikipedia.
Sucesión A003415 de OEIS.

Pensamiento

En ese jardín, Guiomar,
el mutuo jardín que inventan
dos corazones al par,
se funden y complementan
nuestras horas.

Antonio Machado

Posiciones de conjuntos finitos de naturales

PorJosé A. Alonso 27-diciembre-20193-enero-2020

En un ejercicio anterior se mostró que los conjuntos finitos de números naturales se pueden enumerar como sigue

    0: []
    1: [0]
    2: [1]
    3: [1,0]
    4: [2]
    5: [2,0]
    6: [2,1]
    7: [2,1,0]
    8: [3]
    9: [3,0]
   10: [3,1]
   11: [3,1,0]
   12: [3,2]
   13: [3,2,0]
   14: [3,2,1]
   15: [3,2,1,0]
   16: [4]
   17: [4,0]
   18: [4,1]
   19: [4,1,0]

0: []

1: [0]

2: [1]

3: [1,0]

4: [2]

5: [2,0]

6: [2,1]

7: [2,1,0]

8: [3]

9: [3,0]

10: [3,1]

11: [3,1,0]

12: [3,2]

13: [3,2,0]

14: [3,2,1]

15: [3,2,1,0]

16: [4]

17: [4,0]

18: [4,1]

19: [4,1,0]

en la que los elementos están ordenados de manera decreciente.

Además, se definió la constante

   enumeracionCFN :: [[Integer]]

1	enumeracionCFN :: [[Integer]]

tal que sus elementos son los conjuntos de los números naturales con la ordenación descrita anteriormente. Por ejemplo,

   λ> take 20 enumeracionCFN
   [[],
    [0],
    [1],[1,0],
    [2],[2,0],[2,1],[2,1,0],
    [3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],
    [4],[4,0],[4,1],[4,1,0]]

λ> take 20 enumeracionCFN

[[],

[0],

[1],[1,0],

[2],[2,0],[2,1],[2,1,0],

[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],

[4],[4,0],[4,1],[4,1,0]]

Definir la función

   posicion :: [Integer] -> Integer

1	posicion :: [Integer] -> Integer

tal que (posicion xs) es la posición del conjunto finito de números naturales xs, representado por una lista decreciente, en enumeracionCFN. Por ejemplo,

   posicion [2,0]          ==  5
   posicion [2,1]          ==  6
   posicion [2,1,0]        ==  7
   posicion [0]            ==  1
   posicion [1,0]          ==  3
   posicion [2,1,0]        ==  7
   posicion [3,2,1,0]      ==  15
   posicion [4,3,2,1,0]    ==  31
   posicion [5,4,3,2,1,0]  ==  63
   length (show (posicion [3*10^7])) == 9030900

posicion [2,0] == 5

posicion [2,1] == 6

posicion [2,1,0] == 7

posicion [0] == 1

posicion [1,0] == 3

posicion [2,1,0] == 7

posicion [3,2,1,0] == 15

posicion [4,3,2,1,0] == 31

posicion [5,4,3,2,1,0] == 63

length (show (posicion [3*10^7])) == 9030900

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

   posicion [n,n-1..0] == 2^(n+1) - 1.

1	posicion [n,n-1..0] == 2^(n+1) - 1.

Soluciones

import Data.List (genericLength, nub, sort)
import Test.QuickCheck

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

posicion :: [Integer] -> Integer
posicion xs =
  genericLength (takeWhile (< xs) enumeracionCFN)

enumeracionCFN :: [[Integer]]
enumeracionCFN = concatMap enumeracionCFNHasta [0..]

-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeración
-- anterior cuyo primer elemento es n. Por ejemplo,
--    λ> enumeracionCFNHasta 1
--    [[1],[1,0]]
--    λ> enumeracionCFNHasta 2
--    [[2],[2,0],[2,1],[2,1,0]]
--    λ> enumeracionCFNHasta 3
--    [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]
enumeracionCFNHasta :: Integer -> [[Integer]]
enumeracionCFNHasta 0 = [[],[0]]
enumeracionCFNHasta n =
  [n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]

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

posicion2 :: [Integer] -> Integer
posicion2 []     = 0
posicion2 (x:xs) = 2^x + posicion2 xs

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

posicion3 :: [Integer] -> Integer
posicion3 = foldr (\x -> (+) (2^x)) 0 

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

posicion4 :: [Integer] -> Integer
posicion4 xs = sum [2^x | x <- xs ]

-- Equivalencia de las definiciones
-- ================================

-- La propiedad es
prop_equiv :: [Integer] -> Bool
prop_equiv xs =
  all (== posicion xs') [f xs' | f <- [ posicion2
                                      , posicion3
                                      , posicion4]]
  where xs' = reverse (sort (nub (map abs xs)))

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=15}) prop_equiv
--    +++ OK, passed 100 tests.

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

-- La comparación es
--    λ> posicion [19,18,17,16,14,9,6]
--    1000000
--    (2.61 secs, 1,754,265,776 bytes)
--    λ> posicion2 [19,18,17,16,14,9,6]
--    1000000
--    (0.01 secs, 111,808 bytes)
--    λ> posicion3 [19,18,17,16,14,9,6]
--    1000000
--    λ> posicion4 [19,18,17,16,14,9,6]
--    1000000
--    (0.01 secs, 111,704 bytes)

--    λ> length (show (posicion2 [3*10^7]))
--    9030900
--    (2.06 secs, 571,911,304 bytes)
--    λ> length (show (posicion3 [3*10^7]))
--    9030900
--    (2.06 secs, 571,911,544 bytes)
--    λ> length (show (posicion4 [3*10^7]))
--    9030900
--    (2.05 secs, 571,911,464 bytes)

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

-- La propiedad es
prop_posicion :: Integer -> Property
prop_posicion n =
  n >= 0 ==> posicion3 [n,n-1..0] == 2^(n+1) - 1

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

import Data.List (genericLength, nub, sort)

import Test.QuickCheck

-- 1ª solución

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

posicion :: [Integer] -> Integer

posicion xs =

genericLength (takeWhile (< xs) enumeracionCFN)

enumeracionCFN :: [[Integer]]

enumeracionCFN = concatMap enumeracionCFNHasta [0..]

-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeración

-- anterior cuyo primer elemento es n. Por ejemplo,

-- λ> enumeracionCFNHasta 1

-- [[1],[1,0]]

-- λ> enumeracionCFNHasta 2

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

-- λ> enumeracionCFNHasta 3

-- [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]

enumeracionCFNHasta :: Integer -> [[Integer]]

enumeracionCFNHasta 0 = [[],[0]]

enumeracionCFNHasta n =

[n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]

-- 2ª solución

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

posicion2 :: [Integer] -> Integer

posicion2 [] = 0

posicion2 (x:xs) = 2^x + posicion2 xs

-- 3ª solución

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

posicion3 :: [Integer] -> Integer

posicion3 = foldr (\x -> (+) (2^x)) 0

-- 4ª solución

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

posicion4 :: [Integer] -> Integer

posicion4 xs = sum [2^x | x <- xs ]

-- Equivalencia de las definiciones

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

-- La propiedad es

prop_equiv :: [Integer] -> Bool

prop_equiv xs =

all (== posicion xs') [f xs' | f <- [ posicion2

, posicion3

, posicion4]]

where xs' = reverse (sort (nub (map abs xs)))

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=15}) prop_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- La comparación es

-- λ> posicion [19,18,17,16,14,9,6]

-- 1000000

-- (2.61 secs, 1,754,265,776 bytes)

-- λ> posicion2 [19,18,17,16,14,9,6]

-- 1000000

-- (0.01 secs, 111,808 bytes)

-- λ> posicion3 [19,18,17,16,14,9,6]

-- 1000000

-- λ> posicion4 [19,18,17,16,14,9,6]

-- 1000000

-- (0.01 secs, 111,704 bytes)

-- λ> length (show (posicion2 [3*10^7]))

-- 9030900

-- (2.06 secs, 571,911,304 bytes)

-- λ> length (show (posicion3 [3*10^7]))

-- 9030900

-- (2.06 secs, 571,911,544 bytes)

-- λ> length (show (posicion4 [3*10^7]))

-- 9030900

-- (2.05 secs, 571,911,464 bytes)

-- Propiedad

-- =========

-- La propiedad es

prop_posicion :: Integer -> Property

prop_posicion n =

n >= 0 ==> posicion3 [n,n-1..0] == 2^(n+1) - 1

-- La comprobación es

-- λ> quickCheck prop_posicion

-- +++ OK, passed 100 tests.

Pensamiento

¡Volar sin alas donde todo es cielo!

Antonio Machado

Conjuntos con más sumas que restas

PorJosé A. Alonso 26-diciembre-20192-enero-2020

Dado un conjunto de números naturales, por ejemplo A = {0, 2, 3, 4}, calculamos las sumas de todos los pares de elementos de A. Como A tiene 4 elementos hay 16 pares, pero no todas sus sumas son distintas. En este caso solo hay 8 sumas distintas: {0, 2, 3, 4, 5, 6, 7, 8}. Procediendo análogamente hay 9 diferencias distinatas entre los pares de A: {-4, -3, -2, -1, 0, 1, 2, 3, 4}.

Experimentando con más conjuntos, se puede conjeturar que el número de restas es mayor que el de sumas y argumentar que que mientras que con dos números distintos sólo se produce una suma distints sin embargo se producen dos restas distintas. Por ejemplo, con 5 y 7 sólo se produce una suma (ya que 5+7 y 7+5 ambos dan 12) pero dos restas (ya que 5-7 y 7-5 dan -2 y 2, respectivamente).

Sin embargo, la conjetura es falsa. Un contraejemplo en el conjunto {0, 2, 3, 4, 7, 11, 12, 14}, que tiene 26 sumas distintas con sus pares de elementos pero sólo 25 restas.

Los conjuntos con más sumas distintas con sus pares de elementos que restas se llaman conjuntos MSQR (por «más sumas que restas»).

El objetivo de este ejercicio es calcular los conjuntos MSQR.

Definir las funciones

   tieneMSQR :: [Integer] -> Bool
   conjuntosMSQR :: [[Integer]]

1 2	tieneMSQR :: [Integer] -> Bool conjuntosMSQR :: [[Integer]]

tales que

(tieneMSQR xs) se verifica si el conjunto xs tiene más sumas que restas. Por ejemplo,

     tieneMSQR [0, 2, 3, 4]                 ==  False
     tieneMSQR [0, 2, 3, 4, 7, 11, 12, 14]  ==  True

1 2	tieneMSQR [0, 2, 3, 4] == False tieneMSQR [0, 2, 3, 4, 7, 11, 12, 14] == True

conjuntosMSQR es la lista de los conjuntos MSQR. Por ejemplo,

     λ> take 5 conjuntosMSQR
     [[14,12,11,7,4,3,2,0],
      [14,12,11,10,7,3,2,0],
      [14,13,12,9,5,4,2,1,0],
      [14,13,12,10,9,5,2,1,0],
      [15,13,12,8,5,4,3,1]]
   
      length (takeWhile (< [14]) conjuntosMSQR)   ==  0
      length (takeWhile (< [15]) conjuntosMSQR)   ==  4
      length (takeWhile (< [16]) conjuntosMSQR)   ==  10
      length (takeWhile (< [17]) conjuntosMSQR)   ==  30

λ> take 5 conjuntosMSQR

[[14,12,11,7,4,3,2,0],

[14,12,11,10,7,3,2,0],

[14,13,12,9,5,4,2,1,0],

[14,13,12,10,9,5,2,1,0],

[15,13,12,8,5,4,3,1]]

length (takeWhile (< [14]) conjuntosMSQR) == 0

length (takeWhile (< [15]) conjuntosMSQR) == 4

length (takeWhile (< [16]) conjuntosMSQR) == 10

length (takeWhile (< [17]) conjuntosMSQR) == 30

Soluciones

import Data.List (tails, nub, sort)

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

-- (sumas xs) es el conjunto de las sumas de pares de elementos de
-- xs. Por ejemplo,
--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]
sumas :: [Integer] -> [Integer]
sumas xs = nub [x + y | x <- xs, y <- xs]

-- (restas xs) es el conjunto de las restas de pares de elementos de
-- xs. Por ejemplo,
--    restas [0,2,3,4]  ==  [0,-2,-3,-4,2,-1,3,1,4]
restas :: [Integer] -> [Integer]
restas xs = nub [x - y | x <- xs, y <- xs]

tieneMSQR :: [Integer] -> Bool
tieneMSQR xs = length (sumas xs) > length (restas xs)

conjuntosMSQR :: [[Integer]]
conjuntosMSQR = [xs | xs <- enumeracionCFN, tieneMSQR xs]

-- enumeracionCFN es la enumeración de los conjuntos finitos de números
-- naturales del ejercicio anterior.
enumeracionCFN :: [[Integer]]
enumeracionCFN = concatMap enumeracionCFNHasta [0..]

-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeración
-- anterior cuyo primer elemento es n. Por ejemplo,
--    λ> enumeracionCFNHasta 1
--    [[1],[1,0]]
--    λ> enumeracionCFNHasta 2
--    [[2],[2,0],[2,1],[2,1,0]]
--    λ> enumeracionCFNHasta 3
--    [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]
enumeracionCFNHasta :: Integer -> [[Integer]]
enumeracionCFNHasta 0 = [[],[0]]
enumeracionCFNHasta n =
  [n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]

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

-- (sumas2 xs) es el conjunto de las sumas de pares de elementos de
-- xs. Por ejemplo,
--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]
--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]
sumas2 :: [Integer] -> [Integer]
sumas2 xs = nub [x + y | (x:ys) <- tails xs, y <- (x:ys)]

-- (restas2 xs) es el conjunto de las restas de pares de elementos de
-- xs. Por ejemplo,
--    sumas2 [0,2,3,4]  ==  [0,2,3,4,5,6,7,8]
--    restas2 [0,2,3,4]  ==  [0,-2,-3,-4,2,-1,3,1,4]
restas2 :: [Integer] -> [Integer]
restas2 xs = 0 : ys ++ map negate ys
  where ys = nub [x - y | (x:ys) <- tails (sort xs), y <- ys]

tieneMSQR2 :: [Integer] -> Bool
tieneMSQR2 xs = length (sumas2 xs) > length (restas2 xs)

conjuntosMSQR2 :: [[Integer]]
conjuntosMSQR2 = [xs | xs <- enumeracionCFN, tieneMSQR2 xs]

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

--    λ> length (takeWhile (< [17,16..0]) conjuntosMSQR)
--    66
--    (21.36 secs, 10,301,222,168 bytes)
--    λ> length (takeWhile (< [17,16..0]) conjuntosMSQR2)
--    66
--    (10.13 secs, 7,088,969,752 bytes)

import Data.List (tails, nub, sort)

-- 1ª solución

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

-- (sumas xs) es el conjunto de las sumas de pares de elementos de

-- xs. Por ejemplo,

-- sumas2 [0,2,3,4] == [0,2,3,4,5,6,7,8]

sumas :: [Integer] -> [Integer]

sumas xs = nub [x + y | x <- xs, y <- xs]

-- (restas xs) es el conjunto de las restas de pares de elementos de

-- xs. Por ejemplo,

-- restas [0,2,3,4] == [0,-2,-3,-4,2,-1,3,1,4]

restas :: [Integer] -> [Integer]

restas xs = nub [x - y | x <- xs, y <- xs]

tieneMSQR :: [Integer] -> Bool

tieneMSQR xs = length (sumas xs) > length (restas xs)

conjuntosMSQR :: [[Integer]]

conjuntosMSQR = [xs | xs <- enumeracionCFN, tieneMSQR xs]

-- enumeracionCFN es la enumeración de los conjuntos finitos de números

-- naturales del ejercicio anterior.

enumeracionCFN :: [[Integer]]

enumeracionCFN = concatMap enumeracionCFNHasta [0..]

-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeración

-- anterior cuyo primer elemento es n. Por ejemplo,

-- λ> enumeracionCFNHasta 1

-- [[1],[1,0]]

-- λ> enumeracionCFNHasta 2

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

-- λ> enumeracionCFNHasta 3

-- [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]

enumeracionCFNHasta :: Integer -> [[Integer]]

enumeracionCFNHasta 0 = [[],[0]]

enumeracionCFNHasta n =

[n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]

-- 2ª solución

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

-- (sumas2 xs) es el conjunto de las sumas de pares de elementos de

-- xs. Por ejemplo,

-- sumas2 [0,2,3,4] == [0,2,3,4,5,6,7,8]

sumas2 :: [Integer] -> [Integer]

sumas2 xs = nub [x + y | (x:ys) <- tails xs, y <- (x:ys)]

-- (restas2 xs) es el conjunto de las restas de pares de elementos de

-- xs. Por ejemplo,

-- sumas2 [0,2,3,4] == [0,2,3,4,5,6,7,8]

-- restas2 [0,2,3,4] == [0,-2,-3,-4,2,-1,3,1,4]

restas2 :: [Integer] -> [Integer]

restas2 xs = 0 : ys ++ map negate ys

where ys = nub [x - y | (x:ys) <- tails (sort xs), y <- ys]

tieneMSQR2 :: [Integer] -> Bool

tieneMSQR2 xs = length (sumas2 xs) > length (restas2 xs)

conjuntosMSQR2 :: [[Integer]]

conjuntosMSQR2 = [xs | xs <- enumeracionCFN, tieneMSQR2 xs]

-- Comparación de eficiencia

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

-- λ> length (takeWhile (< [17,16..0]) conjuntosMSQR)

-- 66

-- (21.36 secs, 10,301,222,168 bytes)

-- λ> length (takeWhile (< [17,16..0]) conjuntosMSQR2)

-- 66

-- (10.13 secs, 7,088,969,752 bytes)

Pensamiento

¡Qué fácil es volar, qué fácil es!
Todo consiste en no dejar que el suelo
se acerque a nuestros pies.

Antonio Machado

Enumeración de conjuntos finitos de naturales

PorJosé A. Alonso 25-diciembre-20191-enero-2020

Los conjuntos finitos de números naturales se pueden enumerar como sigue

    0: []
    1: [0]
    2: [1]
    3: [1,0]
    4: [2]
    5: [2,0]
    6: [2,1]
    7: [2,1,0]
    8: [3]
    9: [3,0]
   10: [3,1]
   11: [3,1,0]
   12: [3,2]
   13: [3,2,0]
   14: [3,2,1]
   15: [3,2,1,0]
   16: [4]
   17: [4,0]
   18: [4,1]
   19: [4,1,0]

0: []

1: [0]

2: [1]

3: [1,0]

4: [2]

5: [2,0]

6: [2,1]

7: [2,1,0]

8: [3]

9: [3,0]

10: [3,1]

11: [3,1,0]

12: [3,2]

13: [3,2,0]

14: [3,2,1]

15: [3,2,1,0]

16: [4]

17: [4,0]

18: [4,1]

19: [4,1,0]

en la que los elementos están ordenados de manera decreciente.

Definir la constante

   enumeracionCFN :: [[Integer]]

1	enumeracionCFN :: [[Integer]]

tal que sus elementos son los conjuntos de los números naturales con la ordenación descrita anteriormente. Por ejemplo,

   λ> take 20 enumeracionCFN
   [[],
    [0],
    [1],[1,0],
    [2],[2,0],[2,1],[2,1,0],
    [3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],
    [4],[4,0],[4,1],[4,1,0]]

λ> take 20 enumeracionCFN

[[],

[0],

[1],[1,0],

[2],[2,0],[2,1],[2,1,0],

[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],

[4],[4,0],[4,1],[4,1,0]]

Comprobar con QuickCheck que

si (xs,ys) es un par de elementos consecutivos de enumeracionCFN, entonces xs < ys;
todo conjunto finito de números naturales, representado por una lista decreciente, está en enumeracionCFN.

Soluciones

import Data.List (genericLength, nub, sort)
import Test.QuickCheck

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

enumeracionCFN :: [[Integer]]
enumeracionCFN = concatMap enumeracionCFNHasta [0..]

-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeración
-- anterior cuyo primer elemento es n. Por ejemplo,
--    λ> enumeracionCFNHasta 1
--    [[1],[1,0]]
--    λ> enumeracionCFNHasta 2
--    [[2],[2,0],[2,1],[2,1,0]]
--    λ> enumeracionCFNHasta 3
--    [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]
enumeracionCFNHasta :: Integer -> [[Integer]]
enumeracionCFNHasta 0 = [[],[0]]
enumeracionCFNHasta n =
  [n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]

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

enumeracionCFN2 :: [[Integer]]
enumeracionCFN2 = [] : aux 0 [[]]
  where aux n xs = yss ++ aux (n+1) (xs ++ yss)
          where yss = map (n:) xs

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

enumeracionCFN3 :: [[Integer]]
enumeracionCFN3 = map conjunto [0..]

-- (conjunto n) es el conjunto en la posición n. Por ejemplo,
--   conjunto 6  ==  [2,1]
conjunto :: Integer -> [Integer]
conjunto n = reverse [x | (x,y) <- zip [0..] (binario n), y == 1]

-- (binario n) es la representación binarioa del número n (en orden
-- inverso). Por ejemplo,
--   binario 6  ==  [0,1,1]
binario :: Integer -> [Integer]
binario 0 = [0]
binario 1 = [1]
binario n = n `mod` 2 : binario (n `div` 2)

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

--    λ> enumeracionCFN !! (4*10^5)
--    [18,17,12,11,9,7]
--    (1.18 secs, 576,924,344 bytes)
--    λ> enumeracionCFN2 !! (4*10^5)
--    [18,17,12,11,9,7]
--    (0.10 secs, 72,399,784 bytes)
--    λ> enumeracionCFN3 !! (4*10^5)
--    [18,17,12,11,9,7]
--    (0.07 secs, 64,123,952 bytes)
--
--    λ> enumeracionCFN2 !! (6*10^6)
--    [22,20,19,17,16,15,11,10,8,7]
--    (1.25 secs, 1,082,690,216 bytes)
--    λ> enumeracionCFN3 !! (6*10^6)
--    [22,20,19,17,16,15,11,10,8,7]
--    (0.38 secs, 960,134,256 bytes)

-- Propiedades
-- ===========

-- La primera propiedad es
prop_enumeracionCFN :: Int -> Property
prop_enumeracionCFN n =
  n >= 0 ==> xs < ys
  where (xs:ys:_) = drop n enumeracionCFN

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

-- La segunda propiedad es
prop_completa :: [Integer] -> Bool
prop_completa xs =
  xs' `elem` enumeracionCFN
  where xs' = reverse (sort (nub (map abs xs)))

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=15}) prop_completa
--    +++ OK, passed 100 tests.

import Data.List (genericLength, nub, sort)

import Test.QuickCheck

-- 1ª solución

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

enumeracionCFN :: [[Integer]]

enumeracionCFN = concatMap enumeracionCFNHasta [0..]

-- (enumeracionCFNHasta n) es la lista de conjuntos con la enumeración

-- anterior cuyo primer elemento es n. Por ejemplo,

-- λ> enumeracionCFNHasta 1

-- [[1],[1,0]]

-- λ> enumeracionCFNHasta 2

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

-- λ> enumeracionCFNHasta 3

-- [[3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0]]

enumeracionCFNHasta :: Integer -> [[Integer]]

enumeracionCFNHasta 0 = [[],[0]]

enumeracionCFNHasta n =

[n:xs | k <- [0..n-1], xs <- enumeracionCFNHasta k]

-- 2ª solución

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

enumeracionCFN2 :: [[Integer]]

enumeracionCFN2 = [] : aux 0 [[]]

where aux n xs = yss ++ aux (n+1) (xs ++ yss)

where yss = map (n:) xs

-- 3ª solución

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

enumeracionCFN3 :: [[Integer]]

enumeracionCFN3 = map conjunto [0..]

-- (conjunto n) es el conjunto en la posición n. Por ejemplo,

-- conjunto 6 == [2,1]

conjunto :: Integer -> [Integer]

conjunto n = reverse [x | (x,y) <- zip [0..] (binario n), y == 1]

-- (binario n) es la representación binarioa del número n (en orden

-- inverso). Por ejemplo,

-- binario 6 == [0,1,1]

binario :: Integer -> [Integer]

binario 0 = [0]

binario 1 = [1]

binario n = n `mod` 2 : binario (n `div` 2)

-- Comparación de eficiencia

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

-- λ> enumeracionCFN !! (4*10^5)

-- [18,17,12,11,9,7]

-- (1.18 secs, 576,924,344 bytes)

-- λ> enumeracionCFN2 !! (4*10^5)

-- [18,17,12,11,9,7]

-- (0.10 secs, 72,399,784 bytes)

-- λ> enumeracionCFN3 !! (4*10^5)

-- [18,17,12,11,9,7]

-- (0.07 secs, 64,123,952 bytes)

-- λ> enumeracionCFN2 !! (6*10^6)

-- [22,20,19,17,16,15,11,10,8,7]

-- (1.25 secs, 1,082,690,216 bytes)

-- λ> enumeracionCFN3 !! (6*10^6)

-- [22,20,19,17,16,15,11,10,8,7]

-- (0.38 secs, 960,134,256 bytes)

-- Propiedades

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

-- La primera propiedad es

prop_enumeracionCFN :: Int -> Property

prop_enumeracionCFN n =

n >= 0 ==> xs < ys

where (xs:ys:_) = drop n enumeracionCFN

-- La comprobación es

-- λ> quickCheck prop_enumeracionCFN

-- +++ OK, passed 100 tests.

-- La segunda propiedad es

prop_completa :: [Integer] -> Bool

prop_completa xs =

xs' `elem` enumeracionCFN

where xs' = reverse (sort (nub (map abs xs)))

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=15}) prop_completa

-- +++ OK, passed 100 tests.

Pensamiento

Junto al agua fría,
en la senda clara,
sombra dará algún día,
ese arbolillo en que nadie repara.

Antonio Machado

El teorema de Navidad de Fermat

PorJosé A. Alonso 20-diciembre-201927-diciembre-2019

El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el Teorema de Navidad de Fermat.

Definir las funciones

   representaciones :: Integer -> [(Integer,Integer)]
   primosImparesConRepresentacionUnica :: [Integer]
   primos4nM1 :: [Integer]

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

primosImparesConRepresentacionUnica :: [Integer]

primos4nM1 :: [Integer]

tales que

(representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo,

     representaciones  20           ==  [(2,4)]
     representaciones  25           ==  [(0,5),(3,4)]
     representaciones 325           ==  [(1,18),(6,17),(10,15)]
     representaciones 100000147984  ==  [(0,316228)]
     length (representaciones (10^10))    ==  6
     length (representaciones (4*10^12))  ==  7

representaciones 20 == [(2,4)]

representaciones 25 == [(0,5),(3,4)]

representaciones 325 == [(1,18),(6,17),(10,15)]

representaciones 100000147984 == [(0,316228)]

length (representaciones (10^10)) == 6

length (representaciones (4*10^12)) == 7

primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,

     λ> take 20 primosImparesConRepresentacionUnica
     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

1 2	λ> take 20 primosImparesConRepresentacionUnica [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,

     λ> take 20 primos4nM1
     [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

1 2	λ> take 20 primos4nM1 [5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y^2 (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).

Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.

Soluciones

import Data.Numbers.Primes (primes)
import Test.QuickCheck

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

representaciones :: Integer -> [(Integer,Integer)]
representaciones n =
  [(x,y) | x <- [0..n], y <- [x..n], n == x*x + y*y]

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

representaciones2 :: Integer -> [(Integer,Integer)]
representaciones2 n =
  [(x,raiz z) | x <- [0..raiz (n `div` 2)] 
              , let z = n - x*x
              , esCuadrado z]

-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
  where y = raiz x

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz 25  ==  5
--    raiz 24  ==  4
--    raiz 26  ==  5
raiz :: Integer -> Integer 
raiz 0 = 0
raiz 1 = 1
raiz x = aux (0,x)
    where aux (a,b) | d == x    = c
                    | c == a    = a
                    | d < x     = aux (c,b)
                    | otherwise = aux (a,c) 
              where c = (a+b) `div` 2
                    d = c^2

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

representaciones3 :: Integer -> [(Integer,Integer)]
representaciones3 n =
  [(x,raiz3 z) | x <- [0..raiz3 (n `div` 2)] 
               , let z = n - x*x
               , esCuadrado3 z]

-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado3 25  ==  True
--    esCuadrado3 26  ==  False
esCuadrado3 :: Integer -> Bool
esCuadrado3 x = x == y * y
  where y = raiz3 x

-- (raiz3 x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz3 25  ==  5
--    raiz3 24  ==  4
--    raiz3 26  ==  5
raiz3 :: Integer -> Integer
raiz3 x = floor (sqrt (fromIntegral x))
          
-- 4ª definición de representaciones
-- =================================
 
representaciones4 :: Integer -> [(Integer, Integer)]
representaciones4 n = aux 0 (floor (sqrt (fromIntegral n)))
  where aux x y
          | x > y     = [] 
          | otherwise = case compare (x*x + y*y) n of
                          LT -> aux (x + 1) y
                          EQ -> (x, y) : aux (x + 1) (y - 1)
                          GT -> aux x (y - 1)

-- Equivalencia de las definiciones de representaciones
-- ====================================================

-- La propiedad es
prop_representaciones_equiv :: (Positive Integer) -> Bool
prop_representaciones_equiv (Positive n) =
  representaciones  n == representaciones2 n &&
  representaciones2 n == representaciones3 n &&
  representaciones3 n == representaciones4 n

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

-- Comparación de eficiencia de las definiciones de representaciones
-- =================================================================

--    λ> representaciones 3025
--    [(0,55),(33,44)]
--    (2.86 secs, 1,393,133,528 bytes)
--    λ> representaciones2 3025
--    [(0,55),(33,44)]
--    (0.00 secs, 867,944 bytes)
--    λ> representaciones3 3025
--    [(0,55),(33,44)]
--    (0.00 secs, 173,512 bytes)
--    λ> representaciones4 3025
--    [(0,55),(33,44)]
--    (0.00 secs, 423,424 bytes)
--    
--    λ> length (representaciones2 (10^10))
--    6
--    (3.38 secs, 2,188,903,544 bytes)
--    λ> length (representaciones3 (10^10))
--    6
--    (0.10 secs, 62,349,048 bytes)
--    λ> length (representaciones4 (10^10))
--    6
--    (0.11 secs, 48,052,360 bytes)
--
--    λ> length (representaciones3 (4*10^12))
--    7
--    (1.85 secs, 1,222,007,176 bytes)
--    λ> length (representaciones4 (4*10^12))
--    7
--    (1.79 secs, 953,497,480 bytes)

-- Definición de primosImparesConRepresentacionUnica
-- =================================================

primosImparesConRepresentacionUnica :: [Integer]
primosImparesConRepresentacionUnica =
  [x | x <- tail primes
     , length (representaciones4 x) == 1]

-- Definición de primos4nM1
-- ========================

primos4nM1 :: [Integer]
primos4nM1 = [x | x <- primes
                , x `mod` 4 == 1]

-- Teorema de Navidad de Fermat
-- ============================

-- La propiedad es
prop_teoremaDeNavidadDeFermat :: Positive Int -> Bool
prop_teoremaDeNavidadDeFermat (Positive n) =
  primosImparesConRepresentacionUnica !! n == primos4nM1 !! n
             
-- La comprobación es
--    λ> quickCheck prop_teoremaDeNavidadDeFermat
--    +++ OK, passed 100 tests.

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

import Data.Numbers.Primes (primes)

import Test.QuickCheck

-- 1ª definición de representaciones

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

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

representaciones n =

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

-- 2ª definición de representaciones

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

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

representaciones2 n =

[(x,raiz z) | x <- [0..raiz (n `div` 2)]

, let z = n - x*x

, esCuadrado z]

-- (esCuadrado x) se verifica si x es un número al cuadrado. Por

-- ejemplo,

-- esCuadrado 25 == True

-- esCuadrado 26 == False

esCuadrado :: Integer -> Bool

esCuadrado x = x == y * y

where y = raiz x

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,

-- raiz 25 == 5

-- raiz 24 == 4

-- raiz 26 == 5

raiz :: Integer -> Integer

raiz 0 = 0

raiz 1 = 1

raiz x = aux (0,x)

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

| c == a = a

| d < x = aux (c,b)

| otherwise = aux (a,c)

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

d = c^2

-- 3ª definición de representaciones

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

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

representaciones3 n =

[(x,raiz3 z) | x <- [0..raiz3 (n `div` 2)]

, let z = n - x*x

, esCuadrado3 z]

-- (esCuadrado x) se verifica si x es un número al cuadrado. Por

-- ejemplo,

-- esCuadrado3 25 == True

-- esCuadrado3 26 == False

esCuadrado3 :: Integer -> Bool

esCuadrado3 x = x == y * y

where y = raiz3 x

-- (raiz3 x) es la raíz cuadrada entera de x. Por ejemplo,

-- raiz3 25 == 5

-- raiz3 24 == 4

-- raiz3 26 == 5

raiz3 :: Integer -> Integer

raiz3 x = floor (sqrt (fromIntegral x))

-- 4ª definición de representaciones

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

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

representaciones4 n = aux 0 (floor (sqrt (fromIntegral n)))

where aux x y

| x > y = []

| otherwise = case compare (x*x + y*y) n of

LT -> aux (x + 1) y

EQ -> (x, y) : aux (x + 1) (y - 1)

GT -> aux x (y - 1)

-- Equivalencia de las definiciones de representaciones

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

-- La propiedad es

prop_representaciones_equiv :: (Positive Integer) -> Bool

prop_representaciones_equiv (Positive n) =

representaciones n == representaciones2 n &&

representaciones2 n == representaciones3 n &&

representaciones3 n == representaciones4 n

-- La comprobación es

-- λ> quickCheck prop_representaciones_equiv

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia de las definiciones de representaciones

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

-- λ> representaciones 3025

-- [(0,55),(33,44)]

-- (2.86 secs, 1,393,133,528 bytes)

-- λ> representaciones2 3025

-- [(0,55),(33,44)]

-- (0.00 secs, 867,944 bytes)

-- λ> representaciones3 3025

-- [(0,55),(33,44)]

-- (0.00 secs, 173,512 bytes)

-- λ> representaciones4 3025

-- [(0,55),(33,44)]

-- (0.00 secs, 423,424 bytes)

-- λ> length (representaciones2 (10^10))

-- 6

-- (3.38 secs, 2,188,903,544 bytes)

-- λ> length (representaciones3 (10^10))

-- 6

-- (0.10 secs, 62,349,048 bytes)

-- λ> length (representaciones4 (10^10))

-- 6

-- (0.11 secs, 48,052,360 bytes)

-- λ> length (representaciones3 (4*10^12))

-- 7

-- (1.85 secs, 1,222,007,176 bytes)

-- λ> length (representaciones4 (4*10^12))

-- 7

-- (1.79 secs, 953,497,480 bytes)

-- Definición de primosImparesConRepresentacionUnica

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

primosImparesConRepresentacionUnica :: [Integer]

primosImparesConRepresentacionUnica =

[x | x <- tail primes

, length (representaciones4 x) == 1]

-- Definición de primos4nM1

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

primos4nM1 :: [Integer]

primos4nM1 = [x | x <- primes

, x `mod` 4 == 1]

-- Teorema de Navidad de Fermat

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

-- La propiedad es

prop_teoremaDeNavidadDeFermat :: Positive Int -> Bool

prop_teoremaDeNavidadDeFermat (Positive n) =

primosImparesConRepresentacionUnica !! n == primos4nM1 !! n

-- La comprobación es

-- λ> quickCheck prop_teoremaDeNavidadDeFermat

-- +++ OK, passed 100 tests.

Pensamiento

Dijo Dios: brote la nada
Y alzó su mano derecha,
hasta ocultar su mirada.
Y quedó la nada hecha.

Antonio Machado

Árbol binario de divisores

PorJosé A. Alonso 18-diciembre-201925-diciembre-2019

El árbol binario de los divisores de 24 es

2 45

3 15

3 5

Se puede representar por

   N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))

1	N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))

usando el tipo de dato definido por

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

data Arbol = H Int

| N Int Arbol Arbol

deriving (Eq, Show)

Análogamente se obtiene el árbol binario de cualquier número x: se comienza en x y en cada paso se tiene dos hijos (su menor divisor y su cociente) hasta obtener números primos en las hojas.

Definir las funciones

   arbolDivisores      :: Int -> Arbol
   hojasArbolDivisores :: Int -> [Int]

1 2	arbolDivisores :: Int -> Arbol hojasArbolDivisores :: Int -> [Int]

tales que

(arbolDivisores x) es el árbol binario de los divisores de x. Por ejemplo,

     λ> arbolDivisores 90
     N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))
     λ> arbolDivisores 24
     N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3)))
     λ> arbolDivisores 300
     N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5))))

λ> arbolDivisores 90

N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))

λ> arbolDivisores 24

N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3)))

λ> arbolDivisores 300

N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5))))

(hojasArbolDivisores x) es la lista de las hohas del árbol binario de los divisores de x. Por ejemplo

     hojasArbolDivisores 90   ==  [2,3,3,5]
     hojasArbolDivisores 24   ==  [2,2,2,3]
     hojasArbolDivisores 300  ==  [2,2,3,5,5]

hojasArbolDivisores 90 == [2,3,3,5]

hojasArbolDivisores 24 == [2,2,2,3]

hojasArbolDivisores 300 == [2,2,3,5,5]

Soluciones

import Data.Numbers.Primes (isPrime, primeFactors)

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

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

arbolDivisores :: Int -> Arbol
arbolDivisores x
  | y == x    = H x
  | otherwise = N x (H y) (arbolDivisores (x `div` y))
  where y = menorDivisor x

-- (menorDivisor x) es el menor divisor primo de x. Por ejemplo,
--    menorDivisor 45  ==  3
--    menorDivisor 5   ==  5
menorDivisor :: Int -> Int
menorDivisor x =
  head [y | y <- [2..x], x `mod` y == 0]

hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores = hojas . arbolDivisores

-- (hojas a) es la lista de las hojas del árbol a. Por ejemplo,
--    hojas (N 3 (H 4) (N 5 (H 7) (H 2)))  ==  [4,7,2]
hojas :: Arbol -> [Int]
hojas (H x)     = [x]
hojas (N _ i d) = hojas i ++ hojas d

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

arbolDivisores2 :: Int -> Arbol
arbolDivisores2 x
  | y == x    = H x
  | otherwise = N x (H y) (arbolDivisores (x `div` y))
  where (y:_) = primeFactors x

hojasArbolDivisores2 :: Int -> [Int]
hojasArbolDivisores2 = primeFactors

import Data.Numbers.Primes (isPrime, primeFactors)

data Arbol = H Int

| N Int Arbol Arbol

deriving (Eq, Show)

-- 1ª solución

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

arbolDivisores :: Int -> Arbol

arbolDivisores x

| y == x = H x

| otherwise = N x (H y) (arbolDivisores (x `div` y))

where y = menorDivisor x

-- (menorDivisor x) es el menor divisor primo de x. Por ejemplo,

-- menorDivisor 45 == 3

-- menorDivisor 5 == 5

menorDivisor :: Int -> Int

menorDivisor x =

head [y | y <- [2..x], x `mod` y == 0]

hojasArbolDivisores :: Int -> [Int]

hojasArbolDivisores = hojas . arbolDivisores

-- (hojas a) es la lista de las hojas del árbol a. Por ejemplo,

-- hojas (N 3 (H 4) (N 5 (H 7) (H 2))) == [4,7,2]

hojas :: Arbol -> [Int]

hojas (H x) = [x]

hojas (N _ i d) = hojas i ++ hojas d

-- 2ª solución

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

arbolDivisores2 :: Int -> Arbol

arbolDivisores2 x

| y == x = H x

| otherwise = N x (H y) (arbolDivisores (x `div` y))

where (y:_) = primeFactors x

hojasArbolDivisores2 :: Int -> [Int]

hojasArbolDivisores2 = primeFactors

Pensamiento

Cuando el Ser que se es hizo la nada
y reposó que bien lo merecía,
ya tuvo el día noche, y compañía
tuvo el amante en la ausencia de la amada.

Antonio Machado

Intersección de listas infinitas crecientes

PorJosé A. Alonso 17-diciembre-201924-diciembre-2019

Definir la función

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

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

tal que (interseccion xss) es la intersección de la lista no vacía de listas infinitas crecientes xss; es decir, la lista de los elementos que pertenecen a todas las listas de xss. Por ejemplo,

   λ> take 10 (interseccion [[2,4..],[3,6..],[5,10..]])
   [30,60,90,120,150,180,210,240,270,300]
   λ> take 10 (interseccion [[2,5..],[3,5..],[5,7..]])
   [5,11,17,23,29,35,41,47,53,59]

λ> take 10 (interseccion [[2,4..],[3,6..],[5,10..]])

[30,60,90,120,150,180,210,240,270,300]

λ> take 10 (interseccion [[2,5..],[3,5..],[5,7..]])

[5,11,17,23,29,35,41,47,53,59]

Soluciones

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

interseccion :: Ord a => [[a]] -> [a]
interseccion [xs]        = xs
interseccion (xs:ys:zss) = interseccionDos xs (interseccion (ys:zss))

interseccionDos :: Ord a => [a] -> [a] -> [a]
interseccionDos (x:xs) (y:ys)
  | x == y    = x : interseccionDos xs ys
  | x < y     = interseccionDos (dropWhile (<y) xs) (y:ys)
  | otherwise = interseccionDos (x:xs) (dropWhile (<x) ys)  

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

interseccion2 :: Ord a => [[a]] -> [a]
interseccion2 = foldl1 interseccionDos

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

interseccion3 :: Ord a => [[a]] -> [a]
interseccion3 (xs:xss) =
  [x | x <- xs, all (x `pertenece`) xss]
 
pertenece :: Ord a => a -> [a] -> Bool
pertenece x xs = x == head (dropWhile (<x) xs)

-- 1ª solución

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

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

interseccion [xs] = xs

interseccion (xs:ys:zss) = interseccionDos xs (interseccion (ys:zss))

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

interseccionDos (x:xs) (y:ys)

| x == y = x : interseccionDos xs ys

| x < y = interseccionDos (dropWhile (<y) xs) (y:ys)

| otherwise = interseccionDos (x:xs) (dropWhile (<x) ys)

-- 2ª solución

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

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

interseccion2 = foldl1 interseccionDos

-- 3ª solución

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

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

interseccion3 (xs:xss) =

[x | x <- xs, all (x `pertenece`) xss]

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

pertenece x xs = x == head (dropWhile (<x) xs)

Pensamiento

Dios no es el creador del mundo (según Martín), sino el creador de la nada.

Antonio Machado

Cálculo de pi usando la fórmula de Vieta

PorJosé A. Alonso 16-diciembre-201923-diciembre-2019

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

Pensamiento

El tiempo que la barba me platea,
cavó mis ojos y agrandó mi frente,
va siendo en mi recuerdo transparente,
y mientras más al fondo, más clarea.

Antonio Machado

Evaluación de árboles de expresiones aritméticas

PorJosé A. Alonso 12-diciembre-201919-diciembre-2019

Las expresiones aritméticas se pueden representar como árboles con números en las hojas y operaciones en los nodos. Por ejemplo, la expresión «9-2*4» se puede representar por el árbol

/ \

9 *

/ \

2 4

Definiendo el tipo de dato Arbol por

   data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

1	data Arbol = H Int \| N (Int -> Int -> Int) Arbol Arbol

la representación del árbol anterior es

   N (-) (H 9) (N (*) (H 2) (H 4))

1	N (-) (H 9) (N (*) (H 2) (H 4))

Definir la función

   valor :: Arbol -> Int

1	valor :: Arbol -> Int

tal que (valor a) es el valor de la expresión aritmética correspondiente al árbol a. Por ejemplo,

   valor (N (-) (H 9) (N (*) (H 2) (H 4)))    ==  1
   valor (N (+) (H 9) (N (*) (H 2) (H 4)))    ==  17
   valor (N (+) (H 9) (N (div) (H 4) (H 2)))  ==  11
   valor (N (+) (H 9) (N (max) (H 4) (H 2)))  ==  13

valor (N (-) (H 9) (N (*) (H 2) (H 4))) == 1

valor (N (+) (H 9) (N (*) (H 2) (H 4))) == 17

valor (N (+) (H 9) (N (div) (H 4) (H 2))) == 11

valor (N (+) (H 9) (N (max) (H 4) (H 2))) == 13

Soluciones

data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

valor :: Arbol -> Int
valor (H x)     = x
valor (N f i d) = f (valor i) (valor d)

data Arbol = H Int | N (Int -> Int -> Int) Arbol Arbol

valor :: Arbol -> Int

valor (H x) = x

valor (N f i d) = f (valor i) (valor d)

Pensamiento

En cierto modo, las matemáticas no son el arte de responder preguntas matemáticas, es el arte de hacer las preguntas correctas, las preguntas que te dan una idea, las que te guían en direcciones interesantes, las que se conectan con muchas otras preguntas interesantes, las que tienen hermosas respuestas. ~ Gregory Chaitin

Primos o cuadrados de primos

PorJosé A. Alonso 6-diciembre-201917-diciembre-2019

Definir la constante

   primosOcuadradosDePrimos :: [Integer]

1	primosOcuadradosDePrimos :: [Integer]

cuyos elementos son los número primos o cuadrados de primos. Por ejemplo,

   λ> take 20 primosOcuadradosDePrimos
   [2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53]
   λ> primosOcuadradosDePrimos !! (10^6)
   15476729

λ> take 20 primosOcuadradosDePrimos

[2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53]

λ> primosOcuadradosDePrimos !! (10^6)

15476729

Comprobar con QuickCheck que las lista primosOcuadradosDePrimos y unifactorizables (definida en el ejercicio anterior) son iguales.

Soluciones

import Test.QuickCheck
import Data.Numbers.Primes (primeFactors, primes)

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

primosOcuadradosDePrimos :: [Integer]
primosOcuadradosDePrimos =
  filter esPrimoOcuadradoDePrimo [2..]

esPrimoOcuadradoDePrimo :: Integer -> Bool
esPrimoOcuadradoDePrimo n = aux xs
  where xs = primeFactors n
        aux [_]   = True
        aux [x,y] = x == y
        aux _     = False

-- 2ª solución
-- ===========
  
primosOcuadradosDePrimos2 :: [Integer]
primosOcuadradosDePrimos2 = mezcla primes (map (^2) primes)

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y     = x : mezcla xs (y:ys)
                     | otherwise = y : mezcla (x:xs) ys

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

--    λ> primosOcuadradosDePrimos !! (2*10^4)
--    223589
--    (3.08 secs, 9,829,725,096 bytes)
--    λ> primosOcuadradosDePrimos2 !! (2*10^4)
--    223589
--    (0.04 secs, 73,751,888 bytes)
--
--    λ> primosOcuadradosDePrimos2 !! (5*10^5)
--    7362497
--    (1.29 secs, 3,192,803,040 bytes)

-- Propiedad de equivalencia
-- =========================

-- La propiedad es
prop_equivalencia :: Int -> Property
prop_equivalencia n =
  n >= 0 ==> primosOcuadradosDePrimos2 !! n == unifactorizables !! n

--  unifactorizables es la lísta de los números enteros mayores que 1
--  que se pueden escribir sólo de una forma única como producto de
--  enteros distintos mayores que uno. Por ejemplo,
--     λ> take 20 unifactorizables
--     [2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53]
--     λ> unifactorizables !! 300
--     1873
unifactorizables :: [Integer]
unifactorizables =
  [n | n <- [2..]
     , length (sublistasConProducto n [2..n]) == 1]

-- (sublistasConProducto n xs) es la lista de las sublistas de la
-- lista ordenada estrictamente creciente xs (cuyos elementos son
-- enteros mayores que 1) cuyo producto es el número entero n (con n
-- mayor que 1). Por ejemplo,  
--    λ> sublistasConProducto 72 [2,3,4,5,6,7,9,10,16]
--    [[2,4,9],[3,4,6]]
--    λ> sublistasConProducto 720 [2,3,4,5,6,7,9,10,16]
--    [[2,3,4,5,6],[2,4,9,10],[3,4,6,10],[5,9,16]]
--    λ> sublistasConProducto 2 [4,7]
--    []
sublistasConProducto :: Integer -> [Integer] -> [[Integer]]
sublistasConProducto _ [] = []
sublistasConProducto n (x:xs)
  | x > n     = []
  | x == n    = [[x]]
  | r == 0    = map (x:) (sublistasConProducto q xs)
                ++ sublistasConProducto n xs
  | otherwise = sublistasConProducto n xs
  where (q,r) = quotRem n x

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

import Test.QuickCheck

import Data.Numbers.Primes (primeFactors, primes)

-- 1ª solución

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

primosOcuadradosDePrimos :: [Integer]

primosOcuadradosDePrimos =

filter esPrimoOcuadradoDePrimo [2..]

esPrimoOcuadradoDePrimo :: Integer -> Bool

esPrimoOcuadradoDePrimo n = aux xs

where xs = primeFactors n

aux [_] = True

aux [x,y] = x == y

aux _ = False

-- 2ª solución

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

primosOcuadradosDePrimos2 :: [Integer]

primosOcuadradosDePrimos2 = mezcla primes (map (^2) primes)

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

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

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

-- Comparación de eficiencia

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

-- λ> primosOcuadradosDePrimos !! (2*10^4)

-- 223589

-- (3.08 secs, 9,829,725,096 bytes)

-- λ> primosOcuadradosDePrimos2 !! (2*10^4)

-- 223589

-- (0.04 secs, 73,751,888 bytes)

-- λ> primosOcuadradosDePrimos2 !! (5*10^5)

-- 7362497

-- (1.29 secs, 3,192,803,040 bytes)

-- Propiedad de equivalencia

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

-- La propiedad es

prop_equivalencia :: Int -> Property

prop_equivalencia n =

n >= 0 ==> primosOcuadradosDePrimos2 !! n == unifactorizables !! n

-- unifactorizables es la lísta de los números enteros mayores que 1

-- que se pueden escribir sólo de una forma única como producto de

-- enteros distintos mayores que uno. Por ejemplo,

-- λ> take 20 unifactorizables

-- [2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53]

-- λ> unifactorizables !! 300

-- 1873

unifactorizables :: [Integer]

unifactorizables =

[n | n <- [2..]

, length (sublistasConProducto n [2..n]) == 1]

-- (sublistasConProducto n xs) es la lista de las sublistas de la

-- lista ordenada estrictamente creciente xs (cuyos elementos son

-- enteros mayores que 1) cuyo producto es el número entero n (con n

-- mayor que 1). Por ejemplo,

-- λ> sublistasConProducto 72 [2,3,4,5,6,7,9,10,16]

-- [[2,4,9],[3,4,6]]

-- λ> sublistasConProducto 720 [2,3,4,5,6,7,9,10,16]

-- [[2,3,4,5,6],[2,4,9,10],[3,4,6,10],[5,9,16]]

-- λ> sublistasConProducto 2 [4,7]

-- []

sublistasConProducto :: Integer -> [Integer] -> [[Integer]]

sublistasConProducto _ [] = []

sublistasConProducto n (x:xs)

| x > n = []

| x == n = [[x]]

| r == 0 = map (x:) (sublistasConProducto q xs)

++ sublistasConProducto n xs

| otherwise = sublistasConProducto n xs

where (q,r) = quotRem n x

-- La comprobación es

-- λ> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

Pensamiento

Despacito y buena letra: el hacer las cosas bien importa más que el hacerlas.

Antonio Machado

Sublistas con producto dado

PorJosé A. Alonso 5-diciembre-201917-diciembre-2019

Definir las funciones

   sublistasConProducto :: Integer -> [Integer] -> [[Integer]]
   unifactorizables :: [Integer]

1 2	sublistasConProducto :: Integer -> [Integer] -> [[Integer]] unifactorizables :: [Integer]

tales que

(sublistasConProducto n xs) es la lista de las sublistas de la lista ordenada estrictamente creciente xs (cuyos elementos son enteros mayores que 1) cuyo producto es el número entero n (con n mayor que 1). Por ejemplo,

     λ> sublistasConProducto 72 [2,3,4,5,6,7,9,10,16]
     [[2,4,9],[3,4,6]]
     λ> sublistasConProducto 720 [2,3,4,5,6,7,9,10,16]
     [[2,3,4,5,6],[2,4,9,10],[3,4,6,10],[5,9,16]]
     λ> sublistasConProducto 2 [4,7]
     []
     λ> length (sublistasConProducto 1234567 [1..1234567])
     4

λ> sublistasConProducto 72 [2,3,4,5,6,7,9,10,16]

[[2,4,9],[3,4,6]]

λ> sublistasConProducto 720 [2,3,4,5,6,7,9,10,16]

[[2,3,4,5,6],[2,4,9,10],[3,4,6,10],[5,9,16]]

λ> sublistasConProducto 2 [4,7]

[]

λ> length (sublistasConProducto 1234567 [1..1234567])

unifactorizables es la lísta de los números enteros mayores que 1 que se pueden escribir sólo de una forma única como producto de enteros distintos mayores que uno. Por ejemplo,

     λ> take 20 unifactorizables
     [2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53]
     λ> unifactorizables !! 300
     1873

λ> take 20 unifactorizables

[2,3,4,5,7,9,11,13,17,19,23,25,29,31,37,41,43,47,49,53]

λ> unifactorizables !! 300

1873

Soluciones

import Test.QuickCheck
import Data.List (nub, sort, subsequences)

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

sublistasConProducto :: Integer -> [Integer] -> [[Integer]]
sublistasConProducto n xs =
  [ys | ys <- subsequences xs
      , product ys == n]

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

sublistasConProducto2 :: Integer -> [Integer] -> [[Integer]]
sublistasConProducto2 _ [] = []
sublistasConProducto2 n (x:xs)
  | x > n     = []
  | x == n    = [[x]]
  | r == 0    = map (x:) (sublistasConProducto2 q xs)
                ++ sublistasConProducto2 n xs
  | otherwise = sublistasConProducto2 n xs
  where (q,r) = quotRem n x

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

-- La propiedad es
prop_sublistasConProducto :: Integer -> [Integer] -> Bool
prop_sublistasConProducto n xs =
  sort (sublistasConProducto n' xs') == sublistasConProducto2 n' xs'
  where n'  = 2 + abs n
        xs' = (nub . sort . map ((+2) . abs)) xs

-- La comprobación es
--    λ> quickCheckWith (stdArgs {maxSize=30}) prop_sublistasConProducto
--    +++ OK, passed 100 tests.

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

--    λ> sublistasConProducto 15 [1..23]
--    [[3,5],[1,3,5],[15],[1,15]]
--    (3.44 secs, 7,885,411,472 bytes)
--    λ> sublistasConProducto2 15 [1..23]
--    [[1,3,5],[1,15],[3,5],[15]]
--    (0.01 secs, 135,056 bytes)
--
--    λ> length (sublistasConProducto2 1234567 [1..1234567])
--    4
--    (1.49 secs, 1,054,380,480 bytes)

-- Definición de unifactorizables
-- ==============================

unifactorizables :: [Integer]
unifactorizables =
  [n | n <- [2..]
     , length (sublistasConProducto2 n [2..n]) == 1]

import Test.QuickCheck

import Data.List (nub, sort, subsequences)

-- 1ª solución

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

sublistasConProducto :: Integer -> [Integer] -> [[Integer]]

sublistasConProducto n xs =

[ys | ys <- subsequences xs

, product ys == n]

-- 2ª solución

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

sublistasConProducto2 :: Integer -> [Integer] -> [[Integer]]

sublistasConProducto2 _ [] = []

sublistasConProducto2 n (x:xs)

| x > n = []

| x == n = [[x]]

| r == 0 = map (x:) (sublistasConProducto2 q xs)

++ sublistasConProducto2 n xs

| otherwise = sublistasConProducto2 n xs

where (q,r) = quotRem n x

-- Comprobación de equivalencia

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

-- La propiedad es

prop_sublistasConProducto :: Integer -> [Integer] -> Bool

prop_sublistasConProducto n xs =

sort (sublistasConProducto n' xs') == sublistasConProducto2 n' xs'

where n' = 2 + abs n

xs' = (nub . sort . map ((+2) . abs)) xs

-- La comprobación es

-- λ> quickCheckWith (stdArgs {maxSize=30}) prop_sublistasConProducto

-- +++ OK, passed 100 tests.

-- Comparación de eficiencia

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

-- λ> sublistasConProducto 15 [1..23]

-- [[3,5],[1,3,5],[15],[1,15]]

-- (3.44 secs, 7,885,411,472 bytes)

-- λ> sublistasConProducto2 15 [1..23]

-- [[1,3,5],[1,15],[3,5],[15]]

-- (0.01 secs, 135,056 bytes)

-- λ> length (sublistasConProducto2 1234567 [1..1234567])

-- 4

-- (1.49 secs, 1,054,380,480 bytes)

-- Definición de unifactorizables

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

unifactorizables :: [Integer]

unifactorizables =

[n | n <- [2..]

, length (sublistasConProducto2 n [2..n]) == 1]

Pensamiento

Y en el encinar,
¡luna redonda y beata,
siempre conmigo a la par!
Cerca de Úbeda la grande,
cuyos cerros nadie verá,
me iba siguiendo la luna
sobre el olivar.
Una luna jadeante,
siempre conmigo a la par.

Antonio Machado

Menor divisible por todos

PorJosé A. Alonso 28-noviembre-20195-diciembre-2019

Definir la función

   menorDivisible :: Integer -> Integer -> Integer

1	menorDivisible :: Integer -> Integer -> Integer

tal que (menorDivisible a b) es el menor número divisible por todos los números desde a hasta b, ambos inclusive. Por ejemplo,

   menorDivisible 1 10                        ==  2520
   length (show (menorDivisible 1 (3*10^5)))  ==  130141

1 2	menorDivisible 1 10 == 2520 length (show (menorDivisible 1 (3*10^5))) == 130141

Nota: Este ejercicio está basado en el problema 5 del Proyecto Euler

Soluciones

import Data.List (foldl')

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

menorDivisible :: Integer -> Integer -> Integer
menorDivisible a b =
  head [x | x <- [b..]
          , and [x `mod` y == 0 | y <- [a..b]]]

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

menorDivisible2 :: Integer -> Integer -> Integer
menorDivisible2 a b  
  | a == b    = a
  | otherwise = lcm a (menorDivisible (a+1) b)

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

menorDivisible3 :: Integer -> Integer -> Integer
menorDivisible3 a b = foldl lcm 1 [a..b] 

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

menorDivisible4 :: Integer -> Integer -> Integer
menorDivisible4 a b = foldl1 lcm [a..b] 

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

menorDivisible5 :: Integer -> Integer -> Integer
menorDivisible5 a b = foldl' lcm 1 [a..b] 

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

menorDivisible6 :: Integer -> Integer -> Integer
menorDivisible6 a b = foldr1 lcm [a..b] 

-- 7ª solución
-- ===========

menorDivisible7 :: Integer -> Integer -> Integer
menorDivisible7 a = foldr1 lcm . enumFromTo a

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

--   λ> menorDivisible 1 17
--   12252240
--   (18.63 secs, 15,789,475,488 bytes)
--   λ> menorDivisible2 1 17
--   12252240
--   (13.29 secs, 11,868,764,272 bytes)
--   λ> menorDivisible3 1 17
--   12252240
--   (0.00 secs, 114,688 bytes)
--   λ> menorDivisible4 1 17
--   12252240
--   (0.01 secs, 114,752 bytes)
--   λ> menorDivisible5 1 17
--   12252240
--   (0.01 secs, 110,640 bytes)
--   λ> menorDivisible6 1 17
--   12252240
--   (0.01 secs, 114,752 bytes)
--   λ> menorDivisible7 1 17
--   12252240
--   (0.00 secs, 110,912 bytes)
--   
--   λ> length (show (menorDivisible3 1 (10^5)))
--   43452
--   (1.54 secs, 2,021,887,000 bytes)
--   λ> length (show (menorDivisible4 1 (10^5)))
--   43452
--   (1.47 secs, 2,021,886,616 bytes)
--   λ> length (show (menorDivisible5 1 (10^5)))
--   43452
--   (0.65 secs, 2,009,595,568 bytes)
--   λ> length (show (menorDivisible6 1 (10^5)))
--   43452
--   (0.30 secs, 172,986,840 bytes)
--   λ> length (show (menorDivisible7 1 (10^5)))
--   43452
--   (0.30 secs, 172,986,920 bytes)
--   
--   λ> length (show (menorDivisible5 1 (2*10^5)))
--   86871
--   (2.47 secs, 7,989,147,304 bytes)
--   λ> length (show (menorDivisible6 1 (2*10^5)))
--   86871
--   (0.89 secs, 533,876,496 bytes)
--   λ> length (show (menorDivisible7 1 (2*10^5)))
--   86871
--   (0.88 secs, 533,875,608 bytes)

import Data.List (foldl')

-- 1ª solución

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

menorDivisible :: Integer -> Integer -> Integer

menorDivisible a b =

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

, and [x `mod` y == 0 | y <- [a..b]]]

-- 2ª solución

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

menorDivisible2 :: Integer -> Integer -> Integer

menorDivisible2 a b

| a == b = a

| otherwise = lcm a (menorDivisible (a+1) b)

-- 3ª solución

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

menorDivisible3 :: Integer -> Integer -> Integer

menorDivisible3 a b = foldl lcm 1 [a..b]

-- 4ª solución

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

menorDivisible4 :: Integer -> Integer -> Integer

menorDivisible4 a b = foldl1 lcm [a..b]

-- 5ª solución

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

menorDivisible5 :: Integer -> Integer -> Integer

menorDivisible5 a b = foldl' lcm 1 [a..b]

-- 6ª solución

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

menorDivisible6 :: Integer -> Integer -> Integer

menorDivisible6 a b = foldr1 lcm [a..b]

-- 7ª solución

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

menorDivisible7 :: Integer -> Integer -> Integer

menorDivisible7 a = foldr1 lcm . enumFromTo a

-- Comparación de eficiencia

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

-- λ> menorDivisible 1 17

-- 12252240

-- (18.63 secs, 15,789,475,488 bytes)

-- λ> menorDivisible2 1 17

-- 12252240

-- (13.29 secs, 11,868,764,272 bytes)

-- λ> menorDivisible3 1 17

-- 12252240

-- (0.00 secs, 114,688 bytes)

-- λ> menorDivisible4 1 17

-- 12252240

-- (0.01 secs, 114,752 bytes)

-- λ> menorDivisible5 1 17

-- 12252240

-- (0.01 secs, 110,640 bytes)

-- λ> menorDivisible6 1 17

-- 12252240

-- (0.01 secs, 114,752 bytes)

-- λ> menorDivisible7 1 17

-- 12252240

-- (0.00 secs, 110,912 bytes)

-- λ> length (show (menorDivisible3 1 (10^5)))

-- 43452

-- (1.54 secs, 2,021,887,000 bytes)

-- λ> length (show (menorDivisible4 1 (10^5)))

-- 43452

-- (1.47 secs, 2,021,886,616 bytes)

-- λ> length (show (menorDivisible5 1 (10^5)))

-- 43452

-- (0.65 secs, 2,009,595,568 bytes)

-- λ> length (show (menorDivisible6 1 (10^5)))

-- 43452

-- (0.30 secs, 172,986,840 bytes)

-- λ> length (show (menorDivisible7 1 (10^5)))

-- 43452

-- (0.30 secs, 172,986,920 bytes)

-- λ> length (show (menorDivisible5 1 (2*10^5)))

-- 86871

-- (2.47 secs, 7,989,147,304 bytes)

-- λ> length (show (menorDivisible6 1 (2*10^5)))

-- 86871

-- (0.89 secs, 533,876,496 bytes)

-- λ> length (show (menorDivisible7 1 (2*10^5)))

-- 86871

-- (0.88 secs, 533,875,608 bytes)

Pensamiento

Será el peor de los malos
bribón que olvide
su vocación de diablo.

Antonio Machado

Mayor divisor primo

PorJosé A. Alonso 26-noviembre-20193-diciembre-2019

Los divisores primos de 13195 son 5, 7, 13 y 29. Por tanto, el mayor divisor primo de 13195 es 29.

Definir la función

   mayorDivisorPrimo :: Integer -> Integer

1	mayorDivisorPrimo :: Integer -> Integer

tal que (mayorDivisorPrimo n) es el mayor divisor primo de n. Por ejemplo,

   mayorDivisorPrimo 13195            ==  29
   mayorDivisorPrimo 152416333181401  ==  12345701

1 2	mayorDivisorPrimo 13195 == 29 mayorDivisorPrimo 152416333181401 == 12345701

Nota: Este ejercicio está basado en el problema 3 del Proyecto Euler

Soluciones

import Data.Numbers.Primes (primeFactors)

-- 1ª solución  (sin librerías auxiliares)
-- =======================================

mayorDivisorPrimo :: Integer -> Integer
mayorDivisorPrimo = last . divisoresPrimos 

-- (divisoresPrimos n) es la lista de los divisores primos de n. Por
-- ejemplo, 
--    divisoresPrimos 13195  ==  [5,7,13,29]
divisoresPrimos :: Integer -> [Integer]
divisoresPrimos 0 = []
divisoresPrimos 1 = []
divisoresPrimos n = m : divisoresPrimos (n `div` m)
  where m = menorDivisorPrimo n 

-- (menorDivisorPrimo n) es el menor divisor primo de n. Por ejemplo, 
--    menorDivisorPrimo 24  ==  2
--    menorDivisorPrimo 25  ==  5
--    menorDivisorPrimo 29  ==  29
menorDivisorPrimo :: Integer -> Integer
menorDivisorPrimo x =
  head [y | y <- 2 : [3,5..(ceiling . sqrt . fromIntegral) x] ++ [x]
          , x `mod` y == 0]

-- 2ª solución (con la librería Data.Numbers.Primes)
-- =================================================

mayorDivisorPrimo2 :: Integer -> Integer
mayorDivisorPrimo2 = last . primeFactors

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

--   λ> mayorDivisorPrimo 152416333181401
--   12345701
--   (1.96 secs, 1,630,201,856 bytes)
--   λ> mayorDivisorPrimo2 152416333181401
--   12345701
--   (2.01 secs, 5,445,284,432 bytes)

import Data.Numbers.Primes (primeFactors)

-- 1ª solución (sin librerías auxiliares)

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

mayorDivisorPrimo :: Integer -> Integer

mayorDivisorPrimo = last . divisoresPrimos

-- (divisoresPrimos n) es la lista de los divisores primos de n. Por

-- ejemplo,

-- divisoresPrimos 13195 == [5,7,13,29]

divisoresPrimos :: Integer -> [Integer]

divisoresPrimos 0 = []

divisoresPrimos 1 = []

divisoresPrimos n = m : divisoresPrimos (n `div` m)

where m = menorDivisorPrimo n

-- (menorDivisorPrimo n) es el menor divisor primo de n. Por ejemplo,

-- menorDivisorPrimo 24 == 2

-- menorDivisorPrimo 25 == 5

-- menorDivisorPrimo 29 == 29

menorDivisorPrimo :: Integer -> Integer

menorDivisorPrimo x =

head [y | y <- 2 : [3,5..(ceiling . sqrt . fromIntegral) x] ++ [x]

, x `mod` y == 0]

-- 2ª solución (con la librería Data.Numbers.Primes)

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

mayorDivisorPrimo2 :: Integer -> Integer

mayorDivisorPrimo2 = last . primeFactors

-- Comparación de eficiencia

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

-- λ> mayorDivisorPrimo 152416333181401

-- 12345701

-- (1.96 secs, 1,630,201,856 bytes)

-- λ> mayorDivisorPrimo2 152416333181401

-- 12345701

-- (2.01 secs, 5,445,284,432 bytes)

Pensamiento

«Un programa de ordenador es una demostración.» ~ Igor Rivin

Números triangulares

PorJosé A. Alonso 25-noviembre-201925-marzo-2022

La sucesión de los números triangulares se obtiene sumando los números naturales.

   *     *      *        *         *   
        * *    * *      * *       * *  
              * * *    * * *     * * * 
                      * * * *   * * * *
                               * * * * * 
   1     3      6        10        15

* * * * *

* * * * * * * *

* * * * * * * * *

* * * * * * * *

* * * * *

1 3 6 10 15

Así, los 5 primeros números triangulares son

    1 = 1
    3 = 1+2
    6 = 1+2+3
   10 = 1+2+3+4
   15 = 1+2+3+4+5

1 = 1

3 = 1+2

6 = 1+2+3

10 = 1+2+3+4

15 = 1+2+3+4+5

Definir la función

   triangulares :: [Integer]

1	triangulares :: [Integer]

tal que triangulares es la lista de los números triangulares. Por ejemplo,

   take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]
   maximum (take (5*10^6) triangulares4)  ==  12500002500000

1 2	take 10 triangulares == [1,3,6,10,15,21,28,36,45,55] maximum (take (5*10^6) triangulares4) == 12500002500000

Comprobar con QuickCheck que entre dos números triangulares consecutivos siempre hay un número primo.

Soluciones

import Test.QuickCheck (Property, (==>), quickCheck)
import Data.Numbers.Primes (primes)

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

triangulares :: [Integer]
triangulares = [sum [1..n] | n <- [1..]]

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

triangulares2 :: [Integer]
triangulares2 = map triangular [1..]

-- (triangular n) es el n-ésimo número triangular. Por ejemplo, 
--    triangular 5  ==  15
triangular :: Integer -> Integer
triangular 1 = 1
triangular n = n + triangular (n-1)

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

triangulares3 :: [Integer]
triangulares3 = 1 : [x+y | (x,y) <- zip [2..] triangulares]

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

triangulares4 :: [Integer]
triangulares4 = scanl1 (+) [1..]

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

triangulares5 :: [Integer]
triangulares5 = [(n*(n+1)) `div` 2 | n <- [1..]]

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

--    λ> maximum (take (10^4) triangulares)
--    50005000
--    (2.10 secs, 8,057,774,104 bytes)
--    λ> maximum (take (10^4) triangulares2)
--    50005000
--    (18.89 secs, 12,142,690,784 bytes)
--    λ> maximum (take (10^4) triangulares3)
--    50005000
--    (0.01 secs, 4,600,976 bytes)
--    λ> maximum (take (10^4) triangulares4)
--    50005000
--    (0.01 secs, 3,643,192 bytes)
--    λ> maximum (take (10^4) triangulares5)
--    50005000
--    (0.02 secs, 5,161,464 bytes)
--    
--    λ> maximum (take (3*10^4) triangulares3)
--    450015000
--    (26.06 secs, 72,546,027,136 bytes)
--    λ> maximum (take (3*10^4) triangulares4)
--    450015000
--    (0.02 secs, 10,711,600 bytes)
--    λ> maximum (take (3*10^4) triangulares5)
--    450015000
--    (0.03 secs, 15,272,320 bytes)
--    
--    λ> maximum (take (5*10^6) triangulares4)
--    12500002500000
--    (1.67 secs, 1,772,410,336 bytes)
--    λ> maximum (take (5*10^6) triangulares5)
--    12500002500000
--    (4.09 secs, 2,532,407,720 bytes)

-- La propiedad es
prop_triangulares :: Int -> Property
prop_triangulares n =
  n >= 0 ==> siguientePrimo x < y
  where (x:y:_) = drop n triangulares4

-- (siguientePrimo n) es el menor primo mayor o igual que n. Por
-- ejemplo, 
--    siguientePrimo 14  ==  17
--    siguientePrimo 17  ==  17
siguientePrimo :: Integer -> Integer
siguientePrimo n = head (dropWhile (< n) primes)

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

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

import Data.Numbers.Primes (primes)

-- 1ª solución

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

triangulares :: [Integer]

triangulares = [sum [1..n] | n <- [1..]]

-- 2ª solución

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

triangulares2 :: [Integer]

triangulares2 = map triangular [1..]

-- (triangular n) es el n-ésimo número triangular. Por ejemplo,

-- triangular 5 == 15

triangular :: Integer -> Integer

triangular 1 = 1

triangular n = n + triangular (n-1)

-- 3ª solución

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

triangulares3 :: [Integer]

triangulares3 = 1 : [x+y | (x,y) <- zip [2..] triangulares]

-- 4ª solución

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

triangulares4 :: [Integer]

triangulares4 = scanl1 (+) [1..]

-- 5ª solución

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

triangulares5 :: [Integer]

triangulares5 = [(n*(n+1)) `div` 2 | n <- [1..]]

-- Comparación de eficiencia

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

-- λ> maximum (take (10^4) triangulares)

-- 50005000

-- (2.10 secs, 8,057,774,104 bytes)

-- λ> maximum (take (10^4) triangulares2)

-- 50005000

-- (18.89 secs, 12,142,690,784 bytes)

-- λ> maximum (take (10^4) triangulares3)

-- 50005000

-- (0.01 secs, 4,600,976 bytes)

-- λ> maximum (take (10^4) triangulares4)

-- 50005000

-- (0.01 secs, 3,643,192 bytes)

-- λ> maximum (take (10^4) triangulares5)

-- 50005000

-- (0.02 secs, 5,161,464 bytes)

-- λ> maximum (take (3*10^4) triangulares3)

-- 450015000

-- (26.06 secs, 72,546,027,136 bytes)

-- λ> maximum (take (3*10^4) triangulares4)

-- 450015000

-- (0.02 secs, 10,711,600 bytes)

-- λ> maximum (take (3*10^4) triangulares5)

-- 450015000

-- (0.03 secs, 15,272,320 bytes)

-- λ> maximum (take (5*10^6) triangulares4)

-- 12500002500000

-- (1.67 secs, 1,772,410,336 bytes)

-- λ> maximum (take (5*10^6) triangulares5)

-- 12500002500000

-- (4.09 secs, 2,532,407,720 bytes)

-- La propiedad es

prop_triangulares :: Int -> Property

prop_triangulares n =

n >= 0 ==> siguientePrimo x < y

where (x:y:_) = drop n triangulares4

-- (siguientePrimo n) es el menor primo mayor o igual que n. Por

-- ejemplo,

-- siguientePrimo 14 == 17

-- siguientePrimo 17 == 17

siguientePrimo :: Integer -> Integer

siguientePrimo n = head (dropWhile (< n) primes)

-- La comprobación es

-- λ> quickCheck prop_triangulares

-- +++ OK, passed 100 tests.

Pensamiento

Autores, la escena acaba
con un dogma de teatro:
En el principio era la máscara.

Antonio Machado

Factorización prima

PorJosé A. Alonso 21-noviembre-201926-marzo-2022

La descomposición prima de 600 es

   600 = 2³ * 3 * 5²

1	600 = 2³ * 3 * 5²

Definir la función

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

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

tal que (factorizacion x) ses la lista de las bases y exponentes de la descomposición prima de x. Por ejemplo,

   factorizacion 600  ==  [(2,3),(3,1),(5,2)]
   length (factorizacion (product [1..3*10^4]))  ==  3245

1 2	factorizacion 600 == [(2,3),(3,1),(5,2)] length (factorizacion (product [1..3*10^4])) == 3245

Soluciones

import Data.List (genericLength, group, inits, nub, sort, subsequences)
import Data.Numbers.Primes (primes, primeFactors)

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

factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
  [(x,nOcurrencias x xs) | x <- elementos xs]
  where xs = factoresPrimos n

-- (factores primos n) es la lista de los factores primos de n. Por
-- ejemplo, 
--   factoresPrimos 600  ==  [2,2,2,3,5,5]
factoresPrimos :: Integer -> [Integer]
factoresPrimos 1 = []
factoresPrimos n = x : factoresPrimos (n `div` x)
  where x = menorFactor n

-- (menorFactor n) es el menor factor primo de n. Por ejemplo,
--   menorFactor 10  ==  2
--   menorFactor 11  ==  11
menorFactor :: Integer -> Integer
menorFactor n = head [x | x <- [2..n], n `mod` x == 0]

-- (elementos xs) es la lista de los elementos, sin repeticiones, de
-- xs. Por ejemplo,
--   elementos [3,2,3,5,2]  ==  [3,2,5]
elementos :: Eq a => [a] -> [a]
elementos [] = []
elementos (x:xs) = x : elementos (filter (/=x) xs)

-- (nOcurrencias x ys) es el número de ocurrencias de x en ys. Por
-- ejemplo, 
--   nOcurrencias 'a' "Salamanca"  ==  4
nOcurrencias :: Eq a => a -> [a] -> Integer
nOcurrencias x ys = genericLength (filter (==x) ys) 

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

factorizacion2 :: Integer -> [(Integer,Integer)]
factorizacion2 n =
  [(head xs,genericLength xs) | xs <- group (primeFactors n)]

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

factorizacion3 :: Integer -> [(Integer,Integer)]
factorizacion3 = map primeroYlongitud
               . group
               . primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs
-- y la longitud de xs. Por ejemplo,
--    primeroYlongitud [3,2,5,7] == (3,4)
primeroYlongitud :: [a] -> (a,Integer)
primeroYlongitud (x:xs) =
  (x, 1 + genericLength xs)

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

--   λ> length (factorizacion (product [1..10^4]))
--   1229
--   (4.84 secs, 2,583,331,768 bytes)
--   λ> length (factorizacion2 (product [1..10^4]))
--   1229
--   (0.24 secs, 452,543,360 bytes)
--   λ> length (factorizacion3 (product [1..10^4]))
--   1229
--   (0.23 secs, 452,433,504 bytes)
--   
--   λ> length (factorizacion (product (take (2*10^3) primes)))
--   2000
--   (6.58 secs, 3,415,098,552 bytes)
--   λ> length (factorizacion2 (product (take (2*10^3) primes)))
--   2000
--   (0.02 secs, 23,060,512 bytes)
--   λ> length (factorizacion3 (product (take (2*10^3) primes)))
--   2000
--   (0.02 secs, 22,882,080 bytes)

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

import Data.Numbers.Primes (primes, primeFactors)

-- 1ª solución

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

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

factorizacion n =

[(x,nOcurrencias x xs) | x <- elementos xs]

where xs = factoresPrimos n

-- (factores primos n) es la lista de los factores primos de n. Por

-- ejemplo,

-- factoresPrimos 600 == [2,2,2,3,5,5]

factoresPrimos :: Integer -> [Integer]

factoresPrimos 1 = []

factoresPrimos n = x : factoresPrimos (n `div` x)

where x = menorFactor n

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

-- menorFactor 10 == 2

-- menorFactor 11 == 11

menorFactor :: Integer -> Integer

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

-- (elementos xs) es la lista de los elementos, sin repeticiones, de

-- xs. Por ejemplo,

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

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

elementos [] = []

elementos (x:xs) = x : elementos (filter (/=x) xs)

-- (nOcurrencias x ys) es el número de ocurrencias de x en ys. Por

-- ejemplo,

-- nOcurrencias 'a' "Salamanca" == 4

nOcurrencias :: Eq a => a -> [a] -> Integer

nOcurrencias x ys = genericLength (filter (==x) ys)

-- 2ª solución

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

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

factorizacion2 n =

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

-- 3ª solución

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

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

factorizacion3 = map primeroYlongitud

. group

. primeFactors

-- (primeroYlongitud xs) es el par formado por el primer elemento de xs

-- y la longitud de xs. Por ejemplo,

-- primeroYlongitud [3,2,5,7] == (3,4)

primeroYlongitud :: [a] -> (a,Integer)

primeroYlongitud (x:xs) =

(x, 1 + genericLength xs)

-- Comparación de eficiencia de sumaDivisores

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

-- λ> length (factorizacion (product [1..10^4]))

-- 1229

-- (4.84 secs, 2,583,331,768 bytes)

-- λ> length (factorizacion2 (product [1..10^4]))

-- 1229

-- (0.24 secs, 452,543,360 bytes)

-- λ> length (factorizacion3 (product [1..10^4]))

-- 1229

-- (0.23 secs, 452,433,504 bytes)

-- λ> length (factorizacion (product (take (2*10^3) primes)))

-- 2000

-- (6.58 secs, 3,415,098,552 bytes)

-- λ> length (factorizacion2 (product (take (2*10^3) primes)))

-- 2000

-- (0.02 secs, 23,060,512 bytes)

-- λ> length (factorizacion3 (product (take (2*10^3) primes)))

-- 2000

-- (0.02 secs, 22,882,080 bytes)

Pensamiento

¿Todo para los demás?
Mancebo, llena tu jarro,
que ya te lo beberán.

Antonio Machado

Mayor prefijo común

PorJosé A. Alonso 15-noviembre-201922-noviembre-2019

Definir la función

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

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

tal que (mayorPrefijoComun xs ys) calcula el mayor prefijo común a xs e ys. Por ejemplo,

   mayorPrefijoComun "masa" "madre"       == "ma"
   mayorPrefijoComun "masa" "padre"       == ""
   mayorPrefijoComun "hola" "hielo"       == "h"
   mayorPrefijoComun "helado" "heladeria" == "helad"

mayorPrefijoComun "masa" "madre" == "ma"

mayorPrefijoComun "masa" "padre" == ""

mayorPrefijoComun "hola" "hielo" == "h"

mayorPrefijoComun "helado" "heladeria" == "helad"

Soluciones

-- 1ª solución
mayorPrefijoComun :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun _  [] = []
mayorPrefijoComun [] _  = []
mayorPrefijoComun (x:xs) (y:ys)
  | x == y    = x : mayorPrefijoComun xs ys
  | otherwise = []

-- 2ª solución
mayorPrefijoComun2 :: Eq a => [a] -> [a] -> [a]
mayorPrefijoComun2 xs ys =
  [x | (x,_) <- takeWhile iguales (zip xs ys)]
  where iguales (x,y) = x == y

-- 1ª solución

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

mayorPrefijoComun _ [] = []

mayorPrefijoComun [] _ = []

mayorPrefijoComun (x:xs) (y:ys)

| x == y = x : mayorPrefijoComun xs ys

| otherwise = []

-- 2ª solución

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

mayorPrefijoComun2 xs ys =

[x | (x,_) <- takeWhile iguales (zip xs ys)]

where iguales (x,y) = x == y

Pensamiento

Los ojos por que suspiras,
sábelo bien,
los ojos en que te miras
son ojos porque te ven.

Antonio Machado

Listas decrecientes

PorJosé A. Alonso 14-noviembre-201921-noviembre-2019

Definir la función

   listasDecrecientesDesde :: Int -> [[Int]]

1	listasDecrecientesDesde :: Int -> [[Int]]

tal que (listasDecrecientesDesde n) es la lista de las sucesiones estrictamente decrecientes cuyo primer elemento es n. Por ejemplo,

   ghci> listasDecrecientesDesde 2
   [[2],[2,1],[2,1,0],[2,0]]
   ghci> listasDecrecientesDesde 3
   [[3],[3,2],[3,2,1],[3,2,1,0],[3,2,0],[3,1],[3,1,0],[3,0]]

ghci> listasDecrecientesDesde 2

[[2],[2,1],[2,1,0],[2,0]]

ghci> listasDecrecientesDesde 3

[[3],[3,2],[3,2,1],[3,2,1,0],[3,2,0],[3,1],[3,1,0],[3,0]]

Soluciones

-- 1ª solución
listasDecrecientesDesde :: Int -> [[Int]]
listasDecrecientesDesde 0 = [[0]]
listasDecrecientesDesde n =
  [n] : [n:ys | m <- [n-1,n-2..0], ys <- listasDecrecientesDesde m]

-- 2ª solución
listasDecrecientesDesde2 :: Int -> [[Int]]
listasDecrecientesDesde2 0 = [[0]]
listasDecrecientesDesde2 n =
  [n] : [n:xs | m <- [0..n-1], xs <- listasDecrecientesDesde2 m]

-- 1ª solución

listasDecrecientesDesde :: Int -> [[Int]]

listasDecrecientesDesde 0 = [[0]]

listasDecrecientesDesde n =

[n] : [n:ys | m <- [n-1,n-2..0], ys <- listasDecrecientesDesde m]

-- 2ª solución

listasDecrecientesDesde2 :: Int -> [[Int]]

listasDecrecientesDesde2 0 = [[0]]

listasDecrecientesDesde2 n =

[n] : [n:xs | m <- [0..n-1], xs <- listasDecrecientesDesde2 m]

Pensamiento

Viejo como el mundo es
-dijo un doctor-, olvidado,
por sabido, y enterrado
cuál la momia de Ramsés.

Mas el doctor no sabía
que hoy es siempre todavía.

Antonio Machado

Último dígito no nulo del factorial

PorJosé A. Alonso 12-noviembre-201920-noviembre-2019

El factorial de 7 es

   7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040

1	7! = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 5040

por tanto, el último dígito no nulo del factorial de 7 es 4.

Definir la función

   ultimoNoNuloFactorial :: Integer -> Integer

1	ultimoNoNuloFactorial :: Integer -> Integer

tal que (ultimoNoNuloFactorial n) es el último dígito no nulo del factorial de n. Por ejemplo,

   ultimoNoNuloFactorial  7  == 4
   ultimoNoNuloFactorial 10  == 8
   ultimoNoNuloFactorial 12  == 6
   ultimoNoNuloFactorial 97  == 2
   ultimoNoNuloFactorial  0  == 1

ultimoNoNuloFactorial 7 == 4

ultimoNoNuloFactorial 10 == 8

ultimoNoNuloFactorial 12 == 6

ultimoNoNuloFactorial 97 == 2

ultimoNoNuloFactorial 0 == 1

Comprobar con QuickCheck que si n es mayor que 4, entonces el último dígito no nulo del factorial de n es par.

Soluciones

import Data.Char (digitToInt)
import Test.QuickCheck

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

ultimoNoNuloFactorial :: Integer -> Integer
ultimoNoNuloFactorial = ultimoNoNulo . factorial

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

-- (ultimoNoNulo n) es el último dígito no nulo de n. Por ejemplo,
--    ultimoNoNulo 5040  ==  4
ultimoNoNulo :: Integer -> Integer
ultimoNoNulo n | r /= 0    = r
               | otherwise = ultimoNoNulo q
  where (q,r) = n `quotRem` 10

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

ultimoNoNuloFactorial2 :: Integer -> Integer
ultimoNoNuloFactorial2 = last . filter (/= 0) . digitos . factorial

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

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

ultimoNoNuloFactorial3 :: Integer -> Integer
ultimoNoNuloFactorial3 = last . filter (/= 0) . digitos3 . factorial3

digitos3 :: Integer -> [Integer]
digitos3 = map (fromIntegral . digitToInt) . show

factorial3 :: Integer -> Integer
factorial3 = product . enumFromTo 1

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

ultimoNoNulo4 :: Integer -> Integer
ultimoNoNulo4 n = read [head (dropWhile (=='0') (reverse (show n)))]

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

ultimoNoNulo5 :: Integer -> Integer
ultimoNoNulo5 =
  read . return . head . dropWhile ('0' ==) . reverse . show

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

-- La propiedad es
prop_ultimoNoNuloFactorial :: Integer -> Property
prop_ultimoNoNuloFactorial n = 
  n > 4 ==> even (ultimoNoNuloFactorial n)
                  
-- La comprobación es
--    ghci> quickCheck prop_ultimoNoNuloFactorial
--    +++ OK, passed 100 tests.

import Data.Char (digitToInt)

import Test.QuickCheck

-- 1ª solución

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

ultimoNoNuloFactorial :: Integer -> Integer

ultimoNoNuloFactorial = ultimoNoNulo . factorial

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

-- factorial 7 == 5040

factorial :: Integer -> Integer

factorial n = product [1..n]

-- (ultimoNoNulo n) es el último dígito no nulo de n. Por ejemplo,

-- ultimoNoNulo 5040 == 4

ultimoNoNulo :: Integer -> Integer

ultimoNoNulo n | r /= 0 = r

| otherwise = ultimoNoNulo q

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

-- 2ª solución

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

ultimoNoNuloFactorial2 :: Integer -> Integer

ultimoNoNuloFactorial2 = last . filter (/= 0) . digitos . factorial

digitos :: Integer -> [Integer]

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

-- 3ª solución

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

ultimoNoNuloFactorial3 :: Integer -> Integer

ultimoNoNuloFactorial3 = last . filter (/= 0) . digitos3 . factorial3

digitos3 :: Integer -> [Integer]

digitos3 = map (fromIntegral . digitToInt) . show

factorial3 :: Integer -> Integer

factorial3 = product . enumFromTo 1

-- 4ª solución

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

ultimoNoNulo4 :: Integer -> Integer

ultimoNoNulo4 n = read [head (dropWhile (=='0') (reverse (show n)))]

-- 5ª solución

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

ultimoNoNulo5 :: Integer -> Integer

ultimoNoNulo5 =

read . return . head . dropWhile ('0' ==) . reverse . show

-- Propiedad

-- =========

-- La propiedad es

prop_ultimoNoNuloFactorial :: Integer -> Property

prop_ultimoNoNuloFactorial n =

n > 4 ==> even (ultimoNoNuloFactorial n)

-- La comprobación es

-- ghci> quickCheck prop_ultimoNoNuloFactorial

-- +++ OK, passed 100 tests.

Pensamiento

Busca el tu esencial,
que no está en ninguna parte
y en todas partes está.

Antonio Machado

Las sucesiones de Loomis

PorJosé A. Alonso 15-mayo-201925-abril-2021

La sucesión de Loomis generada por un número entero positivo x es la sucesión cuyos términos se definen por

f(0) es x
f(n) es la suma de f(n-1) y el producto de los dígitos no nulos de f(n-1)

Los primeros términos de las primeras sucesiones de Loomis son

Generada por 1: 1, 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, …
Generada por 2: 2, 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
Generada por 3: 3, 6, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, …
Generada por 4: 4, 8, 16, 22, 26, 38, 62, 74, 102, 104, 108, 116, 122, 126, 138, …
Generada por 5: 5, 10, 11, 12, 14, 18, 26, 38, 62, 74, 102, 104, 108, 116, 122, …

Se observa que a partir de un término todas coinciden con la generada por 1. Dicho término se llama el punto de convergencia. Por ejemplo,

la generada por 2 converge a 2
la generada por 3 converge a 26
la generada por 4 converge a 4
la generada por 5 converge a 26

Definir las siguientes funciones

   sucLoomis           :: Integer -> [Integer]
   convergencia        :: Integer -> Integer
   graficaConvergencia :: [Integer] -> IO ()

sucLoomis :: Integer -> [Integer]

convergencia :: Integer -> Integer

graficaConvergencia :: [Integer] -> IO ()

tales que

(sucLoomis x) es la sucesión de Loomis generada por x. Por ejemplo,

     λ> take 15 (sucLoomis 1)
     [1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 2)
     [2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 3)
     [3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]
     λ> take 15 (sucLoomis 4)
     [4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]
     λ> take 15 (sucLoomis 5)
     [5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]
     λ> take 15 (sucLoomis 20)
     [20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]
     λ> take 15 (sucLoomis 100)
     [100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]
     λ> sucLoomis 1 !! (2*10^5)
     235180736652

λ> take 15 (sucLoomis 1)

[1,2,4,8,16,22,26,38,62,74,102,104,108,116,122]

λ> take 15 (sucLoomis 2)

[2,4,8,16,22,26,38,62,74,102,104,108,116,122,126]

λ> take 15 (sucLoomis 3)

[3,6,12,14,18,26,38,62,74,102,104,108,116,122,126]

λ> take 15 (sucLoomis 4)

[4,8,16,22,26,38,62,74,102,104,108,116,122,126,138]

λ> take 15 (sucLoomis 5)

[5,10,11,12,14,18,26,38,62,74,102,104,108,116,122]

λ> take 15 (sucLoomis 20)

[20,22,26,38,62,74,102,104,108,116,122,126,138,162,174]

λ> take 15 (sucLoomis 100)

[100,101,102,104,108,116,122,126,138,162,174,202,206,218,234]

λ> sucLoomis 1 !! (2*10^5)

235180736652

(convergencia x) es el término de convergencia de la sucesioń de Loomis generada por x xon la geerada por 1. Por ejemplo,

     convergencia  2      ==  2
     convergencia  3      ==  26
     convergencia  4      ==  4
     convergencia 17      ==  38
     convergencia 19      ==  102
     convergencia 43      ==  162
     convergencia 27      ==  202
     convergencia 58      ==  474
     convergencia 63      ==  150056
     convergencia 81      ==  150056
     convergencia 89      ==  150056
     convergencia (10^12) ==  1000101125092

convergencia 2 == 2

convergencia 3 == 26

convergencia 4 == 4

convergencia 17 == 38

convergencia 19 == 102

convergencia 43 == 162

convergencia 27 == 202

convergencia 58 == 474

convergencia 63 == 150056

convergencia 81 == 150056

convergencia 89 == 150056

convergencia (10^12) == 1000101125092

(graficaConvergencia xs) dibuja la gráfica de los términos de convergencia de las sucesiones de Loomis generadas por los elementos de xs. Por ejemplo, (graficaConvergencia ([1..50]) dibuja

y graficaConvergencia ([1..148] \ [63,81,89,137]) dibuja

Soluciones

import Data.List               ((\\))
import Data.Char               (digitToInt)
import Graphics.Gnuplot.Simple (plotList, Attribute (Key, Title, XRange, PNG))

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

sucLoomis :: Integer -> [Integer]
sucLoomis x = map (loomis x) [0..]

loomis :: Integer -> Integer -> Integer
loomis x 0 = x
loomis x n = y + productoDigitosNoNulos y
  where y = loomis x (n-1)

productoDigitosNoNulos :: Integer -> Integer
productoDigitosNoNulos = product . digitosNoNulos

digitosNoNulos :: Integer -> [Integer]
digitosNoNulos x =
  [read [c] | c <- show x, c /= '0']

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

sucLoomis2 :: Integer -> [Integer]
sucLoomis2 = iterate siguienteLoomis 

siguienteLoomis :: Integer -> Integer
siguienteLoomis y = y + productoDigitosNoNulos y

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

sucLoomis3 :: Integer -> [Integer]
sucLoomis3 =
  iterate ((+) <*> product .
           map (toInteger . digitToInt) .
           filter (/= '0') . show)

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

--    λ> sucLoomis 1 !! 30000
--    6571272766
--    (2.45 secs, 987,955,944 bytes)
--    λ> sucLoomis2 1 !! 30000
--    6571272766
--    (2.26 secs, 979,543,328 bytes)
--    λ> sucLoomis3 1 !! 30000
--    6571272766
--    (0.31 secs, 88,323,832 bytes)

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

convergencia1 :: Integer -> Integer
convergencia1 x =
  head (dropWhile noEnSucLoomisDe1 (sucLoomis x))

noEnSucLoomisDe1 :: Integer -> Bool
noEnSucLoomisDe1 x = not (pertenece x sucLoomisDe1)

sucLoomisDe1 :: [Integer]
sucLoomisDe1 = sucLoomis 1

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

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

convergencia2 :: Integer -> Integer
convergencia2 = aux (sucLoomis3 1) . sucLoomis3
 where aux as@(x:xs) bs@(y:ys) | x == y    = x
                               | x < y     = aux xs bs
                               | otherwise = aux as ys

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

convergencia3 :: Integer -> Integer
convergencia3 = head . interseccion (sucLoomis3 1) . sucLoomis3
 
-- (interseccion xs ys) es la intersección entre las listas ordenadas xs
-- e ys. Por ejemplo,
--    λ> take 10 (interseccion (sucLoomis3 1) (sucLoomis3 2))
--    [2,4,8,16,22,26,38,62,74,102]
interseccion :: Ord a => [a] -> [a] -> [a]
interseccion = aux
  where aux as@(x:xs) bs@(y:ys) = case compare x y of
                                    LT ->     aux xs bs
                                    EQ -> x : aux xs ys
                                    GT ->     aux as ys
        aux _         _         = []                           

-- 4ª definición de convergencia
-- =============================

convergencia4 :: Integer -> Integer
convergencia4 x = perteneceA (sucLoomis3 x) 1
  where perteneceA (y:ys) n | y == c    = y
                            | otherwise = perteneceA ys c
          where c = head $ dropWhile (< y) $ sucLoomis3 n

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

--    λ> convergencia1 (10^4)
--    150056
--    (2.94 secs, 1,260,809,808 bytes)
--    λ> convergencia2 (10^4)
--    150056
--    (0.03 secs, 700,240 bytes)
--    λ> convergencia3 (10^4)
--    150056
--    (0.03 secs, 1,165,496 bytes)
--    λ> convergencia4 (10^4)
--    150056
--    (0.02 secs, 1,119,648 bytes)
--    
--    λ> convergencia2 (10^12)
--    1000101125092
--    (1.81 secs, 714,901,080 bytes)
--    λ> convergencia3 (10^12)
--    1000101125092
--    (1.92 secs, 744,932,184 bytes)
--    λ> convergencia4 (10^12)
--    1000101125092
--    (1.82 secs, 941,053,328 bytes)

-- Definición de graficaConvergencia
-- ==================================

graficaConvergencia :: [Integer] -> IO ()
graficaConvergencia xs =
  plotList [ Key Nothing
           , Title "Convergencia de sucesiones de Loomis"
           , XRange (fromIntegral (minimum xs),fromIntegral (maximum xs))
           , PNG "Las_sucesiones_de_Loomis_2.png"
           ]
           [(x,convergencia2 x) | x <- xs]

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

import Data.List ((\\))

import Data.Char (digitToInt)

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

-- 1ª definición de sucLoomis

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

sucLoomis :: Integer -> [Integer]

sucLoomis x = map (loomis x) [0..]

loomis :: Integer -> Integer -> Integer

loomis x 0 = x

loomis x n = y + productoDigitosNoNulos y

where y = loomis x (n-1)

productoDigitosNoNulos :: Integer -> Integer

productoDigitosNoNulos = product . digitosNoNulos

digitosNoNulos :: Integer -> [Integer]

digitosNoNulos x =

[read [c] | c <- show x, c /= '0']

-- 2ª definición de sucLoomis

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

sucLoomis2 :: Integer -> [Integer]

sucLoomis2 = iterate siguienteLoomis

siguienteLoomis :: Integer -> Integer

siguienteLoomis y = y + productoDigitosNoNulos y

-- 3ª definición de sucLoomis

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

sucLoomis3 :: Integer -> [Integer]

sucLoomis3 =

iterate ((+) <*> product .

map (toInteger . digitToInt) .

filter (/= '0') . show)

-- Comparación de eficiencia

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

-- λ> sucLoomis 1 !! 30000

-- 6571272766

-- (2.45 secs, 987,955,944 bytes)

-- λ> sucLoomis2 1 !! 30000

-- 6571272766

-- (2.26 secs, 979,543,328 bytes)

-- λ> sucLoomis3 1 !! 30000

-- 6571272766

-- (0.31 secs, 88,323,832 bytes)

-- 1ª definición de convergencia

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

convergencia1 :: Integer -> Integer

convergencia1 x =

head (dropWhile noEnSucLoomisDe1 (sucLoomis x))

noEnSucLoomisDe1 :: Integer -> Bool

noEnSucLoomisDe1 x = not (pertenece x sucLoomisDe1)

sucLoomisDe1 :: [Integer]

sucLoomisDe1 = sucLoomis 1

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

pertenece x ys =

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

-- 2ª definición de convergencia

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

convergencia2 :: Integer -> Integer

convergencia2 = aux (sucLoomis3 1) . sucLoomis3

where aux as@(x:xs) bs@(y:ys) | x == y = x

| x < y = aux xs bs

| otherwise = aux as ys

-- 3ª definición de convergencia

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

convergencia3 :: Integer -> Integer

convergencia3 = head . interseccion (sucLoomis3 1) . sucLoomis3

-- (interseccion xs ys) es la intersección entre las listas ordenadas xs

-- e ys. Por ejemplo,

-- λ> take 10 (interseccion (sucLoomis3 1) (sucLoomis3 2))

-- [2,4,8,16,22,26,38,62,74,102]

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

interseccion = aux

where aux as@(x:xs) bs@(y:ys) = case compare x y of

LT -> aux xs bs

EQ -> x : aux xs ys

GT -> aux as ys

aux _ _ = []

-- 4ª definición de convergencia

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

convergencia4 :: Integer -> Integer

convergencia4 x = perteneceA (sucLoomis3 x) 1

where perteneceA (y:ys) n | y == c = y

| otherwise = perteneceA ys c

where c = head $ dropWhile (< y) $ sucLoomis3 n

-- Comparación de eficiencia

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

-- λ> convergencia1 (10^4)

-- 150056

-- (2.94 secs, 1,260,809,808 bytes)

-- λ> convergencia2 (10^4)

-- 150056

-- (0.03 secs, 700,240 bytes)

-- λ> convergencia3 (10^4)

-- 150056

-- (0.03 secs, 1,165,496 bytes)

-- λ> convergencia4 (10^4)

-- 150056

-- (0.02 secs, 1,119,648 bytes)

-- λ> convergencia2 (10^12)

-- 1000101125092

-- (1.81 secs, 714,901,080 bytes)

-- λ> convergencia3 (10^12)

-- 1000101125092

-- (1.92 secs, 744,932,184 bytes)

-- λ> convergencia4 (10^12)

-- 1000101125092

-- (1.82 secs, 941,053,328 bytes)

-- Definición de graficaConvergencia

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

graficaConvergencia :: [Integer] -> IO ()

graficaConvergencia xs =

plotList [ Key Nothing

, Title "Convergencia de sucesiones de Loomis"

, XRange (fromIntegral (minimum xs),fromIntegral (maximum xs))

, PNG "Las_sucesiones_de_Loomis_2.png"

]

[(x,convergencia2 x) | x <- xs]

Pensamiento

Era una noche del mes
de mayo, azul y serena.
Sobre el agudo ciprés
brillaba la luna llena.

Antonio Machado

Mayor producto de n dígitos consecutivos de un número

PorJosé A. Alonso 14-mayo-201925-abril-2021

Definir la función

   mayorProducto :: Int -> Integer -> Integer

1	mayorProducto :: Int -> Integer -> Integer

tal que (mayorProducto n x) es el mayor producto de n dígitos consecutivos del número x (suponiendo que x tiene al menos n dígitos). Por ejemplo,

   mayorProducto 2 325                  ==  10
   mayorProducto 5 11111                ==  1
   mayorProducto 5 113111               ==  3
   mayorProducto 5 110111               ==  0
   mayorProducto 5 10151112             ==  10
   mayorProducto 5 101511124            ==  10
   mayorProducto 5 (product [1..1000])  ==  41472

mayorProducto 2 325 == 10

mayorProducto 5 11111 == 1

mayorProducto 5 113111 == 3

mayorProducto 5 110111 == 0

mayorProducto 5 10151112 == 10

mayorProducto 5 101511124 == 10

mayorProducto 5 (product [1..1000]) == 41472

Soluciones

import Test.QuickCheck
import Data.List (inits, tails)
import Data.Char (digitToInt)

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

mayorProducto1 :: Int -> Integer -> Integer
mayorProducto1 n x =
  maximum [product xs | xs <- segmentos n (cifras x)]

-- (cifras x) es la lista de las cifras del número x. Por ejemplo, 
--    cifras 325  ==  [3,2,5]
cifras :: Integer -> [Integer]
cifras x = map (toInteger . digitToInt) (show x)

-- (segmentos n xs) es la lista de los segmentos de longitud n de la
-- lista xs. Por ejemplo,
--    segmentos 2 [3,5,4,6]  ==  [[3,5],[5,4],[4,6]]
segmentos :: Int -> [Integer] -> [[Integer]]
segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs))

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

mayorProducto2 :: Int -> Integer -> Integer
mayorProducto2 n x = maximum (aux ns)
    where ns     = [read [d] | d <- show x]
          aux xs | length xs < n = []
                 | otherwise     = product (take n xs) : aux (tail xs)

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

mayorProducto3 :: Int -> Integer -> Integer
mayorProducto3 n = maximum
                 . map (product . take n)
                 . filter ((>=n) . length) 
                 . tails
                 . cifras

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

mayorProducto4 :: Int -> Integer -> Integer
mayorProducto4 n = maximum  
                 . map (product . map (fromIntegral . digitToInt)) 
                 . filter ((==n) . length) 
                 . concatMap inits
                 . tails 
                 . show

-- ---------------------------------------------------------------------
-- Comparación de soluciones                                          --
-- ---------------------------------------------------------------------

-- Tiempo (en segundos) del cálculo de (mayorProducto 5 (product [1..n]))
-- 
--    | Def | 500  | 1000 | 5000 | 10000 
--    | 1   | 0.01 | 0.02 | 0.06 | 0.11
--    | 2   | 0.01 | 0.03 | 0.80 | 3.98
--    | 3   | 0.01 | 0.03 | 0.82 | 4.13
--    | 4   | 2.77 |      |      |

import Test.QuickCheck

import Data.List (inits, tails)

import Data.Char (digitToInt)

-- 1ª solución

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

mayorProducto1 :: Int -> Integer -> Integer

mayorProducto1 n x =

maximum [product xs | xs <- segmentos n (cifras x)]

-- (cifras x) es la lista de las cifras del número x. Por ejemplo,

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

cifras :: Integer -> [Integer]

cifras x = map (toInteger . digitToInt) (show x)

-- (segmentos n xs) es la lista de los segmentos de longitud n de la

-- lista xs. Por ejemplo,

-- segmentos 2 [3,5,4,6] == [[3,5],[5,4],[4,6]]

segmentos :: Int -> [Integer] -> [[Integer]]

segmentos n xs = take (length xs - n + 1) (map (take n) (tails xs))

-- 2ª solución

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

mayorProducto2 :: Int -> Integer -> Integer

mayorProducto2 n x = maximum (aux ns)

where ns = [read [d] | d <- show x]

aux xs | length xs < n = []

| otherwise = product (take n xs) : aux (tail xs)

-- 3ª solución

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

mayorProducto3 :: Int -> Integer -> Integer

mayorProducto3 n = maximum

. map (product . take n)

. filter ((>=n) . length)

. tails

. cifras

-- 4ª solución

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

mayorProducto4 :: Int -> Integer -> Integer

mayorProducto4 n = maximum

. map (product . map (fromIntegral . digitToInt))

. filter ((==n) . length)

. concatMap inits

. tails

. show

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

-- Comparación de soluciones --

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

-- Tiempo (en segundos) del cálculo de (mayorProducto 5 (product [1..n]))

-- | Def | 500 | 1000 | 5000 | 10000

-- | 1 | 0.01 | 0.02 | 0.06 | 0.11

-- | 2 | 0.01 | 0.03 | 0.80 | 3.98

-- | 3 | 0.01 | 0.03 | 0.82 | 4.13

-- | 4 | 2.77 | | |

Pensamiento

A las palabras de amor
les sienta bien su poquito
de exageración.

Antonio Machado

Número de emparejamientos de amigos

PorJosé A. Alonso 30-abril-201919-mayo-2019

El problema del número de emparejamiento de amigos consiste en calcular el número de formas de emparejar n amigos teniendo en cuenta que cada uno puede permanecer soltero o puede ser emparejado con algún otro amigo y que cada amigo puede ser emparejado sólo una vez. Por ejemplo, los 4 posibles emparejamientos de 3 amigos son

   {1}, {2}, {3} 
   {1}, {2, 3} 
   {1, 2}, {3} 
   {1, 3}, {2}

{1}, {2}, {3}

{1}, {2, 3}

{1, 2}, {3}

{1, 3}, {2}

Definir la función

   nEmparejamientos :: Integer -> Integer

1	nEmparejamientos :: Integer -> Integer

tal que (nEmparejamientos n) es el número de formas de emparejar a los n amigos. Por ejemplo,

   nEmparejamientos 2   ==  2
   nEmparejamientos 3   ==  4
   nEmparejamientos 4   ==  10
   nEmparejamientos 10  ==  9496
   nEmparejamientos 30  ==  606917269909048576
   length (show (nEmparejamientos3 (10^4)))  ==  17872

nEmparejamientos 2 == 2

nEmparejamientos 3 == 4

nEmparejamientos 4 == 10

nEmparejamientos 10 == 9496

nEmparejamientos 30 == 606917269909048576

length (show (nEmparejamientos3 (10^4))) == 17872

Soluciones

import Data.List (delete, genericLength)
import Data.Array

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

nEmparejamientos :: Integer -> Integer
nEmparejamientos = genericLength . emparejamientos

emparejamientos :: Integer -> [[[Integer]]]
emparejamientos n = aux [1..n]
  where aux [] = [[]]
        aux (x:xs) = [[x] : ps | ps <- aux xs] ++
                     [[x,y] : ps | y <- xs, ps <- aux (delete y xs)]

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

nEmparejamientos2 :: Integer -> Integer
nEmparejamientos2 0 = 1
nEmparejamientos2 1 = 1
nEmparejamientos2 2 = 2
nEmparejamientos2 n = nEmparejamientos2 (n - 1) + (n - 1) * nEmparejamientos2 (n - 2)

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

nEmparejamientos3 :: Integer -> Integer
nEmparejamientos3 n = (vectorEmparejamientos n) ! n

-- (vectorEmparejamientos n) es el vector con índices de 0 a n tal que el valor
-- de la posición i es el número de formas de emparejar a i amigos. Por ejemplo,
--    λ> vectorEmparejamientos 7
--    array (0,7) [(0,1),(1,1),(2,2),(3,4),(4,10),(5,26),(6,76),(7,232)]
vectorEmparejamientos :: Integer -> Array Integer Integer
vectorEmparejamientos n = v where
  v = array (0,n) [(i,f i) | i <- [0..n]]
  f 0 = 1
  f 1 = 1
  f 2 = 2
  f n = v!(n-1) + (n-1)*v!(n-2)

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

--    λ> nEmparejamientos 12
--    140152
--    (1.81 secs, 280,218,616 bytes)
--    λ> nEmparejamientos2 12
--    140152
--    (0.01 secs, 177,168 bytes)
--    λ> nEmparejamientos3 12
--    140152
--    (0.01 secs, 108,816 bytes)
--    
--    λ> nEmparejamientos2 30
--    606917269909048576
--    (3.97 secs, 449,224,280 bytes)
--    λ> nEmparejamientos3 30
--    606917269909048576
--    (0.01 secs, 135,160 bytes)

import Data.List (delete, genericLength)

import Data.Array

-- 1ª solución

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

nEmparejamientos :: Integer -> Integer

nEmparejamientos = genericLength . emparejamientos

emparejamientos :: Integer -> [[[Integer]]]

emparejamientos n = aux [1..n]

where aux [] = [[]]

aux (x:xs) = [[x] : ps | ps <- aux xs] ++

[[x,y] : ps | y <- xs, ps <- aux (delete y xs)]

-- 2ª solución

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

nEmparejamientos2 :: Integer -> Integer

nEmparejamientos2 0 = 1

nEmparejamientos2 1 = 1

nEmparejamientos2 2 = 2

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

-- 3ª solución

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

nEmparejamientos3 :: Integer -> Integer

nEmparejamientos3 n = (vectorEmparejamientos n) ! n

-- (vectorEmparejamientos n) es el vector con índices de 0 a n tal que el valor

-- de la posición i es el número de formas de emparejar a i amigos. Por ejemplo,

-- λ> vectorEmparejamientos 7

-- array (0,7) [(0,1),(1,1),(2,2),(3,4),(4,10),(5,26),(6,76),(7,232)]

vectorEmparejamientos :: Integer -> Array Integer Integer

vectorEmparejamientos n = v where

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

f 0 = 1

f 1 = 1

f 2 = 2

f n = v!(n-1) + (n-1)*v!(n-2)

-- Comparación de eficiencia

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

-- λ> nEmparejamientos 12

-- 140152

-- (1.81 secs, 280,218,616 bytes)

-- λ> nEmparejamientos2 12

-- 140152

-- (0.01 secs, 177,168 bytes)

-- λ> nEmparejamientos3 12

-- 140152

-- (0.01 secs, 108,816 bytes)

-- λ> nEmparejamientos2 30

-- 606917269909048576

-- (3.97 secs, 449,224,280 bytes)

-- λ> nEmparejamientos3 30

-- 606917269909048576

-- (0.01 secs, 135,160 bytes)

Pensamiento

Toda la imaginería
que no ha brotado del río,
barata bisutería.

Antonio Machado

Emparejamiento de amigos

PorJosé A. Alonso 29-abril-201919-mayo-2019

El problema de emparejamiento de amigos consiste en calcular las formas de emparejar n amigos teniendo en cuenta que cada uno puede permanecer soltero o puede ser emparejado con algún otro amigo y que cada amigo puede ser emparejado sólo una vez. Por ejemplo, los 4 posibles emparejamientos de 3 amigos son

   {1}, {2}, {3} 
   {1}, {2, 3} 
   {1, 2}, {3} 
   {1, 3}, {2}

{1}, {2}, {3}

{1}, {2, 3}

{1, 2}, {3}

{1, 3}, {2}

Definir la función

   emparejamientos :: Integer -> [[[Integer]]]

1	emparejamientos :: Integer -> [[[Integer]]]

tal que (emparejamientos n) es la lista de los posibles emparejamientos de los n amigos (numerados del 1 al n). Por ejemplo,

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

λ> emparejamientos 2

[[[1],[2]],[[1,2]]]

λ> emparejamientos 3

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

Soluciones

import Data.List (delete)

emparejamientos :: Integer -> [[[Integer]]]
emparejamientos n = aux [1..n]
  where aux [] = [[]]
        aux (x:xs) = [[x] : ps | ps <- aux xs] ++
                     [[x,y] : ps | y <- xs, ps <- aux (delete y xs)]

import Data.List (delete)

emparejamientos :: Integer -> [[[Integer]]]

emparejamientos n = aux [1..n]

where aux [] = [[]]

aux (x:xs) = [[x] : ps | ps <- aux xs] ++

[[x,y] : ps | y <- xs, ps <- aux (delete y xs)]

Pensamiento

Crea el alma sus riberas;
montes de ceniza y plomo,
sotillos de primavera.

Antonio Machado

Elementos no repetidos

PorJosé A. Alonso 22-abril-20191-mayo-2019

Definir la función

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

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

tal que (noRepetidos xs) es la lista de los elementos no repetidos de la lista xs. Por ejemplo,

   noRepetidos [3,2,5,2,4,7,3]  ==  [5,4,7]
   noRepetidos "noRepetidos"    ==  "nRptids"
   noRepetidos "Roma"           ==  "Roma"

noRepetidos [3,2,5,2,4,7,3] == [5,4,7]

noRepetidos "noRepetidos" == "nRptids"

noRepetidos "Roma" == "Roma"

Soluciones

import Test.QuickCheck

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

noRepetidos :: Eq a => [a] -> [a]
noRepetidos xs = 
  [x | x <- xs, ocurrencias x xs == 1]
  
-- (ocurrencias x ys) es el número de ocurrencias de x en ys. Por
-- ejemplo,
--    ocurrencias 3 [3,2,5,2,4,7,3]  ==  2
--    ocurrencias 5 [3,2,5,2,4,7,3]  ==  1
ocurrencias :: Eq a => a -> [a] -> Int
ocurrencias x ys = 
  length [y | y <- ys, y == x]

-- 2ª solución
-- ===========
noRepetidos2 :: Eq a => [a] -> [a]
noRepetidos2 [] = []
noRepetidos2 (x:xs) | elem x xs = noRepetidos2 [y | y <- xs, y /= x]
                    | otherwise = x : noRepetidos2 xs

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

-- La propiedad de equivalencia es
prop_equivalencia :: [Int] -> Bool
prop_equivalencia xs =
  noRepetidos xs == noRepetidos2 xs

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

import Test.QuickCheck

-- 1ª solución

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

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

noRepetidos xs =

[x | x <- xs, ocurrencias x xs == 1]

-- (ocurrencias x ys) es el número de ocurrencias de x en ys. Por

-- ejemplo,

-- ocurrencias 3 [3,2,5,2,4,7,3] == 2

-- ocurrencias 5 [3,2,5,2,4,7,3] == 1

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

ocurrencias x ys =

length [y | y <- ys, y == x]

-- 2ª solución

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

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

noRepetidos2 [] = []

noRepetidos2 (x:xs) | elem x xs = noRepetidos2 [y | y <- xs, y /= x]

| otherwise = x : noRepetidos2 xs

-- Equivalencia

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

-- La propiedad de equivalencia es

prop_equivalencia :: [Int] -> Bool

prop_equivalencia xs =

noRepetidos xs == noRepetidos2 xs

-- La comprobación es

-- ghci> quickCheck prop_equivalencia

-- +++ OK, passed 100 tests.

Pensamiento

Y en perfecto rimo
— así a la vera del agua
el doble chopo del río.

Antonio Machado

Matriz dodecafónica

PorJosé A. Alonso 10-abril-201925-abril-2019

Como se explica en Create a Twelve-Tone Melody With a Twelve-Tone Matrix una matriz dodecafónica es una matriz de 12 filas y 12 columnas construidas siguiendo los siguientes pasos:

Se escribe en la primera fila una permutación de los números del 1 al 12. Por ejemplo,

     (  3  1  9  5  4  6  8  7 12 10 11  2 )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )
     (                                     )

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( )

Escribir la primera columna de forma que, para todo i (entre 2 y 12), a(i,1) es el número entre 1 y 12 que verifica la siguiente condición

     (a(1,1) - a(i,1)) = (a(1,i) - a(1,1)) (módulo 12)

1	(a(1,1) - a(i,1)) = (a(1,i) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz con la 1ª fila y la 1ª columna es

     (  3  1  9  5  4  6  8  7 12 10 11  2 )
     (  5                                  )
     (  9                                  )
     (  1                                  )
     (  2                                  )
     ( 12                                  )
     ( 10                                  )
     ( 11                                  )
     (  6                                  )
     (  8                                  )
     (  7                                  )
     (  4                                  )

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( 5 )

( 9 )

( 1 )

( 2 )

( 12 )

( 10 )

( 11 )

( 6 )

( 8 )

( 7 )

( 4 )

Escribir la segunda fila de forma que, para todo j (entre 2 y 12), a(j,2) es el número entre 1 y 12 que verifica la siguiente condición

     (a(2,j) - a(1,j)) = (a(2,1) - a(1,1)) (módulo 12)

1	(a(2,j) - a(1,j)) = (a(2,1) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz con la 1ª fila, 1ª columna y 2ª fila es

     (  3  1  9  5  4  6  8  7 12 10 11  2 )
     (  5  3 11  7  6  8 10  9  2 12  1  4 )
     (  9                                  )
     (  1                                  )
     (  2                                  )
     ( 12                                  )
     ( 10                                  )
     ( 11                                  )
     (  6                                  )
     (  8                                  )
     (  7                                  )
     (  4                                  )

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( 5 3 11 7 6 8 10 9 2 12 1 4 )

( 9 )

( 1 )

( 2 )

( 12 )

( 10 )

( 11 )

( 6 )

( 8 )

( 7 )

( 4 )

Las restantes filas se completan como la 2ª; es decir, para todo i (entre 3 y 12) y todo j (entre 2 y 12), a(i,j) es el número entre 1 y 12 que verifica la siguiente relación.

     (a(i,j) - a(1,j)) = (a(i,1) - a(1,1)) (módulo 12)

1	(a(i,j) - a(1,j)) = (a(i,1) - a(1,1)) (módulo 12)

Siguiendo con el ejemplo anterior, la matriz dodecafónica es

     (  3  1  9  5  4  6  8  7 12 10 11  2 )
     (  5  3 11  7  6  8 10  9  2 12  1  4 )
     (  9  7  3 11 10 12  2  1  6  4  5  8 )
     (  1 11  7  3  2  4  6  5 10  8  9 12 )
     (  2 12  8  4  3  5  7  6 11  9 10  1 )
     ( 12 10  6  2  1  3  5  4  9  7  8 11 )
     ( 10  8  4 12 11  1  3  2  7  5  6  9 )
     ( 11  9  5  1 12  2  4  3  8  6  7 10 )
     (  6  4 12  8  7  9 11 10  3  1  2  5 )
     (  8  6  2 10  9 11  1 12  5  3  4  7 )
     (  7  5  1  9  8 10 12 11  4  2  3  6 )
     (  4  2 10  6  5  7  9  8  1 11 12  3 )

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( 5 3 11 7 6 8 10 9 2 12 1 4 )

( 9 7 3 11 10 12 2 1 6 4 5 8 )

( 1 11 7 3 2 4 6 5 10 8 9 12 )

( 2 12 8 4 3 5 7 6 11 9 10 1 )

( 12 10 6 2 1 3 5 4 9 7 8 11 )

( 10 8 4 12 11 1 3 2 7 5 6 9 )

( 11 9 5 1 12 2 4 3 8 6 7 10 )

( 6 4 12 8 7 9 11 10 3 1 2 5 )

( 8 6 2 10 9 11 1 12 5 3 4 7 )

( 7 5 1 9 8 10 12 11 4 2 3 6 )

( 4 2 10 6 5 7 9 8 1 11 12 3 )

Definir la función

   matrizDodecafonica :: [Int] -> Matrix Int

1	matrizDodecafonica :: [Int] -> Matrix Int

tal que (matrizDodecafonica xs) es la matriz dodecafónica cuya primera fila es xs (que se supone que es una permutación de los números del 1 al 12). Por ejemplo,

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

λ> matrizDodecafonica [3,1,9,5,4,6,8,7,12,10,11,2]

( 3 1 9 5 4 6 8 7 12 10 11 2 )

( 5 3 11 7 6 8 10 9 2 12 1 4 )

( 9 7 3 11 10 12 2 1 6 4 5 8 )

( 1 11 7 3 2 4 6 5 10 8 9 12 )

( 2 12 8 4 3 5 7 6 11 9 10 1 )

( 12 10 6 2 1 3 5 4 9 7 8 11 )

( 10 8 4 12 11 1 3 2 7 5 6 9 )

( 11 9 5 1 12 2 4 3 8 6 7 10 )

( 6 4 12 8 7 9 11 10 3 1 2 5 )

( 8 6 2 10 9 11 1 12 5 3 4 7 )

( 7 5 1 9 8 10 12 11 4 2 3 6 )

( 4 2 10 6 5 7 9 8 1 11 12 3 )

Comprobar con QuickCheck para toda matriz dodecafónica D se verifican las siguientes propiedades:

todas las filas de D son permutaciones de los números 1 a 12,
todos los elementos de la diagonal de D son iguales y
la suma de todos los elementos de D es 936.

Nota: Este ejercicio ha sido propuesto por Francisco J. Hidalgo.

Soluciones

import Data.List
import Test.QuickCheck
import Data.Matrix

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

matrizDodecafonica :: [Int] -> Matrix Int
matrizDodecafonica xs = matrix 12 12 f
  where f (1,j) = xs !! (j-1)
        f (i,1) = modulo12 (2 * f (1,1) - f (1,i)) 
        f (i,j) = modulo12 (f (1,j) + f (i,1) - f (1,1)) 
        modulo12 0  = 12
        modulo12 12 = 12
        modulo12 x  = x `mod` 12
  
-- 2ª solución
-- ===========

matrizDodecafonica2 :: [Int] -> Matrix Int
matrizDodecafonica2 xs = fromLists (secuencias xs)

secuencias :: [Int] -> [[Int]]
secuencias xs = [secuencia a xs | a <- inversa xs]

inversa :: [Int] -> [Int]
inversa xs = map conv (map (\x -> (-x) + 2* (abs a)) xs)
  where a = head xs
        
secuencia :: Int -> [Int] -> [Int]
secuencia n xs = [conv (a+(n-b)) | a <- xs] 
  where b = head xs

conv :: Int -> Int
conv n | n == 0 = 12
       | n < 0 = conv (n+12)
       | n > 11 = conv (mod n 12)
       | otherwise = n          

-- Propiedades
-- ===========

-- Las propiedades son
prop_dodecafonica :: Int -> Property
prop_dodecafonica n = 
  n >= 0 ==>
  all esPermutacion (toLists d)
  && all (== d!(1,1)) [d!(i,i) | i <- [2..12]]
  && sum d == 936
  where xss = permutations [1..12]
        k   = n `mod` product [1..12]
        d   = matrizDodecafonica (xss !! k)
        esPermutacion ys = sort ys == [1..12]

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

import Data.List

import Test.QuickCheck

import Data.Matrix

-- 1ª solución

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

matrizDodecafonica :: [Int] -> Matrix Int

matrizDodecafonica xs = matrix 12 12 f

where f (1,j) = xs !! (j-1)

f (i,1) = modulo12 (2 * f (1,1) - f (1,i))

f (i,j) = modulo12 (f (1,j) + f (i,1) - f (1,1))

modulo12 0 = 12

modulo12 12 = 12

modulo12 x = x `mod` 12

-- 2ª solución

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

matrizDodecafonica2 :: [Int] -> Matrix Int

matrizDodecafonica2 xs = fromLists (secuencias xs)

secuencias :: [Int] -> [[Int]]

secuencias xs = [secuencia a xs | a <- inversa xs]

inversa :: [Int] -> [Int]

inversa xs = map conv (map (\x -> (-x) + 2* (abs a)) xs)

where a = head xs

secuencia :: Int -> [Int] -> [Int]

secuencia n xs = [conv (a+(n-b)) | a <- xs]

where b = head xs

conv :: Int -> Int

conv n | n == 0 = 12

| n < 0 = conv (n+12)

| n > 11 = conv (mod n 12)

| otherwise = n

-- Propiedades

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

-- Las propiedades son

prop_dodecafonica :: Int -> Property

prop_dodecafonica n =

n >= 0 ==>

all esPermutacion (toLists d)

&& all (== d!(1,1)) [d!(i,i) | i <- [2..12]]

&& sum d == 936

where xss = permutations [1..12]

k = n `mod` product [1..12]

d = matrizDodecafonica (xss !! k)

esPermutacion ys = sort ys == [1..12]

-- La comprobación es

-- λ> quickCheck prop_dodecafonica

-- +++ OK, passed 100 tests.

Pensamiento

Como el olivar,
mucho fruto lleva,
poca sombra da.

Antonio Machado

La conjetura de Collatz

PorJosé A. Alonso 9-abril-201926-marzo-2022

La conjetura de Collatz, conocida también como conjetura 3n+1, fue enunciada por Lothar Collatz en 1937 y, hasta la fecha, no se ha resuelto.

La conjetura hace referencia a una propiedad de las sucesiones de Siracusa. La sucesión de Siracusa de un número entero positivo x es la sucesión cuyo primer término es x y el siguiente de un término se obtiene dividiéndolo entre 2, si es par o multiplicándolo por 3 y sumándole 1, si es impar. Por ejemplo, la sucesión de Siracusa de 12 es

   12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, ....

1	12, 6, 3, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, 2, 1, 4, ....

La conjetura de Collatz afirma que para todo número entero positivo x, el 1 pertenece a la sucesión de Siracusa de x.

Definir las funciones

   siracusa        :: Integer -> [Integer]
   graficaSiracusa :: Int -> [Integer] -> IO ()

1 2	siracusa :: Integer -> [Integer] graficaSiracusa :: Int -> [Integer] -> IO ()

tales que

(siracusa x) es la sucesión de Siracusa de x. Por ejemplo,

     λ> take 20 (siracusa 12)
     [12,6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4]
     λ> take 20 (siracusa 22)
     [22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4]

λ> take 20 (siracusa 12)

[12,6,3,10,5,16,8,4,2,1,4,2,1,4,2,1,4,2,1,4]

λ> take 20 (siracusa 22)

[22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,4]

(graficaSiracusa n xs) dibuja los n primeros términos de las sucesiones de Siracusas de los elementos de xs. Por ejemplo, (graficaSiracusa 100 [27]) dibuja

y (graficaSiracusa 150 [1..1000]) dibuja

Comprobar con QuickCheck la conjetura de Collatz.

Soluciones

import Test.QuickCheck
import Graphics.Gnuplot.Simple

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

siracusa :: Integer -> [Integer]
siracusa n | even n    = n : siracusa (n `div` 2)
           | otherwise = n : siracusa (3*n+1)

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

siracusa2 :: Integer -> [Integer]
siracusa2 = iterate siguiente 
  where siguiente x | even x    = x `div` 2
                    | otherwise = 3*x+1

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

-- La comparación es
--    λ> siracusa 12 !! (10^6)
--    4
--    (0.55 secs, 362,791,008 bytes)
--    λ> siracusa 12 !! (2*10^6)
--    2
--    (1.05 secs, 725,456,376 bytes)
--    λ> siracusa2 12 !! (10^6)
--    4
--    (1.66 secs, 647,189,664 bytes)
--    λ> siracusa2 12 !! (2*10^6)
--    2
--    (3.11 secs, 1,294,286,792 bytes)

-- Definición de graficaSiracusa
-- =============================

graficaSiracusa :: Int -> [Integer] -> IO ()
graficaSiracusa n xs =
  plotLists [ Key Nothing
            , PNG "La_conjetura_de_Collatz.png"
            ]
            [take n (siracusa x) | x <- xs]

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

-- La conjetura es
conjeturaCollatz :: Positive Integer -> Bool
conjeturaCollatz (Positive n) =
  1 `elem` siracusa n

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

import Test.QuickCheck

import Graphics.Gnuplot.Simple

-- 1ª definición de siracusa

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

siracusa :: Integer -> [Integer]

siracusa n | even n = n : siracusa (n `div` 2)

| otherwise = n : siracusa (3*n+1)

-- 2ª definición de siracusa

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

siracusa2 :: Integer -> [Integer]

siracusa2 = iterate siguiente

where siguiente x | even x = x `div` 2

| otherwise = 3*x+1

-- Comparación de eficiencia

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

-- La comparación es

-- λ> siracusa 12 !! (10^6)

-- 4

-- (0.55 secs, 362,791,008 bytes)

-- λ> siracusa 12 !! (2*10^6)

-- 2

-- (1.05 secs, 725,456,376 bytes)

-- λ> siracusa2 12 !! (10^6)

-- 4

-- (1.66 secs, 647,189,664 bytes)

-- λ> siracusa2 12 !! (2*10^6)

-- 2

-- (3.11 secs, 1,294,286,792 bytes)

-- Definición de graficaSiracusa

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

graficaSiracusa :: Int -> [Integer] -> IO ()

graficaSiracusa n xs =

plotLists [ Key Nothing

, PNG "La_conjetura_de_Collatz.png"

]

[take n (siracusa x) | x <- xs]

-- Comprobación de la conjetura

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

-- La conjetura es

conjeturaCollatz :: Positive Integer -> Bool

conjeturaCollatz (Positive n) =

1 `elem` siracusa n

-- La comprobación es

-- λ> quickCheck conjeturaCollatz

-- +++ OK, passed 100 tests.

Pensamiento

Que el caminante es suma del camino …

Antonio Machado

Árbol binario de divisores

PorJosé A. Alonso 1-abril-201925-abril-2021

El árbol binario de los divisores de 90 es

2 45

3 15

3 5

Se puede representar por

   N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))

1	N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))

usando el tipo de dato definido por

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

data Arbol = H Int

| N Int Arbol Arbol

deriving (Eq, Show)

Análogamente se obtiene el árbol binario de cualquier número x: se comienza en x y en cada paso se tiene dos hijos (su menor divisor y su cociente) hasta obtener números primos en las hojas.

Definir las funciones

   arbolDivisores      :: Int -> Arbol
   hojasArbolDivisores :: Int -> [Int]

1 2	arbolDivisores :: Int -> Arbol hojasArbolDivisores :: Int -> [Int]

tales que

(arbolDivisores x) es el árbol binario de los divisores de x. Por ejemplo,

     λ> arbolDivisores 90
     N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))
     λ> arbolDivisores 24
     N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3)))
     λ> arbolDivisores 300
     N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5))))

λ> arbolDivisores 90

N 90 (H 2) (N 45 (H 3) (N 15 (H 3) (H 5)))

λ> arbolDivisores 24

N 24 (H 2) (N 12 (H 2) (N 6 (H 2) (H 3)))

λ> arbolDivisores 300

N 300 (H 2) (N 150 (H 2) (N 75 (H 3) (N 25 (H 5) (H 5))))

(hojasArbolDivisores x) es la lista de las hohas del árbol binario de los divisores de x. Por ejemplo

     hojasArbolDivisores 90   ==  [2,3,3,5]
     hojasArbolDivisores 24   ==  [2,2,2,3]
     hojasArbolDivisores 300  ==  [2,2,3,5,5]

hojasArbolDivisores 90 == [2,3,3,5]

hojasArbolDivisores 24 == [2,2,2,3]

hojasArbolDivisores 300 == [2,2,3,5,5]

Soluciones

import Data.Numbers.Primes (primeFactors)

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

-- Definición de arbolDivisores
-- ============================

arbolDivisores :: Int -> Arbol
arbolDivisores x
  | y == x    = H x
  | otherwise = N x (H y) (arbolDivisores (x `div` y))
  where y = menorDivisor x

-- (menorDivisor x) es el menor divisor primo de x. Por ejemplo,
--    menorDivisor 45  ==  3
--    menorDivisor 5   ==  5
menorDivisor :: Int -> Int
menorDivisor x =
  head [y | y <- [2..x], x `mod` y == 0]

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

hojasArbolDivisores :: Int -> [Int]
hojasArbolDivisores = hojas . arbolDivisores

-- (hojas a) es la lista de las hojas del árbol a. Por ejemplo,
--    hojas (N 3 (H 4) (N 5 (H 7) (H 2)))  ==  [4,7,2]
hojas :: Arbol -> [Int]
hojas (H x)     = [x]
hojas (N _ i d) = hojas i ++ hojas d

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

hojasArbolDivisores2 :: Int -> [Int]
hojasArbolDivisores2 = primeFactors

import Data.Numbers.Primes (primeFactors)

data Arbol = H Int

| N Int Arbol Arbol

deriving (Eq, Show)

-- Definición de arbolDivisores

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

arbolDivisores :: Int -> Arbol

arbolDivisores x

| y == x = H x

| otherwise = N x (H y) (arbolDivisores (x `div` y))

where y = menorDivisor x

-- (menorDivisor x) es el menor divisor primo de x. Por ejemplo,

-- menorDivisor 45 == 3

-- menorDivisor 5 == 5

menorDivisor :: Int -> Int

menorDivisor x =

head [y | y <- [2..x], x `mod` y == 0]

-- 1ª definición de hojasArbolDivisores

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

hojasArbolDivisores :: Int -> [Int]

hojasArbolDivisores = hojas . arbolDivisores

-- (hojas a) es la lista de las hojas del árbol a. Por ejemplo,

-- hojas (N 3 (H 4) (N 5 (H 7) (H 2))) == [4,7,2]

hojas :: Arbol -> [Int]

hojas (H x) = [x]

hojas (N _ i d) = hojas i ++ hojas d

-- 2ª definición de hojasArbolDivisores

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

hojasArbolDivisores2 :: Int -> [Int]

hojasArbolDivisores2 = primeFactors

Pensamiento

Entre las brevas soy blando;
entre las rocas, de piedra.
¡Malo!

Antonio Machado

Soluciones

Referencia

Pensamiento

Soluciones

Referencia

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Referencias

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Soluciones

Pensamiento

Entradas recientes

Buscar

Correo electrónico