Menor número con una cantidad de divisores dada
El menor número con 2¹ divisores es el 2, ya que tiene 2 divisores (el 1 y el 2) y el anterior al 2 (el 1) sólo tiene 1 divisor (el 1).
El menor número con 2² divisores es el 6, ya que tiene 4 divisores (el 1, 2, 3 y 6) y sus anteriores (el 1, 2, 3, 4 y 5) tienen menos de 4 divisores (tienen 1, 1, 1, 3 y 1, respectivamente).
El menor número con 2³ divisores es el 24, ya que tiene 8 divisores (el 1, 2, 3, 4, 6, 8, 12 y 24) y sus anteriores (del 1 al 23) tienen menos de 8 divisores.
El menor número con 16 divisores es el 120, ya que tiene 16 divisores (el 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 y 120) y sus anteriores (del 1 al 119) tienen menos de 16 divisores.
El menor número, módulo 100, con 16 divisores es el 20, ya que el menor número con 16 divisores es el 120 y 120 módulo 100 es 20.
Definir la función
menor :: Integer -> Integer -> Integer
tal que (menor n m) es el menor número, módulo m, con 2^n divisores. Por ejemplo,
menor 4 1000 == 120 menor 4 100 == 20 [menor n (10^9) | n <- [1..8]] == [2,6,24,120,840,7560,83160,1081080] menor 500500 500500506 == 8728302
Soluciones
import Data.List (foldl', genericLength, genericTake, group) import Data.Numbers.Primes (primeFactors, primes) -- 1ª solución -- =========== menor :: Integer -> Integer -> Integer menor n m = head [x `mod` m | x <- [1..], numDivisores x == 2^n] -- (numDivisores x) es el número de divisores de x. Por ejemplo, -- numDivisores 120 == 16 numDivisores :: Integer -> Integer numDivisores = product . map ((+1) . genericLength) . group . primeFactors -- 2ª solución -- =========== menor2 :: Integer -> Integer -> Integer menor2 n m = product (genericTake n potencias) `mod` m -- potencias es la sucesión de las potencias de la forma p^(2^k), -- donde p es un número primo y k es un número natural, ordenadas de -- menor a mayor. Por ejemplo, -- take 14 potencias == [2,3,4,5,7,9,11,13,16,17,19,23,25,29] potencias :: [Integer] potencias = 2 : mezcla (tail primes) (map (^2) potencias) -- (mezcla xs ys) es la lista obtenida mezclando las dos listas xs e ys, -- que se suponen ordenadas y disjuntas. Por ejemplo, -- λ> take 15 (mezcla [2^n | n <- [1..]] [3^n | n <- [1..]]) -- [2,3,4,8,9,16,27,32,64,81,128,243,256,512,729] mezcla :: Ord a => [a] -> [a] -> [a] mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys) | x > y = y : mezcla (x:xs) ys -- 3ª solución -- =========== menor3 :: Integer -> Integer -> Integer menor3 n m = producto m (genericTake n potencias) -- (producto m xs) es el productos de los elementos de xs módulo m. Por -- ejemplo, -- producto 1000 [12,23,45,67,89] == 460 -- product [12,23,45,67,89] == 74060460 producto :: Integer -> [Integer] -> Integer producto m = foldl' (\a b -> (a * (b `mod` m)) `mod` m) 1 -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> menor 7 (10^5) -- 83160 -- (5.04 secs, 3322592576 bytes) -- λ> menor2 7 (10^5) -- 83160 -- (0.01 secs, 2578064 bytes) -- λ> menor3 7 (10^5) -- 83160 -- (0.01 secs, 3093448 bytes) -- -- λ> menor2 123456 500500506 -- 470474928 -- (52.42 secs, 18074107216 bytes) -- λ> menor3 123456 500500506 -- 470474928 -- (0.17 secs, 41497520 bytes)