Sucesión de números parientes
Se dice que dos números naturales son parientes sitienen exactamente un factor primo en común, independientemente de su multiplicidad. Por ejemplo,
- Los números 12 (2²·3) y 40 (2³·5) son parientes, pues tienen al 2 como único factor primo en común.
- Los números 49 (7²) y 63 (3²·7) son parientes, pues tienen al 7 como único factor primo en común.
- Los números 12 (2²·3) y 30 (2·3·5) no son parientes, pues tienen dos factores primos en común.
- Los números 49 (7²) y 25 (5²) no son parientes, pues no tienen factores primos en común.
Se dice que una lista de números naturales es una secuencia de parientes si cada par de números consecutivos son parientes. Por ejemplo,
- La lista [12,40,35,28] es una secuencia de parientes.
- La lista [12,30,21,49] no es una secuencia de parientes.
Definir la función
|
1 |
secuenciaParientes :: [Integer] -> Bool |
tal que (secuenciaParientes xs) se verifica si xs es una secuencia de parientes. Por ejemplo,
|
1 2 3 |
secuenciaParientes [12,40,35,28] == True secuenciaParientes [12,30,21,49] == False secuenciaParientes [2^n | n <- [1..2000]] == True |
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 |
import Data.List (intersect, nub) import Data.Numbers.Primes (primes, primeFactors) -- (parientes x y) se verifica si x e y son parientes. Por ejemplo, -- parientes 12 40 == True -- parientes 49 63 == True -- parientes 12 30 == False -- parientes 49 25 == False -- 1ª definición (con gcd) parientes1 :: Integer -> Integer -> Bool parientes1 x y = length [p | p <- takeWhile (<= d) primes, d `mod` p == 0] == 1 where d = gcd x y -- 2ª definición (con primeFactors) parientes2 :: Integer -> Integer -> Bool parientes2 0 0 = False parientes2 x y = length (nub (primeFactors x `intersect` primeFactors y)) == 1 -- Comparación de eficiencia -- ghci> parientes1 (2^25) (2^25) -- True -- (34.34 secs, 15974866184 bytes) -- ghci> parientes2 (2^25) (2^25) -- True -- (0.01 secs, 3093024 bytes) -- Usaremos la 2ª definición parientes :: Integer -> Integer -> Bool parientes = parientes2 -- Definiciones de secuenciaParientes -- ================================== -- 1ª definición (por recursión) secuenciaParientes :: [Integer] -> Bool secuenciaParientes [] = True secuenciaParientes [x] = True secuenciaParientes (x1:x2:xs) = parientes x1 x2 && secuenciaParientes (x2:xs) -- 2ª definición (por recursión con 2 ecuaciones) secuenciaParientes2 :: [Integer] -> Bool secuenciaParientes2 (x1:x2:xs) = parientes x1 x2 && secuenciaParientes2 (x2:xs) secuenciaParientes2 _ = True -- 3ª definición (sin recursión): secuenciaParientes3 :: [Integer] -> Bool secuenciaParientes3 xs = all (\(x,y) -> parientes x y) (zip xs (tail xs)) -- 4ª definición secuenciaParientes4 :: [Integer] -> Bool secuenciaParientes4 xs = all (uncurry parientes) (zip xs (tail xs)) |
4 Comentarios