Números balanceados
Un número está balanceado si tiene un número par de divisores primos (contados con su multiplicidad). Por ejemplo, 60 es balanceado porque tiene 4 divisores primos (2, 2, 3 y 5).
Un balanceador del entero positivo k es par de enteros positivos (a,b) tales que a es menor que b y, para todo x entre 1 y k, el valor del polinomio P(x) = (x+a)*(x+b) es un número balanceado. Por ejemplo, (2,4) es un balanceador de 3 ya que
P(1) = (1+2)*(1+4) = 15 = 3*5 es balanceado P(2) = (2+2)*(2+4) = 24 = 2*2*2*3 es balanceado P(3) = (3+2)*(3+4) = 35 = 5*7 es balanceado
Definir la función
balanceadores :: Integer -> [(Integer,Integer)]
tal que (balanceadores k) es el conjunto de los balanceadores de k. Por ejemplo,
λ> take 7 (balanceadores 3) [(2,4),(1,6),(5,9),(1,11),(6,11),(7,12),(8,14)] λ> take 7 (balanceadores 5) [(8,14),(10,17),(6,18),(12,22),(13,23),(8,24),(14,24)] λ> take 7 (balanceadores 3) [(2,4),(1,6),(5,9),(1,11),(6,11),(7,12),(8,14)] λ> take 7 (balanceadores 4) [(6,11),(8,14),(9,15),(10,17),(6,18),(11,18),(7,19)] λ> take 7 (balanceadores 5) [(8,14),(10,17),(6,18),(12,22),(13,23),(8,24),(14,24)] λ> head (balanceadores 19) (1325,2827)
Nota: Este ejercicio está basado en el problema N2 de la Olimpíada Internacional de Matemáticas (IMO) del 2009.
Soluciones
import Data.Numbers.Primes (primeFactors) -- 1ª solución -- =========== balanceadores :: Integer -> [(Integer,Integer)] balanceadores k = [(a,b) | (a,b) <- pares , all esBalanceado [(x+a)*(x+b) | x <- [1..k]]] -- (esBalanceado x) se verifica si x es balanceado. Por ejemplo, -- esBalanceado 60 == True -- esBalanceado 50 == False esBalanceado :: Integer -> Bool esBalanceado = even . length . primeFactors -- pares el lista de pares de enteros positivos con el primero menor que -- el segundo. Por ejemplo, -- λ> take 10 pares -- [(1,2),(1,3),(2,3),(1,4),(2,4),(3,4),(1,5),(2,5),(3,5),(4,5)] pares :: [(Integer,Integer)] pares = [(a,b) | b <- [1..] , a <- [1..b-1]] -- 2ª solución -- =========== balanceadores2 :: Integer -> [(Integer,Integer)] balanceadores2 1 = balanceadores 1 balanceadores2 k = [(a,b) | (a,b) <- balanceadores2 (k-1) , all esBalanceado [(x+a)*(x+b) | x <- [1..k]]] -- 3ª solución -- =========== balanceadores3 :: Integer -> [(Integer,Integer)] balanceadores3 k = [(a,b) | (a,b) <- pares , and [esBalanceado (x+a) == esBalanceado (x+b) | x <- [1..k]]] -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> head (balanceadores 17) -- (189,282) -- (0.53 secs, 1,227,921,384 bytes) -- λ> head (balanceadores2 17) -- (189,282) -- (0.97 secs, 2,483,869,656 bytes) -- λ> head (balanceadores3 17) -- (189,282) -- (0.36 secs, 983,881,264 bytes)