Menu Close

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)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
Inicial

3 soluciones de “Números balanceados

  1. Rubén Muñoz Mkrtchian
    import Data.Numbers.Primes (primeFactors)
     
    balanceadores :: Integer -> [(Integer,Integer)]
    balanceadores n = concatMap (aux n) [1..]
     
    -- aux n b es la lista de balanceadores de n que tienen al número b como
    -- segundo elemento de cada par. Por ejemplo,
    --   λ> aux 3 11
    --   [(1,11),(6,11)]
    --   λ> aux 4 18
    --   [(6,18),(11,18)]
     
    aux :: Integer -> Integer -> [(Integer,Integer)]
    aux n b = [(a,b) | a <- [1..b-1],
               all (x -> balanceado ((x+a)*(x+b))) [1..n]]
     
    -- balanceado n se verifica si n tiene un número par de divisores primos. Por
    -- ejemplo,
    --   λ> balanceado 60
    --   True
    --   λ> balanceado 32
    --   False
     
    balanceado :: Integer -> Bool
    balanceado = even . length . primeFactors
  2. Mercedes Vega Gallo
    import Data.Numbers.Primes
     
    -- La función "balanceado x" se verifica si x es un número balanceado.
    balanceado :: Integer -> Bool
    balanceado x = even (length (primeFactors x))
     
    -- La función "propPol a b k" se verifica si, para un a y b determinados, todo
    -- x entre 1 y k hace que el valor del polinomio sea un número balanceado.
    propPol :: Integer -> Integer -> Integer -> Bool
    propPol a b k = all (balanceado) [(x+a)*(x+b)|x<-[1..k]]
     
    balanceadores :: Integer -> [(Integer,Integer)]
    balanceadores k = [(a,b)| b<-[1..],a<-[1..b-1], propPol a b k]
  3. Joaquín Infante Rodríguez
    import Data.Numbers.Primes
    import Data.List
     
    balanceado :: Integer -> Bool
    balanceado x = even (length (primeFactors x))
     
    balanceador :: (Integer,Integer) -> Integer -> Bool
    balanceador (a,b) k = and [balanceado ((x+a)*(x+b)) | x <- [1..k]]
     
    balanceadores :: Integer -> [(Integer,Integer)]
    balanceadores k = [(a,b) | b<-[1..] , a<-[1..b-1] , balanceador (a,b) k]

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.