Fracciones que son cuadrados perfectos

Nitesh Singh ha planteado en Mathematics Competitions el siguiente problema:

¿Cuántos números enteros n existen tales que n/(1450−n) es un cuadrado perfecto?

Vamos a generalizarlo y resolverlo con Haskell. La generalización es

Para cada número natural x, calcular los números enteros n tales que n/(x−n) es un cuadrado perfecto.

Escribiremos dos formas de resolverlo y compararemos su eficiencia.

Este ejercicio sirve para ilustrar cómo el prepocesamiento matemático puede ayudar a mejorar la eficiencia de los programas.

-- ---------------------------------------------------------------------
-- § 1ª solución                                                      --
-- ---------------------------------------------------------------------

-- Puesto que n/(x-n) es un cuadrado perfecto, se tiene que 0 ≤ n < x.

-- (soluciones1 x) es la lista de los números enteros n tales que
-- n/(x−n) es un cuadrado perfecto. Por ejemplo,
--    soluciones1 1450  ==  [0,725,1160,1305,1421,1440,1445]
soluciones1 :: Integer -> [Integer]
soluciones1 x = 
  [n | n <- [0..x-1], 
       n `rem` (x - n) == 0,
       esCuadrado (n `div` (x - n))]
  
-- (esCuadrado x) se verifica si x es un cuadrado perfecto. Por ejemplo, 
--    esCuadrado  9  ==  True
--    esCuadrado 10  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x =
  x == y^2
  where y = floor (sqrt (fromIntegral x))
        
-- ---------------------------------------------------------------------
-- § 2ª solución                                                      --
-- ---------------------------------------------------------------------

-- Puesto que n/(x-n) es un cuadrado perfecto, existe un k tal que
--    n/(x-n) = k^2
-- Luego,         
--    n = x * k^2/(k^2 + 1).     
-- Además, como n < x se tiene que k < sqrt(x).        

-- (soluciones2 x) es la lista de los números enteros n tales que
-- n/(x−n) es un cuadrado perfecto. Por ejemplo,
--    soluciones2 1450  ==  [0,725,1160,1305,1421,1440,1445]
soluciones2 :: Integer -> [Integer]
soluciones2 x =
  [x * k^2 `div` (k^2 + 1) | k <- [0..c-1], 
                             x * k^2 `rem` (k^2 + 1) == 0]
  where c = ceiling (sqrt (fromIntegral x))
        
-- ---------------------------------------------------------------------
-- § Equivalencia de las soluciones                                   --
-- ---------------------------------------------------------------------
        
-- (prop_equivalencia m) se verifica si para todos los números x entre 0
-- y m, son iguales (soluciones1 x) y (soluciones2 x). Por ejemplo,          
--    ghci> prop_equivalencia 2000
--    True
prop_equivalencia :: Integer -> Bool
prop_equivalencia m =
  and [soluciones1 x == soluciones2 x | x <- [0..m]]

-- ---------------------------------------------------------------------
-- § Comparación de la eficiencia                                     --
-- ---------------------------------------------------------------------

-- La segunda definición es más eficiente como se comprueba en el
-- siguiente ejemplo:
--    ghci> length (soluciones1 10000000)
--    5
--    (34.39 secs, 1360001588 bytes)
--    ghci> length (soluciones2 10000000)
--    5
--    (0.05 secs, 3098372 bytes)

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

-- § 1ª solución --

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

-- Puesto que n/(x-n) es un cuadrado perfecto, se tiene que 0 ≤ n < x.

-- (soluciones1 x) es la lista de los números enteros n tales que

-- n/(x−n) es un cuadrado perfecto. Por ejemplo,

-- soluciones1 1450 == [0,725,1160,1305,1421,1440,1445]

soluciones1 :: Integer -> [Integer]

soluciones1 x =

[n | n <- [0..x-1],

n `rem` (x - n) == 0,

esCuadrado (n `div` (x - n))]

-- (esCuadrado x) se verifica si x es un cuadrado perfecto. Por ejemplo,

-- esCuadrado 9 == True

-- esCuadrado 10 == False

esCuadrado :: Integer -> Bool

esCuadrado x =

x == y^2

where y = floor (sqrt (fromIntegral x))

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

-- § 2ª solución --

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

-- Puesto que n/(x-n) es un cuadrado perfecto, existe un k tal que

-- n/(x-n) = k^2

-- Luego,

-- n = x * k^2/(k^2 + 1).

-- Además, como n < x se tiene que k < sqrt(x).

-- (soluciones2 x) es la lista de los números enteros n tales que

-- n/(x−n) es un cuadrado perfecto. Por ejemplo,

-- soluciones2 1450 == [0,725,1160,1305,1421,1440,1445]

soluciones2 :: Integer -> [Integer]

soluciones2 x =

[x * k^2 `div` (k^2 + 1) | k <- [0..c-1],

x * k^2 `rem` (k^2 + 1) == 0]

where c = ceiling (sqrt (fromIntegral x))

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

-- § Equivalencia de las soluciones --

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

-- (prop_equivalencia m) se verifica si para todos los números x entre 0

-- y m, son iguales (soluciones1 x) y (soluciones2 x). Por ejemplo,

-- ghci> prop_equivalencia 2000

-- True

prop_equivalencia :: Integer -> Bool

prop_equivalencia m =

and [soluciones1 x == soluciones2 x | x <- [0..m]]

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

-- § Comparación de la eficiencia --

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

-- La segunda definición es más eficiente como se comprueba en el

-- siguiente ejemplo:

-- ghci> length (soluciones1 10000000)

-- 5

-- (34.39 secs, 1360001588 bytes)

-- ghci> length (soluciones2 10000000)

-- 5

-- (0.05 secs, 3098372 bytes)

Se puede imprimir o compartir con