Números altamente compuestos

José A. Alonso, 16-enero-2019

Un número altamente compuesto es un entero positivo con más divisores que cualquier entero positivo más pequeño. Por ejemplo,

4 es un número altamente compuesto porque es el menor con 3 divisores,
5 no es altamente compuesto porque tiene menos divisores que 4 y
6 es un número altamente compuesto porque es el menor con 4 divisores,

Los primeros números altamente compuestos son

   1, 2, 4, 6, 12, 24, 36, 48, 60, 120, 180, 240, 360, ...

Definir las funciones

   esAltamenteCompuesto       :: Int -> Bool
   altamenteCompuestos        :: [Int]
   graficaAltamenteCompuestos :: Int -> IO ()

tales que

(esAltamanteCompuesto x) se verifica si x es altamente compuesto. Por ejemplo,

     esAltamenteCompuesto 4      ==  True
     esAltamenteCompuesto 5      ==  False
     esAltamenteCompuesto 6      ==  True
     esAltamenteCompuesto 1260   ==  True
     esAltamenteCompuesto 2520   ==  True
     esAltamenteCompuesto 27720  ==  True

altamente compuestos es la sucesión de los números altamente compuestos. Por ejemplo,

     λ> take 20 altamenteCompuestos
     [1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560]

(graficaAltamenteCompuestos n) dibuja la gráfica de los n primeros números altamente compuestos. Por ejemplo, (graficaAltamenteCompuestos 25) dibuja

Soluciones

import Data.List (group)
import Data.Numbers.Primes (primeFactors)
import Graphics.Gnuplot.Simple
 
-- 1ª definición de esAltamenteCompuesto
-- =====================================
 
esAltamenteCompuesto :: Int -> Bool
esAltamenteCompuesto x =
  and [nDivisores x > nDivisores y | y <- [1..x-1]]
 
-- (nDivisores x) es el número de divisores de x. Por ejemplo,
--    nDivisores 30  ==  8
nDivisores :: Int -> Int
nDivisores x = length (divisores x)
 
-- (divisores x) es la lista de los divisores de x. Por ejemplo,
--    divisores 30  ==  [1,2,3,5,6,10,15,30]
divisores :: Int -> [Int]
divisores x =
  [y | y <- [1..x]
     , x `mod` y == 0]
 
-- 2ª definición de esAltamenteCompuesto
-- =====================================
 
esAltamenteCompuesto2 :: Int -> Bool
esAltamenteCompuesto2 x =
  all (nDivisores2 x >) [nDivisores2 y | y <- [1..x-1]]
 
-- (nDivisores2 x) es el número de divisores de x. Por ejemplo,
--    nDivisores2 30  ==  8
nDivisores2 :: Int -> Int
nDivisores2 = succ . length . divisoresPropios
 
-- (divisoresPropios x) es la lista de los divisores de x menores que
-- x. Por ejemplo, 
--    divisoresPropios 30  ==  [1,2,3,5,6,10,15]
divisoresPropios :: Int -> [Int]
divisoresPropios x =
  [y | y <- [1..x `div` 2]
     , x `mod` y == 0]
 
-- 3ª definición de esAltamenteCompuesto
-- =====================================
 
esAltamenteCompuesto3 :: Int -> Bool
esAltamenteCompuesto3 x =
  all (nDivisores3 x >) [nDivisores3 y | y <- [1..x-1]]
 
-- (nDivisores3 x) es el número de divisores de x. Por ejemplo,
--    nDivisores3 30  ==  8
nDivisores3 :: Int -> Int
nDivisores3 x =
  product [1 + length xs | xs <- group (primeFactors x)]
 
-- 4ª definición de esAltamenteCompuesto
-- =====================================
 
esAltamenteCompuesto4 :: Int -> Bool
esAltamenteCompuesto4 x =
  x `pertenece` altamenteCompuestos2
 
-- 1ª definición de altamenteCompuestos 
-- ====================================
 
altamenteCompuestos :: [Int]
altamenteCompuestos =
  filter esAltamenteCompuesto4 [1..]
 
-- 2ª definición de altamenteCompuestos 
-- ====================================
 
altamenteCompuestos2 :: [Int]
altamenteCompuestos2 =
  1 : [y | ((x,n),(y,m)) <- zip sucMaxDivisores (tail sucMaxDivisores)
         , m > n]
 
-- sucMaxDivisores es la sucesión formada por los números enteros
-- positivos y el máximo número de divisores hasta cada número. Por
-- ejemplo,
--    λ> take 12 sucMaxDivisores
--    [(1,1),(2,2),(3,2),(4,3),(5,3),(6,4),(7,4),(8,4),(9,4),(10,4),(11,4),(12,6)]
sucMaxDivisores :: [(Int,Int)]
sucMaxDivisores =
  zip [1..] (scanl1 max (map nDivisores3 [1..]))
 
pertenece :: Int -> [Int] -> Bool
pertenece x ys =
  x == head (dropWhile (<x) ys)
 
-- Comparación de eficiencia de esAltamenteCompuesto
-- =================================================
 
--    λ> esAltamenteCompuesto 1260
--    True
--    (2.99 secs, 499,820,296 bytes)
--    λ> esAltamenteCompuesto2 1260
--    True
--    (0.51 secs, 83,902,744 bytes)
--    λ> esAltamenteCompuesto3 1260
--    True
--    (0.04 secs, 15,294,192 bytes)
--    λ> esAltamenteCompuesto4 1260
--    True
--    (0.04 secs, 15,594,392 bytes)
--    
--    λ> esAltamenteCompuesto2 2520
--    True
--    (2.10 secs, 332,940,168 bytes)
--    λ> esAltamenteCompuesto3 2520
--    True
--    (0.09 secs, 37,896,168 bytes)
--    λ> esAltamenteCompuesto4 2520
--    True
--    (0.06 secs, 23,087,456 bytes)
--
--    λ> esAltamenteCompuesto3 27720
--    True
--    (1.32 secs, 841,010,624 bytes)
--    λ> esAltamenteCompuesto4 27720
--    True
--    (1.33 secs, 810,870,384 bytes)
 
-- Comparación de eficiencia de altamenteCompuestos
-- ================================================
 
--    λ> altamenteCompuestos !! 25
--    45360
--    (2.84 secs, 1,612,045,976 bytes)
--    λ> altamenteCompuestos2 !! 25
--    45360
--    (0.01 secs, 102,176 bytes)
 
-- Definición de graficaAltamenteCompuestos
-- ========================================
 
graficaAltamenteCompuestos :: Int -> IO ()
graficaAltamenteCompuestos n =
  plotList [ Key Nothing
           , PNG ("Numeros_altamente_compuestos.png")
           ]
           (take n altamenteCompuestos2)

import Data.List (group) import Data.Numbers.Primes (primeFactors) import Graphics.Gnuplot.Simple -- 1ª definición de esAltamenteCompuesto -- ===================================== esAltamenteCompuesto :: Int -> Bool esAltamenteCompuesto x = and [nDivisores x > nDivisores y | y <- [1..x-1]] -- (nDivisores x) es el número de divisores de x. Por ejemplo, -- nDivisores 30 == 8 nDivisores :: Int -> Int nDivisores x = length (divisores x) -- (divisores x) es la lista de los divisores de x. Por ejemplo, -- divisores 30 == [1,2,3,5,6,10,15,30] divisores :: Int -> [Int] divisores x = [y | y <- [1..x] , x `mod` y == 0] -- 2ª definición de esAltamenteCompuesto -- ===================================== esAltamenteCompuesto2 :: Int -> Bool esAltamenteCompuesto2 x = all (nDivisores2 x >) [nDivisores2 y | y <- [1..x-1]] -- (nDivisores2 x) es el número de divisores de x. Por ejemplo, -- nDivisores2 30 == 8 nDivisores2 :: Int -> Int nDivisores2 = succ . length . divisoresPropios -- (divisoresPropios x) es la lista de los divisores de x menores que -- x. Por ejemplo, -- divisoresPropios 30 == [1,2,3,5,6,10,15] divisoresPropios :: Int -> [Int] divisoresPropios x = [y | y <- [1..x `div` 2] , x `mod` y == 0] -- 3ª definición de esAltamenteCompuesto -- ===================================== esAltamenteCompuesto3 :: Int -> Bool esAltamenteCompuesto3 x = all (nDivisores3 x >) [nDivisores3 y | y <- [1..x-1]] -- (nDivisores3 x) es el número de divisores de x. Por ejemplo, -- nDivisores3 30 == 8 nDivisores3 :: Int -> Int nDivisores3 x = product [1 + length xs | xs <- group (primeFactors x)] -- 4ª definición de esAltamenteCompuesto -- ===================================== esAltamenteCompuesto4 :: Int -> Bool esAltamenteCompuesto4 x = x `pertenece` altamenteCompuestos2 -- 1ª definición de altamenteCompuestos -- ==================================== altamenteCompuestos :: [Int] altamenteCompuestos = filter esAltamenteCompuesto4 [1..] -- 2ª definición de altamenteCompuestos -- ==================================== altamenteCompuestos2 :: [Int] altamenteCompuestos2 = 1 : [y | ((x,n),(y,m)) <- zip sucMaxDivisores (tail sucMaxDivisores) , m > n] -- sucMaxDivisores es la sucesión formada por los números enteros -- positivos y el máximo número de divisores hasta cada número. Por -- ejemplo, -- λ> take 12 sucMaxDivisores -- [(1,1),(2,2),(3,2),(4,3),(5,3),(6,4),(7,4),(8,4),(9,4),(10,4),(11,4),(12,6)] sucMaxDivisores :: [(Int,Int)] sucMaxDivisores = zip [1..] (scanl1 max (map nDivisores3 [1..])) pertenece :: Int -> [Int] -> Bool pertenece x ys = x == head (dropWhile (<x) ys) -- Comparación de eficiencia de esAltamenteCompuesto -- ================================================= -- λ> esAltamenteCompuesto 1260 -- True -- (2.99 secs, 499,820,296 bytes) -- λ> esAltamenteCompuesto2 1260 -- True -- (0.51 secs, 83,902,744 bytes) -- λ> esAltamenteCompuesto3 1260 -- True -- (0.04 secs, 15,294,192 bytes) -- λ> esAltamenteCompuesto4 1260 -- True -- (0.04 secs, 15,594,392 bytes) -- -- λ> esAltamenteCompuesto2 2520 -- True -- (2.10 secs, 332,940,168 bytes) -- λ> esAltamenteCompuesto3 2520 -- True -- (0.09 secs, 37,896,168 bytes) -- λ> esAltamenteCompuesto4 2520 -- True -- (0.06 secs, 23,087,456 bytes) -- -- λ> esAltamenteCompuesto3 27720 -- True -- (1.32 secs, 841,010,624 bytes) -- λ> esAltamenteCompuesto4 27720 -- True -- (1.33 secs, 810,870,384 bytes) -- Comparación de eficiencia de altamenteCompuestos -- ================================================ -- λ> altamenteCompuestos !! 25 -- 45360 -- (2.84 secs, 1,612,045,976 bytes) -- λ> altamenteCompuestos2 !! 25 -- 45360 -- (0.01 secs, 102,176 bytes) -- Definición de graficaAltamenteCompuestos -- ======================================== graficaAltamenteCompuestos :: Int -> IO () graficaAltamenteCompuestos n = plotList [ Key Nothing , PNG ("Numeros_altamente_compuestos.png") ] (take n altamenteCompuestos2)

Pensamiento

Nuestras horas son minutos
cuando esperamos saber,
y siglos cuando sabemos
lo que se puede aprender.

Antonio Machado

Posted in Medio

Tagged all, and, Comprensión, div, group, length, mod, Orden superior, primeFactors, product, succ

4 Comments

adogargon

16-enero-2019 at 11:18

Responder

import Graphics.Gnuplot.Simple
 
esAltamenteCompuesto :: Int -> Bool
esAltamenteCompuesto x =
  null [a | a <- [1..x-1]
          , length (divisores a) >= length (divisores x)]
 
divisores :: Int -> [Int]
divisores x = [a | a <- [1..x]
                   , x `mod` a == 0]
 
complejos :: [Int]
complejos = filter esAltamenteCompuesto [1..]
 
graficaAltamenteCompuestos :: Int -> IO ()
graficaAltamenteCompuestos n =  
  plotList [] (take n complejos)

frahidzam

16-enero-2019 at 11:43

Responder

import Graphics.Gnuplot.Simple
 
esAltamenteCompuesto :: Int -> Bool
esAltamenteCompuesto n =
  elem n (1 : parInt (altamenteCompuestos1 n))
 
altamenteCompuestos1 :: Int -> [(Int,Int)]
altamenteCompuestos1 n = estDec (zip [1..n] [divisores n | n <- [1..n]]) 0
 
divisores :: Int -> Int
divisores n = length [x | x <- [1..div n 2], mod n x == 0]
 
estDec :: [(Int,Int)] -> Int -> [(Int,Int)]
estDec [] _ = []
estDec (a:xs) x | snd a > x = a : estDec xs (snd a)
                | otherwise = estDec xs x
 
parInt :: [(Int,Int)] -> [Int]
parInt []     = []
parInt (x:xs) = fst x : parInt xs
 
altamenteCompuestos :: [Int]
altamenteCompuestos = [x | x <- [1..], esAltamenteCompuesto x]
 
graficaAltamenteCompuestos :: Int -> IO ()
graficaAltamenteCompuestos n =
  plotList [Key Nothing]
           (take n altamenteCompuestos)

luipromor

16-enero-2019 at 11:54

Responder

import Graphics.Gnuplot.Simple
 
esAltamenteCompuesto :: Int -> Bool
esAltamenteCompuesto x =
  (not . or) [(length . factores) x <= (length . factores) n
             | n <- [1..x - 1]]
  where factores x = [n | n <- [1..div x 2]
                        , mod x n == 0 ]
 
graficaAltamenteCompuestos :: Int -> IO ()
graficaAltamenteCompuestos z =
  plotList [] (take z [x | x <- [1..], esAltamenteCompuesto x])

ireprirod

19-enero-2019 at 21:47

Responder

import Graphics.Gnuplot.Simple
 
esAltamenteCompuesto :: Int -> Bool
esAltamenteCompuesto x = elem x altamenteCompuestos
 
altamenteCompuestos :: [Int]
altamenteCompuestos = mayorAnteriores (map nDivisores [1..])
 
nDivisores :: Int -> Int
nDivisores x = length [ y | y<-[1..x] , mod  x y == 0]
 
mayorAnteriores :: [Int] -> [Int]
mayorAnteriores (x:xs)=
  x:[ b |(a,b)<-zip xs [2..], a > maximum (take (b-1) (x:xs))]
 
graficaAltamenteCompuestos :: Int -> IO ()
graficaAltamenteCompuestos n =
  plotList [Key Nothing]
           (take n altamenteCompuestos)

Subscribe to Blog via Email

Entradas recientes

Etiquetas

Números altamente compuestos

Soluciones

Pensamiento

Se puede imprimir o compartir con

4 Comments

Leave a Reply to frahidzamCancel reply

Subscribe to Blog via Email

Entradas recientes

Etiquetas