I1M2018: Resolución de una ecuación con factoriales en Haskell

En la tercera parte de la clase de hoy del curso de Informática de 1º del Grado en Matemáticas se han explicado las soluciones de los ejercicios de la relación 28, cuyo objetivo es resolver la ecuación a! * b! = a! + b! + c!, donde a, b y c son números naturales.

Los ejercicios, y sus soluciones, se muestran a continuación.

-- ---------------------------------------------------------------------
-- Introducción                                                       --
-- ---------------------------------------------------------------------

-- El objetivo de esta relación de ejercicios es resolver la ecuación
--    a! * b! = a! + b! + c!
-- donde a, b y c son números naturales.

-- ---------------------------------------------------------------------
-- Importación de librerías auxiliares                                --
-- ---------------------------------------------------------------------

import Test.QuickCheck 

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función
--    factorial :: Integer -> Integer
-- tal que (factorial n) es el factorial de n. Por ejemplo,
--    factorial 5  ==  120
-- ---------------------------------------------------------------------

factorial :: Integer -> Integer
factorial n = product [1..n]

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la constante
--    factoriales :: [Integer]
-- tal que factoriales es la lista de los factoriales de los números
-- naturales. Por ejemplo,
--    take 7 factoriales  ==  [1,1,2,6,24,120,720]
-- ---------------------------------------------------------------------

-- 1ª definición
factoriales1 :: [Integer]
factoriales1 = [factorial n | n <- [0..]]

-- 2ª definición
factoriales2 :: [Integer]
factoriales2 = scanl (*) 1 [1..]
 
-- Comparación de eficiencia:
--    ghci> let n = factoriales !! 30000 in n-n
--    0
--    (3.20 secs, 723071452 bytes)
--    ghci> let n = factoriales2 !! 30000 in n-n
--    0
--    (3.16 secs, 721944872 bytes)
--    ghci> let n = factoriales3 !! 30000 in n-n
--    0
--    (1.74 secs, 720384724 bytes)

-- Usaremos como factoriales la 2ª definición:
factoriales :: [Integer]
factoriales = factoriales2

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir, usando factoriales, la función
--    esFactorial :: Integer -> Bool
-- tal que (esFactorial n) se verifica si existe un  número natural m
-- tal que n es m!. Por ejemplo,
--    esFactorial 120  ==  True
--    esFactorial  20  ==  False
-- ---------------------------------------------------------------------

esFactorial :: Integer -> Bool
esFactorial n = n == head (dropWhile (<n) factoriales)

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la constante
--    posicionesFactoriales :: [(Integer,Integer)]
-- tal que posicionesFactoriales es la lista de los factoriales con su
-- posición. Por ejemplo,
--    ghci> take 7 posicionesFactoriales
--    [(0,1),(1,1),(2,2),(3,6),(4,24),(5,120),(6,720)]
-- ---------------------------------------------------------------------

posicionesFactoriales :: [(Integer,Integer)]
posicionesFactoriales = zip [0..] factoriales 

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir la función
--    invFactorial :: Integer -> Maybe Integer
-- tal que (invFactorial x) es (Just n) si el factorial de n es x y es
-- Nothing, en caso contrario. Por ejemplo,
--    invFactorial 120  == Just 5
--    invFactorial 20   == Nothing
-- ---------------------------------------------------------------------

invFactorial :: Integer -> Maybe Integer
invFactorial x 
    | esFactorial x = Just (head [n | (n,y) <- posicionesFactoriales, y==x])
    | otherwise     = Nothing

-- ---------------------------------------------------------------------
-- Ejercicio 6. Definir la constante
--    pares :: [(Integer,Integer)]
-- tal que pares es la lista de todos los pares de números naturales. Por
-- ejemplo, 
--    ghci> take 11 pares
--    [(0,0),(0,1),(1,1),(0,2),(1,2),(2,2),(0,3),(1,3),(2,3),(3,3),(0,4)]
-- ---------------------------------------------------------------------

pares :: [(Integer,Integer)]
pares = [(x,y) | y <- [0..], x <- [0..y]]

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir la constante
--    solucionFactoriales :: (Integer,Integer,Integer)
-- tal que solucionFactoriales es una terna (a,b,c) que es una solución
-- de la ecuación 
--    a! * b! = a! + b! + c!
-- Calcular el valor de solucionFactoriales.
-- ---------------------------------------------------------------------

solucionFactoriales :: (Integer,Integer,Integer)
solucionFactoriales = (a,b,c)
    where (a,b)  = head [(x,y) | (x,y) <- pares,
                                 esFactorial (f x * f y - f x - f y)]
          f      = factorial 
          Just c = invFactorial (f a * f b - f a - f b)

-- El cálculo es
--    ghci> solucionFactoriales
--    (3,3,4)

-- ---------------------------------------------------------------------
-- Ejercicio 8. Comprobar con QuickCheck que solucionFactoriales es la
-- única solución de la ecuación
--    a! * b! = a! + b! + c!
-- con a, b y c números naturales
-- ---------------------------------------------------------------------

prop_solucionFactoriales :: Integer -> Integer -> Integer -> Property
prop_solucionFactoriales x y z =
    x >= 0 && y >= 0 && z >= 0 
    ==> (x,y,z) == solucionFactoriales || 
        not (f x * f y == f x + f y + f z)
    where f = factorial

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

-- ---------------------------------------------------------------------
-- Nota: El ejercicio se basa en el artículo "Ecuación con factoriales"
-- del blog Gaussianos publicado en
--    http://gaussianos.com/ecuacion-con-factoriales
-- ---------------------------------------------------------------------

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

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

-- Introducción --

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

-- El objetivo de esta relación de ejercicios es resolver la ecuación

-- a! * b! = a! + b! + c!

-- donde a, b y c son números naturales.

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

-- Importación de librerías auxiliares --

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

import Test.QuickCheck

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

-- Ejercicio 1. Definir la función

-- factorial :: Integer -> Integer

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

-- factorial 5 == 120

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

factorial :: Integer -> Integer

factorial n = product [1..n]

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

-- Ejercicio 2. Definir la constante

-- factoriales :: [Integer]

-- tal que factoriales es la lista de los factoriales de los números

-- naturales. Por ejemplo,

-- take 7 factoriales == [1,1,2,6,24,120,720]

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

-- 1ª definición

factoriales1 :: [Integer]

factoriales1 = [factorial n | n <- [0..]]

-- 2ª definición

factoriales2 :: [Integer]

factoriales2 = scanl (*) 1 [1..]

-- Comparación de eficiencia:

-- ghci> let n = factoriales !! 30000 in n-n

-- 0

-- (3.20 secs, 723071452 bytes)

-- ghci> let n = factoriales2 !! 30000 in n-n

-- 0

-- (3.16 secs, 721944872 bytes)

-- ghci> let n = factoriales3 !! 30000 in n-n

-- 0

-- (1.74 secs, 720384724 bytes)

-- Usaremos como factoriales la 2ª definición:

factoriales :: [Integer]

factoriales = factoriales2

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

-- Ejercicio 3. Definir, usando factoriales, la función

-- esFactorial :: Integer -> Bool

-- tal que (esFactorial n) se verifica si existe un número natural m

-- tal que n es m!. Por ejemplo,

-- esFactorial 120 == True

-- esFactorial 20 == False

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

esFactorial :: Integer -> Bool

esFactorial n = n == head (dropWhile (<n) factoriales)

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

-- Ejercicio 4. Definir la constante

-- posicionesFactoriales :: [(Integer,Integer)]

-- tal que posicionesFactoriales es la lista de los factoriales con su

-- posición. Por ejemplo,

-- ghci> take 7 posicionesFactoriales

-- [(0,1),(1,1),(2,2),(3,6),(4,24),(5,120),(6,720)]

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

posicionesFactoriales :: [(Integer,Integer)]

posicionesFactoriales = zip [0..] factoriales

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

-- Ejercicio 5. Definir la función

-- invFactorial :: Integer -> Maybe Integer

-- tal que (invFactorial x) es (Just n) si el factorial de n es x y es

-- Nothing, en caso contrario. Por ejemplo,

-- invFactorial 120 == Just 5

-- invFactorial 20 == Nothing

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

invFactorial :: Integer -> Maybe Integer

invFactorial x

| esFactorial x = Just (head [n | (n,y) <- posicionesFactoriales, y==x])

| otherwise = Nothing

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

-- Ejercicio 6. Definir la constante

-- pares :: [(Integer,Integer)]

-- tal que pares es la lista de todos los pares de números naturales. Por

-- ejemplo,

-- ghci> take 11 pares

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

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

pares :: [(Integer,Integer)]

pares = [(x,y) | y <- [0..], x <- [0..y]]

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

-- Ejercicio 7. Definir la constante

-- solucionFactoriales :: (Integer,Integer,Integer)

-- tal que solucionFactoriales es una terna (a,b,c) que es una solución

-- de la ecuación

-- a! * b! = a! + b! + c!

-- Calcular el valor de solucionFactoriales.

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

solucionFactoriales :: (Integer,Integer,Integer)

solucionFactoriales = (a,b,c)

where (a,b) = head [(x,y) | (x,y) <- pares,

esFactorial (f x * f y - f x - f y)]

f = factorial

Just c = invFactorial (f a * f b - f a - f b)

-- El cálculo es

-- ghci> solucionFactoriales

-- (3,3,4)

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

-- Ejercicio 8. Comprobar con QuickCheck que solucionFactoriales es la

-- única solución de la ecuación

-- a! * b! = a! + b! + c!

-- con a, b y c números naturales

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

prop_solucionFactoriales :: Integer -> Integer -> Integer -> Property

prop_solucionFactoriales x y z =

x >= 0 && y >= 0 && z >= 0

==> (x,y,z) == solucionFactoriales ||

not (f x * f y == f x + f y + f z)

where f = factorial

-- La comprobación es

-- ghci> quickCheck prop_solucionFactoriales

-- +++ OK, passed 100 tests.

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

-- Nota: El ejercicio se basa en el artículo "Ecuación con factoriales"

-- del blog Gaussianos publicado en

-- http://gaussianos.com/ecuacion-con-factoriales

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

Se puede imprimir o compartir con