Representación de 2ⁿ como 7x²+y² (con x e y impares) en Haskell

En la Olimpiada Matemática de Moscú del 1988 se propuso el siguiente problema:

Si $n \geq 3$ , entonces $2^n$ se puede representar como $2^n = 7x^2+y^2$ con x e y impares.

En la siguiente relación de ejercicios (elaborada para la asignatura de Informática de 1º del Grado en Matemáticas) se resuelve el problema con Haskell.

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función
--     paresDeImpares :: [(Integer,Integer)]
-- tal que paresDeImpares es la lista de pares de números impares. Por
-- ejemplo,  
--    ghci> take 10 paresDeImpares
--    [(1,1),(1,3),(3,1),(1,5),(3,3),(5,1),(1,7),(3,5),(5,3),(7,1)]
-- ---------------------------------------------------------------------

paresDeImpares :: [(Integer,Integer)]
paresDeImpares = 
    [(x,y) | n <- [1..], x <- [1,3..n], let y = n-x, odd y]

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función
--    solucion1 :: Integer -> (Integer,Integer)
-- tal que (solucion1 n) es una solución de la ecuación 2^n =
-- 7*x^2+y^2. Por ejemplo, 
--    solucion1 3  ==  (1,1)
--    solucion1 8  ==  (5,9)
-- ---------------------------------------------------------------------

solucion1 :: Integer -> (Integer,Integer)
solucion1 n = 
    head [(x,y) | (x,y) <- paresDeImpares, 2^n == 7*x^2+y^2]

-- ---------------------------------------------------------------------
-- Ejercicio 3. Calcular las soluciones de 2^n = 7*x^2+y^2 para n entre
-- 3 y 10.
-- ---------------------------------------------------------------------

-- El cálculo es
--    ghci> [(n,solucion1 n) | n <- [3..10]]
--    [(3,(1,1)), (4,(1,3)),(5,(1,5)), (6,(3,1)),
--     (7,(1,11)),(8,(5,9)),(9,(7,13)),(10,(3,31))]

-- ---------------------------------------------------------------------
-- Ejercicio 4. A partir del cálculo anterior conjeturar cómo se obtiene
-- la solución de m+1 a partir de la de m.
-- ---------------------------------------------------------------------

-- Sean (x,y) y (x',y') las soluciones de 2^n = 7*x^2+y^2  cuando n es m
-- y m+1, respectivamente. Se trata de encontrar cómo obtener (x',y') a
-- partir de (x,y).
-- 
-- A partir de las soluciones anteriores podemos obtener la siguiente
-- tabla
--
--     n | x |  y | (x+y)/2 | |7x-y|/2 | |x-y|/2 | (7x+y)/2
--   ----+---+----+---------+----------+---------+---------- 
--     3 | 1 |  1 | 1       | 3        |         |
--     4 | 1 |  3 |         |          | 1       | 5
--     5 | 1 |  5 | 3       | 1        |         |  
--     6 | 3 |  1 |         |          | 1       | 11
--     7 | 1 | 11 |         |          | 5       | 9
--     8 | 5 |  9 | 7       | 13       |         | 
--     9 | 7 | 13 |         |          | 3       | 31
--    10 | 3 | 31 | 17      | 5        |         | 
-- 
-- Se observa que x' = (x+y)/2 para m en {3,5,8}; es decir, en los
-- casos en que (x+y)/2 es impar. En estos casos, y' = |7x-y|/2.
-- 
-- En el caso de que (x+y)/2 es par (es decir para m en {4,6,7,9}), se
-- tiene que x' = |x-y|/2 e y' = (7x+y)/2. 

-- ---------------------------------------------------------------------
-- Ejercicio 5. Definir, usando la conjetura de ejercicio 4, la función
--    solucion2 :: Integer -> (Integer,Integer)
-- tal que (solucion2 n) es una solución de la ecuación 2^n =
-- 7*x^2+y^2. Por ejemplo, 
--    solucion2 3  ==  (1,1)
--    solucion2 8  ==  (5,9)
-- ---------------------------------------------------------------------

solucion2 :: Integer -> (Integer,Integer)
solucion2 3 = (1,1)
solucion2 n | odd media = (media, abs (7*x-y) `div` 2)
            | otherwise  = (abs (x-y) `div` 2, (7*x+y) `div` 2)
            where (x,y) = solucion2 (n-1)
                  media = (x+y) `div` 2

-- ---------------------------------------------------------------------
-- Ejercicio 6. Comprobar la equivalencia de las funciones solucion1 y
-- solucion2 para n entre 3 y 10.
-- ---------------------------------------------------------------------

-- La comprobación es
--    ghci> and [solucion1 n == solucion2 n | n <- [3..10]]
--    True

-- ---------------------------------------------------------------------
-- Ejercicio 7. Comparar la eficiencia de las funciones solucion1 y
-- solucion2 para n = 28.
-- ---------------------------------------------------------------------

-- La comparación es
--    ghci> solucion1 28
--    (181,16377)
--    (299.50 secs, 42599321084 bytes)
--    ghci> solucion2 28
--    (181,16377)
--    (0.00 secs, 525644 bytes)

-- ---------------------------------------------------------------------
-- Ejercicio 8. Demostrar que la solucion2 es correcta; es decir, que
-- para n >= 3, si (solucion2 n) es (x,y) entonces 2^n = 7*x^2+y^2.
-- ---------------------------------------------------------------------

-- Se demuestra por inducción en n.
-- 
-- Base (n=3). Para n=3, (solucion2 n) es (1,1) y 2^3 = 7*1^2+1^2.
--
-- Paso. Supongamos que se cumple para n; es decir que (solucion2 n) es
-- (x,y) y 2^n = 7*x^2+y^2. Sea (u,v) = (solucion2 (n+1)). hay que
-- demostrar que 2^(n+1) = 7*u^2+v^2. Distinguiremos dos casos según la
-- paridad de (x+y)/2.
-- 
-- Caso 1. Supongamos que (x+y)/2 es impar, entonces u = (x+y)/2 y 
-- v = |7x-y|/2. Por tanto,
--     7*u^2+v^2 = 7*((x+y)/2)^2 + (|7x-y|/2)^2
--               = 7*(x^2+2xy+y^2)/4 + (49x^2-14xy+y^2)/4
--               = (56x^2+8y^2)/4
--               = 14x^2+2y^2
--               = 2(7x^2+y^2)
--               = 2*2^n             [por la hipótesis de inducción]
--               = 2^(n+1)
-- 
-- Caso 2. Supongamos que (x+y)/2 es par, entonces u = |x-y|/2 y 
-- v = (7x+y)/2. Por tanto,
--     7*u^2+v^2 = 7*(|x-y|/2)^2 + ((7x+y)/2)^2
--               = 7*(x^2-2xy+y^2)/4 + (49x^2+14xy+y^2)/4
--               = (56x^2+8y^2)/4
--               = 14x^2+2y^2
--               = 2(7x^2+y^2)
--               = 2*2^n             [por la hipótesis de inducción]
--               = 2^(n+1)

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

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

-- Ejercicio 1. Definir la función

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

-- tal que paresDeImpares es la lista de pares de números impares. Por

-- ejemplo,

-- ghci> take 10 paresDeImpares

-- [(1,1),(1,3),(3,1),(1,5),(3,3),(5,1),(1,7),(3,5),(5,3),(7,1)]

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

paresDeImpares :: [(Integer,Integer)]

paresDeImpares =

[(x,y) | n <- [1..], x <- [1,3..n], let y = n-x, odd y]

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

-- Ejercicio 2. Definir la función

-- solucion1 :: Integer -> (Integer,Integer)

-- tal que (solucion1 n) es una solución de la ecuación 2^n =

-- 7*x^2+y^2. Por ejemplo,

-- solucion1 3 == (1,1)

-- solucion1 8 == (5,9)

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

solucion1 :: Integer -> (Integer,Integer)

solucion1 n =

head [(x,y) | (x,y) <- paresDeImpares, 2^n == 7*x^2+y^2]

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

-- Ejercicio 3. Calcular las soluciones de 2^n = 7*x^2+y^2 para n entre

-- 3 y 10.

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

-- El cálculo es

-- ghci> [(n,solucion1 n) | n <- [3..10]]

-- [(3,(1,1)), (4,(1,3)),(5,(1,5)), (6,(3,1)),

-- (7,(1,11)),(8,(5,9)),(9,(7,13)),(10,(3,31))]

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

-- Ejercicio 4. A partir del cálculo anterior conjeturar cómo se obtiene

-- la solución de m+1 a partir de la de m.

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

-- Sean (x,y) y (x',y') las soluciones de 2^n = 7*x^2+y^2 cuando n es m

-- y m+1, respectivamente. Se trata de encontrar cómo obtener (x',y') a

-- partir de (x,y).

-- A partir de las soluciones anteriores podemos obtener la siguiente

-- tabla

-- n | x | y | (x+y)/2 | |7x-y|/2 | |x-y|/2 | (7x+y)/2

-- ----+---+----+---------+----------+---------+----------

-- 3 | 1 | 1 | 1 | 3 | |

-- 4 | 1 | 3 | | | 1 | 5

-- 5 | 1 | 5 | 3 | 1 | |

-- 6 | 3 | 1 | | | 1 | 11

-- 7 | 1 | 11 | | | 5 | 9

-- 8 | 5 | 9 | 7 | 13 | |

-- 9 | 7 | 13 | | | 3 | 31

-- 10 | 3 | 31 | 17 | 5 | |

-- Se observa que x' = (x+y)/2 para m en {3,5,8}; es decir, en los

-- casos en que (x+y)/2 es impar. En estos casos, y' = |7x-y|/2.

-- En el caso de que (x+y)/2 es par (es decir para m en {4,6,7,9}), se

-- tiene que x' = |x-y|/2 e y' = (7x+y)/2.

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

-- Ejercicio 5. Definir, usando la conjetura de ejercicio 4, la función

-- solucion2 :: Integer -> (Integer,Integer)

-- tal que (solucion2 n) es una solución de la ecuación 2^n =

-- 7*x^2+y^2. Por ejemplo,

-- solucion2 3 == (1,1)

-- solucion2 8 == (5,9)

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

solucion2 :: Integer -> (Integer,Integer)

solucion2 3 = (1,1)

solucion2 n | odd media = (media, abs (7*x-y) `div` 2)

| otherwise = (abs (x-y) `div` 2, (7*x+y) `div` 2)

where (x,y) = solucion2 (n-1)

media = (x+y) `div` 2

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

-- Ejercicio 6. Comprobar la equivalencia de las funciones solucion1 y

-- solucion2 para n entre 3 y 10.

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

-- La comprobación es

-- ghci> and [solucion1 n == solucion2 n | n <- [3..10]]

-- True

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

-- Ejercicio 7. Comparar la eficiencia de las funciones solucion1 y

-- solucion2 para n = 28.

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

-- La comparación es

-- ghci> solucion1 28

-- (181,16377)

-- (299.50 secs, 42599321084 bytes)

-- ghci> solucion2 28

-- (181,16377)

-- (0.00 secs, 525644 bytes)

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

-- Ejercicio 8. Demostrar que la solucion2 es correcta; es decir, que

-- para n >= 3, si (solucion2 n) es (x,y) entonces 2^n = 7*x^2+y^2.

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

-- Se demuestra por inducción en n.

-- Base (n=3). Para n=3, (solucion2 n) es (1,1) y 2^3 = 7*1^2+1^2.

-- Paso. Supongamos que se cumple para n; es decir que (solucion2 n) es

-- (x,y) y 2^n = 7*x^2+y^2. Sea (u,v) = (solucion2 (n+1)). hay que

-- demostrar que 2^(n+1) = 7*u^2+v^2. Distinguiremos dos casos según la

-- paridad de (x+y)/2.

-- Caso 1. Supongamos que (x+y)/2 es impar, entonces u = (x+y)/2 y

-- v = |7x-y|/2. Por tanto,

-- 7*u^2+v^2 = 7*((x+y)/2)^2 + (|7x-y|/2)^2

-- = 7*(x^2+2xy+y^2)/4 + (49x^2-14xy+y^2)/4

-- = (56x^2+8y^2)/4

-- = 14x^2+2y^2

-- = 2(7x^2+y^2)

-- = 2*2^n [por la hipótesis de inducción]

-- = 2^(n+1)

-- Caso 2. Supongamos que (x+y)/2 es par, entonces u = |x-y|/2 y

-- v = (7x+y)/2. Por tanto,

-- 7*u^2+v^2 = 7*(|x-y|/2)^2 + ((7x+y)/2)^2

-- = 7*(x^2-2xy+y^2)/4 + (49x^2+14xy+y^2)/4

-- = (56x^2+8y^2)/4

-- = 14x^2+2y^2

-- = 2(7x^2+y^2)

-- = 2*2^n [por la hipótesis de inducción]

-- = 2^(n+1)

Se puede imprimir o compartir con