Orden de divisibilidad
El orden de divisibilidad de un número x es el mayor n tal que para todo i menor o igual que n, los i primeros dígitos de n es divisible por i. Por ejemplo, el orden de divisibilidad de 74156 es 3 porque
7 es divisible por 1 74 es divisible por 2 741 es divisible por 3 7415 no es divisible por 4
Definir la función
ordenDeDivisibilidad :: Integer -> Int
tal que (ordenDeDivisibilidad x) es el orden de divisibilidad de x. Por ejemplo,
ordenDeDivisibilidad 74156 == 3 ordenDeDivisibilidad 3608528850368400786036725 == 25
Soluciones
import Data.List (inits) -- 1ª definición de ordenDeDivisibilidad -- ===================================== ordenDeDivisibilidad :: Integer -> Int ordenDeDivisibilidad n = length (takeWhile (\(x,k) -> x `mod` k == 0) (zip (sucDigitos n) [1..])) -- (sucDigitos x) es la sucesión de los dígitos de x. Por ejemplo, -- sucDigitos 325 == [3,32,325] -- sucDigitos 32050 == [3,32,320,3205,32050] sucDigitos :: Integer -> [Integer] sucDigitos n = [n `div` (10^i) | i <- [k-1,k-2..0]] where k = length (show n) -- 2ª definición de sucDigitos sucDigitos2 :: Integer -> [Integer] sucDigitos2 n = [read xs | xs <- aux (show n)] where aux [] = [] aux (d:ds) = [d] : map (d:) (aux ds) -- 3ª definición de sucDigitos sucDigitos3 :: Integer -> [Integer] sucDigitos3 n = [read (take k ds) | k <- [1..length ds]] where ds = show n -- 4ª definición de sucDigitos sucDigitos4 :: Integer -> [Integer] sucDigitos4 n = [read xs | xs <- tail (inits (show n))] -- 5ª definición de sucDigitos sucDigitos5 :: Integer -> [Integer] sucDigitos5 n = map read (tail (inits (show n))) -- 6ª definición de sucDigitos sucDigitos6 :: Integer -> [Integer] sucDigitos6 = map read . (tail . inits . show) -- Eficiencia de las definiciones de sucDigitos -- λ> length (sucDigitos (10^5000)) -- 5001 -- (0.01 secs, 1550688 bytes) -- λ> length (sucDigitos2 (10^5000)) -- 5001 -- (1.25 secs, 729411872 bytes) -- λ> length (sucDigitos3 (10^5000)) -- 5001 -- (0.02 secs, 2265120 bytes) -- λ> length (sucDigitos4 (10^5000)) -- 5001 -- (1.10 secs, 728366872 bytes) -- λ> length (sucDigitos5 (10^5000)) -- 5001 -- (1.12 secs, 728393864 bytes) -- λ> length (sucDigitos6 (10^5000)) -- 5001 -- (1.20 secs, 728403052 bytes) -- -- λ> length (sucDigitos (10^3000000)) -- 3000001 -- (2.73 secs, 820042696 bytes) -- λ> length (sucDigitos3 (10^3000000)) -- 3000001 -- (3.69 secs, 820043688 bytes) -- 2ª definición de ordenDeDivisibilidad -- ===================================== ordenDeDivisibilidad2 :: Integer -> Int ordenDeDivisibilidad2 x = length $ takeWhile (==0) $ zipWith (mod . read) (tail $ inits $ show x) [1..]