Menu Close

Etiqueta: div

Los números de Smith

Un número de Smith es un número natural compuesto que cumple que la suma de sus dígitos es igual a la suma de los dígitos de todos sus factores primos (si tenemos algún factor primo repetido lo sumamos tantas veces como aparezca). Por ejemplo, el 22 es un número de Smith ya que

    22 = 2*11 y
   2+2 = 2+(1+1)

y el 4937775 también lo es ya que

   4937775       = 3*5*5*65837 y 
   4+9+3+7+7+7+5 = 3+5+5+(6+5+8+3+7)

Definir las funciones

   esSmith :: Integer -> Bool
   smith :: [Integer]

tales que

  • (esSmith x) se verifica si x es un número de Smith. Por ejemplo,
     esSmith 22          ==  True
     esSmith 29          ==  False
     esSmith 2015        ==  False
     esSmith 4937775     ==  True
     esSmith 4567597056  ==  True
  • smith es la lista cuyos elementos son los números de Smith. Por ejemplo,
     λ> take 17 smith
     [4,22,27,58,85,94,121,166,202,265,274,319,346,355,378,382,391]
     λ> smith !! 2000
     62158

Soluciones

import Data.Numbers.Primes
 
esSmith :: Integer -> Bool
esSmith x = 
    not (isPrime x) && 
    sumaDigitos x == sum (map sumaDigitos (primeFactors x))
 
sumaDigitos :: Integer -> Integer
sumaDigitos x | x < 10 = x
              | otherwise = x `mod` 10 + sumaDigitos (x `div` 10)
 
smith :: [Integer]
smith = [x | x <- [1..], esSmith x]

Mayor semiprimo menor que n

Un número semiprimo es un número natural que es producto de dos números primos no necesariamente distintos. Por ejemplo, 26 es semiprimo (porque 26 = 2*13 ) y 49 también lo es (porque 49 = 7*7).

Definir la función

   mayorSemiprimoMenor :: Integer -> Integer

tal que (mayorSemiprimoMenor n) es el mayor semiprimo menor que n (suponiendo que n > 4). Por ejemplo,

   mayorSemiprimoMenor 27      ==  26
   mayorSemiprimoMenor 50      ==  49
   mayorSemiprimoMenor 49      ==  46
   mayorSemiprimoMenor (10^6)  ==  999997

Soluciones

import Data.Numbers.Primes (primes, isPrime)
 
-- 1ª definición
-- =============
 
mayorSemiprimoMenor :: Integer -> Integer
mayorSemiprimoMenor n =
    head [x | x <- [n-1,n-2..2], semiPrimo x]
 
semiPrimo :: Integer -> Bool
semiPrimo n =
    not (null [x | x <- [n,n-1..2], 
                   primo x,
                   n `mod` x == 0,
                   primo (n `div` x)])
 
primo :: Integer -> Bool
primo n = [x | x <- [1..n], n `mod` x == 0] == [1,n] 
 
-- 2ª definición
-- =============
 
mayorSemiprimoMenor2 :: Integer -> Integer
mayorSemiprimoMenor2 n =
    head [x | x <- [n-1,n-2..2], semiPrimo2 x]
 
semiPrimo2 :: Integer -> Bool
semiPrimo2 n =
    not (null [x | x <- [n-1,n-2..2], 
                   isPrime x,
                   n `mod` x == 0,
                   isPrime (n `div` x)])
 
-- 3ª definición
-- =============
 
mayorSemiprimoMenor3 :: Integer -> Integer
mayorSemiprimoMenor3 n =
    head [x | x <- [n-1,n-2..2], semiPrimo3 x]
 
semiPrimo3 :: Integer -> Bool
semiPrimo3 n =
    not (null [x | x <- reverse (takeWhile (<n) primes),
                   n `mod` x == 0,
                   isPrime (n `div` x)])
 
-- Comparación de eficiencia
-- =========================
 
--    λ> mayorSemiprimoMenor 2000
--    1994
--    (2.32 secs, 329,036,016 bytes)
--    λ> mayorSemiprimoMenor2 2000
--    1994
--    (0.13 secs, 81,733,304 bytes)
--    λ> mayorSemiprimoMenor3 2000
--    1994
--    (0.02 secs, 0 bytes)

Productos de N números consecutivos

La semana pasada se planteó en Twitter el siguiente problema

Se observa que

      1x2x3x4 = 2x3x4 
      2x3x4x5 = 4x5x6

¿Existen ejemplos de otros productos de cuatro enteros consecutivos iguales a un producto de tres enteros consecutivos?

Definir la función

   esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer

tal que (esProductoDeNconsecutivos n x) es (Just m) si x es el producto de n enteros consecutivos a partir de m y es Nothing si x no es el producto de n enteros consecutivos. Por ejemplo,

   esProductoDeNconsecutivos 3   6  == Just 1
   esProductoDeNconsecutivos 4   6  == Nothing
   esProductoDeNconsecutivos 4  24  == Just 1
   esProductoDeNconsecutivos 3  24  == Just 2
   esProductoDeNconsecutivos 3 120  == Just 4
   esProductoDeNconsecutivos 4 120  == Just 2

Para ejemplos mayores,

   λ> esProductoDeNconsecutivos 3 (product [10^20..2+10^20])
   Just 100000000000000000000
   λ> esProductoDeNconsecutivos2 4 (product [10^20..2+10^20])
   Nothing
   λ> esProductoDeNconsecutivos2 4 (product [10^20..3+10^20])
   Just 100000000000000000000

Usando la función esProductoDeNconsecutivos resolver el problema.

Soluciones

import Data.Maybe
 
-- 1ª definición
esProductoDeNconsecutivos1 :: Integer -> Integer -> Maybe Integer
esProductoDeNconsecutivos1 n x 
    | null productos = Nothing
    | otherwise      = Just (head productos)
    where productos = [m | m <- [1..x-n], product [m..m+n-1] == x]
 
-- 2ª definición
esProductoDeNconsecutivos2 :: Integer -> Integer -> Maybe Integer
esProductoDeNconsecutivos2 n x = aux k
    where k = floor (fromIntegral x ** (1/(fromIntegral n))) - (n `div` 2)
          aux m | y == x    = Just m
                | y <  x    = aux (m+1)
                | otherwise = Nothing
                where y = product [m..m+n-1]
 
-- Comparación de eficiencia
--    λ> esProductoDeNconsecutivos1 3 (product [10^7..2+10^7])
--    Just 10000000
--    (12.37 secs, 5678433692 bytes)
--    λ> esProductoDeNconsecutivos2 3 (product [10^7..2+10^7])
--    Just 10000000
--    (0.00 secs, 1554932 bytes)
 
-- Solución del problema
-- =====================
 
soluciones :: [Integer]
soluciones = [x | x <- [121..]
                , isJust (esProductoDeNconsecutivos2 4 x)
                , isJust (esProductoDeNconsecutivos2 3 x)]
 
-- El cálculo es
--    λ> head soluciones
--    175560
--    λ> esProductoDeNconsecutivos2 4 175560
--    Just 19
--    λ> esProductoDeNconsecutivos2 3 175560
--    Just 55
--    λ> product [19,20,21,22] 
--    175560
--    λ> product [55,56,57]
--    175560
--    λ> product [19,20,21,22] == product [55,56,57]
--    True
 
-- Se puede definir una función para automatizar el proceso anterior:
soluciones2 :: [(Integer,[Integer],[Integer])]
soluciones2 = [(x,[a..a+3],[b..b+2]) 
               | x <- [121..]
               , let y = esProductoDeNconsecutivos2 4 x
               , isJust y
               , let z = esProductoDeNconsecutivos2 3 x
               , isJust z
               , let a = fromJust y
               , let b = fromJust z
               ]
 
-- El cálculo es 
--    λ> head soluciones2
--    (175560,[19,20,21,22],[55,56,57])

Ceros finales del factorial

Definir la función

   cerosDelFactorial :: Integer -> Integer

tal que (cerosDelFactorial n) es el número de ceros en que termina el factorial de n. Por ejemplo,

   cerosDelFactorial 24                           ==  4
   cerosDelFactorial 25                           ==  6
   length (show (cerosDelFactorial (1234^5678)))  ==  17552

Soluciones

import Data.List (genericLength)
 
-- 1ª definición
-- =============
 
cerosDelFactorial1 :: Integer -> Integer
cerosDelFactorial1 n = ceros (factorial n)
 
-- (factorial n) es el factorial n. Por ejemplo,
--    factorial 3  ==  6
factorial :: Integer -> Integer
factorial n = product [1..n]
 
-- (ceros n) es el número de ceros en los que termina el número n. Por
-- ejemplo, 
--    ceros 320000  ==  4
ceros :: Integer -> Integer
ceros n | rem n 10 /= 0 = 0
        | otherwise     = 1 + ceros (div n 10)
 
-- 2ª definición
-- =============
 
cerosDelFactorial2 :: Integer -> Integer
cerosDelFactorial2 n = ceros2 (factorial n)
 
-- (ceros n) es el número de ceros en los que termina el número n. Por
-- ejemplo, 
--    ceros 320000  ==  4
ceros2 :: Integer -> Integer
ceros2 n = genericLength (takeWhile (=='0') (reverse (show n)))
 
-- 3ª definición
-- =============
 
cerosDelFactorial3 :: Integer -> Integer
cerosDelFactorial3 n | n < 5     = 0
                     | otherwise = m + cerosDelFactorial3 m
                     where m = n `div` 5
 
-- Comparación de la eficiencia
--    λ> cerosDelFactorial1 (3*10^4)
--    7498
--    (3.96 secs, 1,252,876,376 bytes)
--    λ> cerosDelFactorial2 (3*10^4)
--    7498
--    (3.07 secs, 887,706,864 bytes)
--    λ> cerosDelFactorial3 (3*10^4)
--    7498
--    (0.03 secs, 9,198,896 bytes)

Primos gemelos próximos a múltiplos de 6

Un par de números primos (p,q) es un par de números primos gemelos si su distancia de 2; es decir, si q = p+2. Por ejemplo, (17,19) es una par de números primos gemelos.

Se dice que un par de números (x,y) está próximo a un múltiplo de 6 si es de la forma (6*n-1,6*n+1). Por ejemplo, (17,19) está cerca de un múltiplo de 6 porque (17,19) = (6*3-1,6*3+1).

Definir las funciones

   primosGemelos :: Integer -> [(Integer,Integer)]
   primosGemelosNoProximosAmultiplosDe6 :: Integer -> [(Integer,Integer)]

tales que

  • (primosGemelos n) es la lista de los primos gemelos menores que n. Por ejemplo,
     primosGemelos 50  == [(3,5),(5,7),(11,13),(17,19),(29,31),(41,43)]
     primosGemelos 43  == [(3,5),(5,7),(11,13),(17,19),(29,31)]
  • (primosGemelosNoProximosAmultiplosDe6 n) es la lista de los primos gemelos menores que n que no están próximos a un múltiplo de 6. Por ejemplo,
     primosGemelosNoProximosAmultiplosDe6 50              == [(3,5)]
     length (primosGemelosNoProximosAmultiplosDe6 (10^9)) == 1

Soluciones

primosGemelos :: Integer -> [(Integer,Integer)]
primosGemelos n = [(x,x+2) | x <- [3,5..n-3], 
                             primo x,
                             primo (x+2)]
 
primo :: Integer -> Bool
primo n = divisores n == [1,n]
 
divisores :: Integer -> [Integer]
divisores n = [x | x <- [1..n], n `mod` x == 0]
 
proximosAmultiplosDe6 :: (Integer,Integer) -> Bool
proximosAmultiplosDe6 (x,y) =
    (x+1) `mod` 6 == 0 && y == 6*n+1
    where n = (x+1) `div` 6
 
primosGemelosNoProximosAmultiplosDe6 :: Integer -> [(Integer,Integer)]
primosGemelosNoProximosAmultiplosDe6 n =
    [p | p <- primosGemelos n,
         not (proximosAmultiplosDe6 p)]
 
 
-- Experimentado con primosGemelosNProximosAmultiplosDe6
--    primosGemelosNoProximosAmultiplosDe6 50    == [(3,5)]
--    primosGemelosNoProximosAmultiplosDe6 500   == [(3,5)]
--    primosGemelosNoProximosAmultiplosDe6 5000  == [(3,5)]
-- se observa que el único par de primos gemelos no próximos a múltiplos
-- de 6 es el (3,5). Su demostración es la siguiente:
--
-- Para cualquier n > 3, se tiene que de los tres números n-1, n. n+1
-- uno es divisible por 2 y alguno es divisible por 3. Si n-1 y n+1 son
-- primos, entonces el que es divisible por 2 y por 3 es n y, por tanto,
-- n es divisible por 6 y (n-1,n+1) están próximos a un múltiplo de 6.
 
-- Usando la propiedad tenemos una definición más eficiente
primosGemelosNoProximosAmultiplosDe6' :: Integer -> [(Integer,Integer)]
primosGemelosNoProximosAmultiplosDe6' n = [(3,5)]

Números muy divisibles por 3

Se dice que un número n es muy divisible por 3 si es divisible por 3 y sigue siendo divisible por 3 si vamos quitando dígitos por la derecha. Por ejemplo, 96060 es muy divisible por 3 porque 96060, 9606, 960, 96 y 9 son todos divisibles por 3.

Definir las funciones

   muyDivPor3             :: Integer -> Bool
   numeroMuyDivPor3Cifras :: Integer -> Integer

tales que

  • (muyDivPor3 n) se verifica si n es muy divisible por 3. Por ejemplo,
     muyDivPor3 96060 == True
     muyDivPor3 90616 == False
  • (numeroMuyDivPor3CifrasC k) es la cantidad de números de k cifras muy divisibles por 3. Por ejemplo,
     numeroMuyDivPor3Cifras 5                    == 768
     numeroMuyDivPor3Cifras 7                    == 12288
     numeroMuyDivPor3Cifras (10^6) `rem` (10^6)  == 332032

Soluciones

import Data.List (genericLength)
 
muyDivPor3 :: Integer -> Bool
muyDivPor3 n 
    | n < 10    = n `rem` 3 == 0
    | otherwise = n `rem` 3 == 0 && muyDivPor3 (n `div` 10)
 
-- 1ª definición
-- =============
 
numeroMuyDivPor3Cifras :: Integer -> Integer
numeroMuyDivPor3Cifras k = 
    genericLength [x | x <- [10^(k-1)..10^k-1], muyDivPor3 x]
 
-- 2ª definición
-- =============
 
numeroMuyDivPor3Cifras2 :: Integer -> Integer
numeroMuyDivPor3Cifras2 k = 
    genericLength [x | x <- [n,n+3..10^k-1], muyDivPor3 x]
    where n = k*10^(k-1)
 
-- 3ª definición
-- =============
 
numeroMuyDivPor3Cifras3 :: Integer -> Integer
numeroMuyDivPor3Cifras3 k = genericLength (numeroMuyDivPor3Cifras3a k)
 
numeroMuyDivPor3Cifras3a :: Integer -> [Integer]
numeroMuyDivPor3Cifras3a 1 = [3,6,9] 
numeroMuyDivPor3Cifras3a k = 
    [10*x+y | x <- numeroMuyDivPor3Cifras3a (k-1),
              y <- [0,3..9]]
 
-- 4ª definición
-- =============
 
numeroMuyDivPor3Cifras4 :: Integer -> Integer
numeroMuyDivPor3Cifras4 1 = 3
numeroMuyDivPor3Cifras4 k = 4 * numeroMuyDivPor3Cifras4 (k-1)
 
-- 5ª definición
-- =============
 
numeroMuyDivPor3Cifras5 :: Integer -> Integer
numeroMuyDivPor3Cifras5 k = 3 * 4^(k-1)
 
-- Comparación de eficiencia
-- =========================
 
--    λ> numeroMuyDivPor3Cifras 6
--    3072
--    (3.47 secs, 534,789,608 bytes)
--    λ> numeroMuyDivPor3Cifras2 6
--    2048
--    (0.88 secs, 107,883,432 bytes)
--    λ> numeroMuyDivPor3Cifras3 6
--    3072
--    (0.01 secs, 0 bytes)
--    
--    λ> numeroMuyDivPor3Cifras2 7
--    0
--    (2.57 secs, 375,999,336 bytes)
--    λ> numeroMuyDivPor3Cifras3 7
--    12288
--    (0.02 secs, 0 bytes)
--    λ> numeroMuyDivPor3Cifras4 7
--    12288
--    (0.00 secs, 0 bytes)
--    λ> numeroMuyDivPor3Cifras5 7
--    12288
--    (0.01 secs, 0 bytes)
--
--    λ> numeroMuyDivPor3Cifras4 (10^5) `rem` 100000
--    32032
--    (5.74 secs, 1,408,600,592 bytes)
--    λ> numeroMuyDivPor3Cifras5 (10^5) `rem` 100000
--    32032
--    (0.02 secs, 0 bytes)

Próximos a múltiplos de 6

Se dice que un par de números (x,y) está próximo a un múltiplo de 6 si es de la forma (6*n-1,6*n+1). Por ejemplo, (17,19) está cerca de un múltiplo de 6 porque (17,19) = (6*3-1,6*3+1).

Definir la función

   proximosAmultiplosDe6 :: (Integer,Integer) -> Bool

tal que (proximosAmultiplosDe6 (x,y)) se verifica si el par (x,y) está próximo a un múltiplo de 6. Por ejemplo,

   proximosAmultiplosDe6 (17,19)                          ==  True
   proximosAmultiplosDe6 (18,20)                          ==  False
   proximosAmultiplosDe6 (5,19)                           ==  False
   proximosAmultiplosDe6 (1,3)                            ==  False
   proximosAmultiplosDe6 (74074073407403,74074073407405)  ==  True
   proximosAmultiplosDe6 (86419752308637,86419752308639)  ==  False

Soluciones

-- 1ª solución
proximosAmultiplosDe6 :: (Integer,Integer) -> Bool
proximosAmultiplosDe6 (x,y) =
    (x+1) `mod` 6 == 0 && y == 6*n+1
    where n = (x+1) `div` 6
 
-- 2ª solución
proximosAmultiplosDe6' :: (Integer,Integer) -> Bool
proximosAmultiplosDe6' (a,b) = 
    a+1 == b-1 && mod (a+b) 6 == 0

Entero positivo con ciertas propiedades

El 6 de octubre, se propuso en el blog Gaussianos el siguiente problema

Demostrar que para todo entero positivo n, existe otro entero positivo que tiene las siguientes propiedades:

  1. Tiene exactamente n dígitos.
  2. Ninguno de sus dígitos es 0.
  3. Es divisible por la suma de sus dígitos.

Definir la función

   especiales :: Integer -> [Integer]

tal que (especiales n) es la lista de los números enteros que cumplen las 3 propiedades anteriores para n. Por ejemplo,

   take 3 (especiales 2)  ==  [12,18,21]
   take 3 (especiales 3)  ==  [111,112,114]
   head (especiales 30)   ==  111111111111111111111111111125
   length (especiales 3)  ==  108
   null (especiales 1000) ==  False

En el primer ejemplo, 12 es un número especial para 2 ya que tiene exactamente 2 dígitos, ninguno de sus dígitos es 0 y 12 es divisible por la suma de sus dígitos.

Soluciones

especiales :: Integer -> [Integer]
especiales n = [x | x <- [(10^n-1) `div` 9..10^n-1]
                  , esEspecial x]
 
esEspecial :: Integer -> Bool
esEspecial x = 
    notElem 0 digitos &&
    x `mod` sum digitos == 0        
    where digitos = [read [d] | d <- show x]

Con mínimo común denominador

Los números racionales se pueden representar como pares de enteros:

   type Racional a = (a,a)

Definir la función

   reducida :: Integral a => [Racional a] -> [Racional a]

tal que (reducida xs) es la lista de los números racionales donde cada uno es igual al correspondiente elemento de xs y el denominador de todos los elementos de (reducida xs) es el menor número que cumple dicha condición; es decir, si xs es la lista

   [(x_1, y_1), ..., (x_n, y_n)]

entonces (reducida xs) es

   [(z_1, d), ..., (z_n, d)]

tales que

   z_1/d = x_1/y_1, ..., z_n/d = x_n/y_n

y d es el menor posible. Por ejemplo,

   reducida [(1,2),(1,3),(1,4)]  ==  [(6,12),(4,12),(3,12)]
   reducida [(1,2),(1,3),(6,4)]  ==  [(3,6),(2,6),(9,6)]
   reducida [(-7,6),(-10,-8)]    ==  [(-14,12),(15,12)]
   reducida [(8,12)]             ==  [(2,3)]

Soluciones

type Racional a = (a,a) 
 
reducida :: Integral a => [Racional a] -> [Racional a]
reducida xs = 
    [(x * (m `div` y), m) | (x,y) <- ys]
    where ys = map fraccionReducida xs
          m  = mcm [y | (_,y) <- ys]
 
-- (fraccionReducida r) es el número racional igual a r con menor
-- denominador positivo. Por ejemplo,
--    fraccionReducida ( 6, 10)  ==  ( 3,5)
--    fraccionReducida (-6, 10)  ==  (-3,5)
--    fraccionReducida ( 6,-10)  ==  (-3,5)
--    fraccionReducida (-6,-10)  ==  ( 3,5)
--    fraccionReducida ( 3,  5)  ==  ( 3,5)
fraccionReducida :: Integral a => (a,a) -> (a,a)
fraccionReducida (x,y) =
    (s * x1 `div` m, y1 `div` m)
    where s  = signum x * signum y      
          x1 = abs x
          y1 = abs y
          m  = gcd x1 y1
 
-- (mcm xs) es el mínimo común múltiplo de xs. Por ejemplo,
--    mcm [2,6,10]  ==  30
mcm :: Integral a => [a] -> a
mcm = foldl lcm 1

Perímetro más frecuente de triángulos rectángulos

El grado perimetral de un número p es la cantidad de tres triángulos rectángulos de lados enteros cuyo perímetro es p. Por ejemplo, el grado perimetral de 120 es 3 ya que sólo hay 3 triángulos rectángulos de lados enteros cuyo perímetro es 120: {20,48,52}, {24,45,51} y {30,40,50}.

Definir la función

   maxGradoPerimetral :: Int -> (Int,[Int])

tal que (maxGradoPerimetral n) es el par (m,ps) tal que m es el máximo grado perimetral de los números menores o iguales que n y ps son los perímetros, menores o iguales que n, cuyo grado perimetral es m. Por ejemplo,

   maxGradoPerimetral   50  ==  (1,[12,24,30,36,40,48])
   maxGradoPerimetral  100  ==  (2,[60,84,90])
   maxGradoPerimetral  200  ==  (3,[120,168,180])
   maxGradoPerimetral  400  ==  (4,[240,360])
   maxGradoPerimetral  500  ==  (5,[420])
   maxGradoPerimetral  750  ==  (6,[720])
   maxGradoPerimetral  839  ==  (6,[720])
   maxGradoPerimetral  840  ==  (8,[840])
   maxGradoPerimetral 1500  ==  (8,[840,1260])
   maxGradoPerimetral 2000  ==  (10,[1680])
   maxGradoPerimetral 3000  ==  (12,[2520])

Soluciones

import Data.List
import Data.Array (accumArray, assocs)
 
-- 1ª solución                                                      --
-- ===========
 
maxGradoPerimetral1 :: Int -> (Int,[Int])
maxGradoPerimetral1 p = (m,[x | (n,x) <- ts, n == m])
    where ts    = [(length (triangulos x),x) | x <- [1..p]] 
          (m,_) = maximum ts 
 
-- (triangulos p) es el conjunto de triángulos rectángulos de perímetro
-- p. Por ejemplo,
--    triangulos 120  ==  [(20,48,52),(24,45,51),(30,40,50)]
triangulos :: Int -> [(Int,Int,Int)]
triangulos p = 
    [(a,b,c) | a <- [1..q],
               b <- [a..q],
               let c = p-a-b,
               a*a+b*b == c*c]
    where q = p `div` 2
 
-- 2ª solución                                                      --
-- ===========
 
maxGradoPerimetral2 :: Int -> (Int,[Int])
maxGradoPerimetral2 p = (m,[x | (n,x) <- ts, n == m])
    where ts    = [(n,x) | (x,n) <- numeroPerimetrosTriangulos p, n > 0]
          (m,_) = maximum ts 
 
-- (numeroPerimetrosTriangulos p) es la lista formado por los números de
-- 1 a p y la cantidad de triángulos rectángulos enteros cuyo perímetro
-- es dicho número. Por ejemplo,
--    ghci>  [(p,n) | (p,n) <- numeroPerimetrosTriangulos 70, n > 0]
--    [(12,1),(24,1),(30,1),(36,1),(40,1),(48,1),(56,1),(60,2),(70,1)]
numeroPerimetrosTriangulos :: Int -> [(Int,Int)] 
numeroPerimetrosTriangulos p = 
    assocs (accumArray (\x _ -> 1+x) 0 (1,p) (perimetrosTriangulos p))
 
-- (perimetrosTriangulos p) es la lista formada por los perímetros y los
-- lados de los triángulos rectángulos enteros cuyo perímetro es menor o
-- igual que p. Por ejemplo,
--    ghci> perimetrosTriangulos 70
--    [(12,(3,4,5)),   (30,(5,12,13)),(24,(6,8,10)),  (56,(7,24,25)),
--     (40,(8,15,17)), (36,(9,12,15)),(60,(10,24,26)),(48,(12,16,20)),
--     (60,(15,20,25)),(70,(20,21,29))]
perimetrosTriangulos :: Int -> [(Int,(Int,Int,Int))]
perimetrosTriangulos p =
    [(q,(a,b,c)) | a <- [1..p1],
                   b <- [a..p1],
                   esCuadrado (a*a+b*b), 
                   let c = raizCuadradaE (a*a+b*b), 
                   let q = a+b+c,
                   q <= p]
    where p1 = p `div` 2
 
-- (esCuadrado n) se verifica si n es un cuadrado. Por ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 27  ==  False
esCuadrado :: Int -> Bool
esCuadrado n = a*a == n
    where a = raizCuadradaE n
 
-- (raizCuadradaE n) es la raíz cuadrada entera de n. Por ejemplo,
--    raizCuadradaE 25  ==  5
--    raizCuadradaE 27  ==  5
--    raizCuadradaE 35  ==  5
--    raizCuadradaE 36  ==  6
raizCuadradaE :: Int -> Int
raizCuadradaE = floor . sqrt . fromIntegral
 
-- 3ª solución                                                      --
-- ===========
 
maxGradoPerimetral3 :: Int -> (Int,[Int])
maxGradoPerimetral3 p = (m,[x | (n,x) <- ts, n == m])
    where ts    = [(n,x) | (x,n) <- numeroPerimetrosTriangulos2 p, n > 0]
          (m,_) = maximum ts 
 
-- (numeroPerimetrosTriangulos2 p) es la lista formado por los números de
-- 1 a p y la cantidad de triángulos rectángulos enteros cuyo perímetro
-- es dicho número. Por ejemplo,
--    ghci>  [(p,n) | (p,n) <- numeroPerimetrosTriangulos2 70, n > 0]
--    [(12,1),(24,1),(30,1),(36,1),(40,1),(48,1),(56,1),(60,2),(70,1)]
numeroPerimetrosTriangulos2 :: Int -> [(Int,Int)] 
numeroPerimetrosTriangulos2 p = 
    [(head xs, length xs) | xs <- group (sort (perimetrosTriangulos2 p))]
 
-- (perimetrosTriangulos2 p) es la lista formada por los perímetros de
-- los triángulos rectángulos enteros cuyo perímetro es menor o igual
-- que p. Por ejemplo, 
--    perimetrosTriangulos2 70  ==  [12,30,24,56,40,36,60,48,60,70]
perimetrosTriangulos2 :: Int -> [Int]
perimetrosTriangulos2 p =
    [q | a <- [1..p1],
         b <- [a..p1],
         esCuadrado (a*a+b*b), 
         let c = raizCuadradaE (a*a+b*b), 
         let q = a+b+c,
         q <= p]
    where p1 = p `div` 2
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    ghci> maxGradoPerimetral1 1000
--    (8,[840])
--    (120.08 secs, 21116625136 bytes)
--    ghci> maxGradoPerimetral2 1000
--    (8,[840])
--    (0.66 secs, 132959056 bytes)
--    ghci> maxGradoPerimetral3 1000
--    (1000,[1])
--    (0.66 secs, 133443816 bytes)