import Data.List (genericLength, group, sort)
import Data.Numbers.Primes (primeFactors)
type Punto = (Integer,Integer)
-- (visible p) se verifica si el punto p es visible. Por ejemplo,
-- visible (4,5) == True
-- visible (4,6) == False
visible :: Punto -> Bool
visible (x,y) = gcd x y == 1
-- (visibles n) es el conjunto de los puntos visibles en la cuadrícula
-- de lado 1. Por ejemplo,
-- cuadrado 1 <= x, y <= n. Por ejemplo,
-- λ> sort (visibles 6)
-- [(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(2,1),(2,3),(2,5),(3,1),(3,2),(3,4),
-- (3,5),(4,1),(4,3),(4,5),(5,1),(5,2),(5,3),(5,4),(5,6),(6,1),(6,5)]
-- 1ª definición de visibles
visibles1 :: Integer -> [Punto]
visibles1 n = [(x,y) | x <- [1..n], y <- [1..n], visible (x,y)]
-- 2ª definición de visibles
visibles2 :: Integer -> [Punto]
visibles2 n = (1,1) : ps ++ [(y,x) | (x,y) <- ps]
where ps = [(x,y) | x <- [1..n], y <- [x+1..n], visible (x,y)]
-- Comparación de eficiencia
-- =========================
-- λ> length (visibles1 1000)
-- 608383
-- (3.40 secs, 758,346,208 bytes)
-- λ> length (visibles2 1000)
-- 608383
-- (2.22 secs, 464,276,856 bytes)
-- Usaremos la 2ª definición de visibles
visibles :: Integer -> [Punto]
visibles = visibles2
-- 1ª definición de nVisibles
nVisibles1 :: Integer -> Integer
nVisibles1 = genericLength . visibles
-- 2ª definición de nVisibles
nVisibles2 :: Integer -> Integer
nVisibles2 n =
1 + 2 * genericLength [(x,y) | x <- [1..n],
y <- [x+1..n],
visible (x,y)]
-- 3ª definición de nVisibles
nVisibles3 :: Integer -> Integer
nVisibles3 1 = 1
nVisibles3 n = nVisibles3 (n-1) + (2 * phi n)
-- La función φ de Euler (del ejercicio anterior).
phi :: Integer -> Integer
phi n = product [(p-1)*p^(e-1) | (p,e) <- factorizacion n]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
[(head xs,genericLength xs) | xs <- group (primeFactors n)]
-- 4ª definición de nVisibles
nVisibles4 :: Integer -> Integer
nVisibles4 n = 2 * sum [phi x | x <- [1..n]] - 1
-- Comparación de eficiencia
-- =========================
-- λ> nVisibles1 1000
-- 608383
-- (2.69 secs, 521,599,512 bytes)
-- λ> nVisibles2 1000
-- 608383
-- λ> nVisibles3 1000
-- 608383
-- (0.05 secs, 0 bytes)
-- λ> nVisibles4 1000
-- 608383
-- (0.04 secs, 0 bytes)