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
1 2 3 4 |
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
1 |
ordenDeDivisibilidad :: Integer -> Int |
tal que (ordenDeDivisibilidad x) es el orden de divisibilidad de x. Por ejemplo,
1 2 3 4 |
ordenDeDivisibilidad 74156 == 3 ordenDeDivisibilidad 12 == 2 ordenDeDivisibilidad 7 == 1 ordenDeDivisibilidad 3608528850368400786036725 == 25 |
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 |
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 -- ghci> length (sucDigitos (10^5000)) -- 5001 -- (0.01 secs, 1550688 bytes) -- ghci> length (sucDigitos2 (10^5000)) -- 5001 -- (1.25 secs, 729411872 bytes) -- ghci> length (sucDigitos3 (10^5000)) -- 5001 -- (0.02 secs, 2265120 bytes) -- ghci> length (sucDigitos4 (10^5000)) -- 5001 -- (1.10 secs, 728366872 bytes) -- ghci> length (sucDigitos5 (10^5000)) -- 5001 -- (1.12 secs, 728393864 bytes) -- ghci> length (sucDigitos6 (10^5000)) -- 5001 -- (1.20 secs, 728403052 bytes) -- -- ghci> length (sucDigitos (10^3000000)) -- 3000001 -- (2.73 secs, 820042696 bytes) -- ghci> 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..] |
Otras soluciones
- Se pueden escribir otras soluciones en los comentarios.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
2 Comentarios