Menor número con una cantidad dada de divisores
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 4 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 8 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.
Definir la función
|
1 |
menor :: Integer -> Integer |
tal que (menor n) es el menor número con 2^n divisores. Por ejemplo,
|
1 2 3 4 5 |
menor 1 == 2 menor 2 == 6 menor 3 == 24 menor 4 == 120 length (show (menor (4*10^4))) == 207945 |
Comprobar con QuickCheck que, para todo k >=0, (menor (2^k)) es un divisor de (menor (2^(k+1))).
Nota: Este ejercicio está basado en el problema N1 de la Olimpíada Internacional de Matemáticas (IMO) del 2011.
Soluciones
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
import Data.List (genericLength, genericTake, group) import Data.Numbers.Primes (primeFactors, primes) import Test.QuickCheck (Positive (Positive), maxSize, stdArgs, quickCheck, quickCheckWith) -- 1ª solución -- =========== menor1 :: Integer -> Integer menor1 n = head [x | x <- [1..], numeroDivisores x == 2^n] -- (numeroDivisores n) es el número de divisores de n. Por ejemplo, -- numeroDivisores 12 == 6 numeroDivisores :: Integer -> Integer numeroDivisores = genericLength . divisores -- (divisores x) es la lista de los divisores de x. Por ejemplo, -- divisores 12 == [1,3,2,6,4,12] -- divisores 25 == [1,5,25] divisores :: Integer -> [Integer] divisores n = [x | x <- [1..n], n `rem` x == 0] -- 2ª solución -- =========== menor2 :: Integer -> Integer menor2 n = head [x | x <- [1..], numeroDivisores2 x == 2^n] numeroDivisores2 :: Integer -> Integer numeroDivisores2 = product . map ((+1) . genericLength) . group . primeFactors -- 3ª solución -- =========== menor3 :: Integer -> Integer menor3 n = product (genericTake n potencias) -- 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 -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_menor :: Positive Integer -> Bool prop_menor (Positive n) = all (== menor1 n) [menor2 n, menor3 n] -- La comprobación es -- λ> quickCheckWith (stdArgs {maxSize=5}) prop_menor -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> menor 8 -- 1081080 -- (47.69 secs, 94,764,856,352 bytes) -- λ> menor2 8 -- 1081080 -- (36.17 secs, 94,764,856,368 bytes) -- λ> menor3 8 -- 1081080 -- (0.00 secs, 116,960 bytes) -- Definición de menor -- =================== -- En lo que sigue, usaremos menor3 como menor. menor :: Integer -> Integer menor = menor3 -- Propiedad -- ========= -- La propiedad es prop_menor_divide :: Positive Integer -> Bool prop_menor_divide (Positive n) = menor (n+1) `mod` menor n == 0 -- La comprobación es -- λ> quickCheck prop_menor_divide -- +++ OK, passed 100 tests. |
El código se encuentra en GitHub.