Pares de enteros con sólo un factor primo común
Dos enteros positivos a y b se dirán relacionados si poseen, exactamente, un factor primo en común. Por ejemplo, 12 y 20 están relacionados, pero 6 y 30 no lo están.
Definir la lista infinita
|
1 |
paresRel :: [(Int,Int)] |
tal que paresRel enumera todos los pares (a,b), con 1 ≤ a < b, tal que a y b están relacionados. Por ejemplo,
|
1 2 |
ghci> take 10 paresRel [(2,4),(2,6),(3,6),(4,6),(2,8),(4,8),(6,8),(3,9),(6,9),(2,10)] |
¿Qué lugar ocupa el par (51,111) en la lista infinita paresRel?
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 |
import Data.List (group, intersect, nub) import Data.Numbers.Primes (primeFactors) -- 1ª solución -- =========== paresRel1 :: [(Int,Int)] paresRel1 = [(a,b) | b <- [1..], a <- [1..b-1], relacionados a b] relacionados :: Int -> Int -> Bool relacionados a b = length (nub (primeFactors a `intersect` primeFactors b)) == 1 -- 2ª solución -- =========== paresRel2 :: [(Int,Int)] paresRel2 = [(x,y) | y <- [4..], x <- [2..y-2], rel x y] where rel x y = m /= 1 && all (== head ps) ps where m = gcd x y ps = primeFactors m -- 3ª solución -- =========== paresRel3 :: [(Int,Int)] paresRel3 = [(x,y) | y <- [2..], x <- [2..y-1], relacionados3 x y] relacionados3 :: Int -> Int -> Bool relacionados3 x y = length (group (primeFactors (gcd x y))) == 1 -- Comparación de eficiencia -- λ> paresRel1 !! 40000 -- (216,489) -- (3.19 secs, 1,825,423,056 bytes) -- λ> paresRel2 !! 40000 -- (216,489) -- (0.96 secs, 287,174,864 bytes) -- λ> paresRel3 !! 40000 -- (216,489) -- (0.70 secs, 264,137,928 bytes) -- Cálculo -- ======= -- El cálculo es -- ghci> 1 + length (takeWhile (/=(51,111)) paresRel1) -- 2016 |
No es necesaria la función lambda en posicion. Quedaría así: