Menu Close

Exponentes de Hamming

José A. Alonso,

Los números de Hamming forman una sucesión estrictamente creciente de números que cumplen las siguientes condiciones:

  • El número 1 está en la sucesión.
  • Si x está en la sucesión, entonces 2x, 3x y 5x también están.
  • Ningún otro número está en la sucesión.

Los primeros números de Hamming son 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, …

Los exponentes de un número de Hamming n es una terna (x,y,z) tal que n = 2^x*3^y*5^z. Por ejemplo, los exponentes de 600 son (3,1,2) ya que 600 = 2^x*3^1*5^z.

Definir la sucesión

   sucExponentesHamming :: [(Int,Int,Int)]

cuyos elementos son los exponentes de los números de Hamming. Por ejemplo,

   λ> take 21 sucExponentesHamming
   [(0,0,0),(1,0,0),(0,1,0),(2,0,0),(0,0,1),(1,1,0),(3,0,0),
    (0,2,0),(1,0,1),(2,1,0),(0,1,1),(4,0,0),(1,2,0),(2,0,1),
    (3,1,0),(0,0,2),(0,3,0),(1,1,1),(5,0,0),(2,2,0),(3,0,1)]
   λ> sucExponentesHamming !! (5*10^5)
   (74,82,7)

Soluciones

import Data.Numbers.Primes (primeFactors)
 
-- 1ª solución
-- ===========
 
sucExponentesHamming :: [(Int,Int,Int)]
sucExponentesHamming = map exponentes hamming
 
-- (exponentes n) es la terna de exponentes del número de Hamming n. Por
-- ejemplo, 
--    exponentes 600  ==  (3,1,2)
exponentes :: Integer -> (Int,Int,Int)
exponentes x = (length as, length cs, length ds)
  where xs = primeFactors x
        (as,bs) = span (==2) xs
        (cs,ds) = span (==3) bs
 
-- hamming es la sucesión de los números de Hamming. Por ejemplo,
--    λ> take 21 hamming
--    [1,2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,30,32,36,40]
hamming :: [Integer]
hamming = 1 : mezcla3 [2*i | i <- hamming]  
                      [3*i | i <- hamming]  
                      [5*i | i <- hamming]  
 
-- mezcla3 xs ys zs es la lista obtenida mezclando las listas ordenadas
-- xs, ys y zs y eliminando los elementos duplicados. Por ejemplo, 
--    mezcla3 [2,4,6,8,10] [3,6,9,12] [5,10]  ==  [2,3,4,5,6,8,9,10,12]
mezcla3 :: Ord a => [a] -> [a] -> [a] -> [a]
mezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs)  
 
-- mezcla2 xs ys zs es la lista obtenida mezclando las listas ordenadas
-- xs e ys y eliminando los elementos duplicados. Por ejemplo, 
--    mezcla2 [2,4,6,8,10,12] [3,6,9,12]  ==  [2,3,4,6,8,9,10,12]
mezcla2 :: Ord a => [a] -> [a] -> [a] 
mezcla2 p@(x:xs) q@(y:ys) | x < y     = x:mezcla2 xs q
                          | x > y     = y:mezcla2 p  ys  
                          | otherwise = x:mezcla2 xs ys
mezcla2 []       ys                   = ys
mezcla2 xs       []                   = xs
 
-- 2ª solución
-- ===========
 
sucExponentesHamming2 :: [(Int,Int,Int)]
sucExponentesHamming2 = map exponentes2 hamming
 
exponentes2 :: Integer -> (Int,Int,Int)
exponentes2 = aux (0,0,0)
  where aux (a,b,c) 1 = (a,b,c)
        aux (a,b,c) x | mod x 2 == 0 = aux (a+1,b,c) (div x 2)
                      | mod x 3 == 0 = aux (a,b+1,c) (div x 3)
                      | otherwise    = aux (a,b,c+1) (div x 5)
 
-- 3ª solución
-- ===========
 
sucExponentesHamming3 :: [(Int,Int,Int)]
sucExponentesHamming3 = map exponentes3 hamming
 
exponentes3 :: Integer -> (Int,Int,Int)
exponentes3 1 = (0,0,0)
exponentes3 x
  | x `mod` 2 == 0 = suma (1,0,0) (descomposicion (x `div` 2))
  | x `mod` 3 == 0 = suma (0,1,0) (descomposicion (x `div` 3))
  | otherwise      = suma (0,0,1) (descomposicion (x `div` 5))
  where suma (x,y,z) (a,b,c) = (x+a,y+b,z+c)
 
-- 4ª solución
-- ===========
 
type Terna = (Int,Int,Int)
 
sucExponentesHamming4 :: [Terna]
sucExponentesHamming4 =
  (0,0,0) : mezclaT3 [(x+1,y,z) | (x,y,z) <- sucExponentesHamming4]
                     [(x,y+1,z) | (x,y,z) <- sucExponentesHamming4]
                     [(x,y,z+1) | (x,y,z) <- sucExponentesHamming4]
 
mezclaT3 :: [Terna] -> [Terna] -> [Terna] -> [Terna]
mezclaT3 t1 t2 t3 = mezclaT2 t1 (mezclaT2 t2 t3)
 
mezclaT2 :: [Terna] -> [Terna] -> [Terna]
mezclaT2 ts1@((i,j,k):xs) ts2@((a,b,c):ys)
  | x < y     = (i,j,k) : mezclaT2 xs ts2
  | x > y     = (a,b,c) : mezclaT2 ts1 ys
  | otherwise = (i,j,k) : mezclaT2 xs ys
  where x = 2^i*3^j*5^k
        y = 2^a*3^b*5^c
Posted in Medio
Tagged , , , , , , ,

3 Comments

  1. albcarcas1
    Responder 
    import Data.Numbers.Primes
 
sucExponentesHamming :: [(Int,Int,Int)]
sucExponentesHamming = map (aux (0,0,0)) hamming
  where aux (a,b,c) 1 = (a,b,c)
        aux (a,b,c) x | mod x 2 == 0 = aux (a+1,b,c) (div x 2)
                      | mod x 3 == 0 = aux (a,b+1,c) (div x 3)
                      | otherwise    = aux (a,b,c+1) (div x 5)
 
hamming :: [Integer]
hamming = [x | x <- [1..], divisoresPrimosEn x [2,3,5]]
 
divisoresPrimosEn :: Integer -> [Integer] -> Bool
divisoresPrimosEn x ys = and [elem x ys | x <- primeFactors x]
  2. alerodrod5
    Responder 
    sucExponentesHamming :: [(Int,Int,Int)]
sucExponentesHamming = map descomposicion hamming
 
hamming :: [Integer]
hamming = 1 : mezcla3 [2*i | i <- hamming]  
                      [3*i | i <- hamming]  
                      [5*i | i <- hamming]  
 
mezcla3 :: [Integer] -> [Integer] -> [Integer] -> [Integer]
mezcla3 xs ys zs = mezcla2 xs (mezcla2 ys zs)
 
mezcla2 :: [Integer] -> [Integer] -> [Integer]
mezcla2 p@(x:xs) q@(y:ys) | x < y     = x:mezcla2 xs q
                          | x > y     = y:mezcla2 p  ys  
                          | otherwise = x:mezcla2 xs ys
mezcla2 []       ys                   = ys
mezcla2 xs       []                   = xs
 
descomposicion :: Integer -> (Int,Int,Int)
descomposicion x
  | x `mod` 2 == 0 = suma (1,0,0) (descomposicion (x `div` 2))
  | x `mod` 3 == 0 = suma (0,1,0) (descomposicion (x `div` 3))
  | x `mod` 5 == 0 = suma (0,0,1) (descomposicion (x `div` 5))
  | otherwise      = (0,0,0)
 
suma :: (Int,Int,Int) -> (Int, Int,Int) -> (Int,Int,Int)
suma (x,y,z) (a,b,c) = (x+a,y+b,z+c)
  3. Chema Cortés
    Responder 
    import           Data.Function (on)
import           Data.List
 
sucExponentesHamming :: [(Int,Int,Int)]
sucExponentesHamming =
  (0,0,0) : mezcla [(x+1,y,z) | (x,y,z) <- sucExponentesHamming]
                   [(x,y+1,z) | (x,y,z) <- sucExponentesHamming]
                   [(x,y,z+1) | (x,y,z) <- sucExponentesHamming]
 
mezcla :: [(Int,Int,Int)] -> [(Int,Int,Int)] -> [(Int,Int,Int)] -> [(Int,Int,Int)]
mezcla (x:xs) (y:ys) (z:zs) = m : mezcla xs' ys' zs'
  where
    m = minimumBy (compare `on` (i,j,k) -> 2^i*3^j*5^k) [x,y,z]
    xs' = if m==x then xs else x:xs
    ys' = if m==y then ys else y:ys
    zs' = if m==z then zs else z:zs

Escribe tu solución

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