Puntos visibles en la cuadrícula de un plano
La cuadrícula entera de lado n, Cₙ, es el conjunto de los puntos (x,y) donde x e y son números enteros tales que 1 ≤ x, y ≤ n.
Un punto (x,y) de Cₙ es visible desde el origen si el máximo común divisor de x e y es 1. Por ejemplo, el punto (4,6) no es visible porque está ocultado por el (2,3); en cambio, el (2,3) sí es visible.
El conjunto de los puntos visibles en la cuadrícula entera de lado 6 son (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) y (6,5).
Definir la función
|
1 |
nVisibles :: Integer -> Integer |
tal que (nVisibles n) es el número de los puntos visibles en la cuadrícula de lado n.Por ejemplo,
|
1 2 3 4 5 6 |
nVisibles 6 == 23 nVisibles 10 == 63 nVisibles 100 == 6087 nVisibles 1000 == 608383 nVisibles 10000 == 60794971 nVisibles 100000 == 6079301507 |
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
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) |
Referencias
- N.J.A. Sloane, Sucesión A018805 en OEIS.
No se me ocurre nada más «rápido» (para n=100.000 toma casi 10 minutos!) que restar los puntos internos de todas las diagonales, por lo que el algoritmo es O(n^2) pues el nº de diagonales se aproxima a 3n^2/Pi (https://en.wikipedia.org/wiki/Farey_sequence#Next_term).