Dígitos en la factorización

José A. Alonso

19-02-2016

El enunciado del problema 652 de Números y algo más es el siguiente

Si factorizamos los factoriales de un número en función de sus divisores primos y sus potencias, ¿Cuál es el menor número n tal que entre los factores primos y los exponentes de estos, n! contiene los dígitos del cero al nueve? Por ejemplo

6! = 2⁴x3²x5¹, le faltan los dígitos 0,6,7,8 y 9

12! = 2¹⁰x3⁵x5²x7¹x11¹, le faltan los dígitos 4,6,8 y 9

Definir la función

digitosDeFactorizacion :: Integer -> [Integer]

tal que (digitosDeFactorizacion n) es el conjunto de los dígitos que aparecen en la factorización de n. Por ejemplo,

digitosDeFactorizacion (factorial 6)   ==  [1,2,3,4,5]
digitosDeFactorizacion (factorial 12)  ==  [0,1,2,3,5,7]

Usando la función anterior, calcular la solución del problema.

Comprobar con QuickCheck que si n es mayor que 100, entonces

digitosDeFactorizacion (factorial n) == [0..9]

Soluciones

import Data.List (genericLength, group, nub, sort)
import Data.Numbers.Primes (primeFactors)
import Test.QuickCheck

-- 1ª definición
-- =============

digitosDeFactorizacion1 :: Integer -> [Integer]
digitosDeFactorizacion1 n =
   sort (nub (concat [digitos x | x <- numerosDeFactorizacion n]))

-- (digitos n) es la lista de los digitos del número n. Por ejemplo,
--    digitos 320274  ==  [3,2,0,2,7,4]
digitos :: Integer -> [Integer]
digitos n = [read [x] | x <- show n]

-- (numerosDeFactorizacion n) es el conjunto de los números en la
-- factorización de n. Por ejemplo,
--    numerosDeFactorizacion 60  ==  [1,2,3,5]
numerosDeFactorizacion :: Integer -> [Integer]
numerosDeFactorizacion n =
   sort (nub (aux (factorizacion n)))
   where aux [] = []
         aux ((x,y):zs) = x : y : aux zs

-- (factorización n) es la factorización de n. Por ejemplo,
--    factorizacion 300  ==  [(2,2),(3,1),(5,2)]
factorizacion :: Integer -> [(Integer,Integer)]
factorizacion n =
    [(head xs, genericLength xs) | xs <- group (factorizacion' n)]

-- (factorizacion' n) es la lista de todos los factores primos de n; es
-- decir, es una lista de números primos cuyo producto es n. Por ejemplo,
--    factorizacion 300  ==  [2,2,3,5,5]
factorizacion' :: Integer -> [Integer]
factorizacion' n | n == 1    = []
                 | otherwise = x : factorizacion' (div n x)
                 where x = menorFactor n

-- (menorFactor n) es el menor factor primo de n. Por ejemplo,
--    menorFactor 15  ==  3
menorFactor :: Integer -> Integer
menorFactor n = head [x | x <- [2..], rem n x == 0]

-- (factorial n) es el factorial de n. Por ejemplo,
--    factorial 5  ==  120
factorial :: Integer -> Integer
factorial n = product [1..n]

-- 2ª definición
-- =============

digitosDeFactorizacion2 :: Integer -> [Integer]
digitosDeFactorizacion2 n =
   sort (nub (concat [digitos x | x <- numerosDeFactorizacion2 n]))

-- (numerosDeFactorizacion2 n) es el conjunto de los números en la
-- factorización de n. Por ejemplo,
--    numerosDeFactorizacion2 60  ==  [1,2,3,5]
numerosDeFactorizacion2 :: Integer -> [Integer]
numerosDeFactorizacion2 n =
    sort (nub (aux (factorizacion2 n)))
    where aux xs = concat [[a,b] | (a,b) <- xs]

-- (factorización2 n) es la factorización de n. Por ejemplo,
--    factorizacion2 300  ==  [(2,2),(3,1),(5,2)]
factorizacion2 :: Integer -> [(Integer,Integer)]
factorizacion2 n =
    [(head xs, genericLength xs) | xs <- group (primeFactors n)]

-- 3ª definición
-- =============

digitosDeFactorizacion3 :: Integer -> [Integer]
digitosDeFactorizacion3 n =
    sort (nub (concat [digitos x | x <- aux (group (primeFactors n))]))
    where aux  []            = []
          aux (ys@(y:_):xss) = y : genericLength ys : aux xss

-- Definición
-- ==========

digitosDeFactorizacion :: Integer -> [Integer]
digitosDeFactorizacion = digitosDeFactorizacion3

-- Solución
-- ========

-- Para calcular la solución, se define la constante
solucion :: Integer
solucion =
    head [n | n <- [1..], digitosDeFactorizacion (factorial n) == [0..9]]

-- El cálculo de la solución es
--    λ> solucion2
--    49

-- Propiedad
-- =========

-- La propiedad es
prop_completa :: Integer -> Bool
prop_completa n =
    digitosDeFactorizacion (factorial n1) == [0..9]
    where n1 = 101 + abs n

-- La comprobación es
--    λ> quickCheck prop_completa
--    +++ OK, passed 100 tests.