Números muy divisibles por 3
Se dice que un número n es muy divisible por 3 si es divisible por 3 y sigue siendo divisible por 3 si vamos quitando dígitos por la derecha. Por ejemplo, 96060 es muy divisible por 3 porque 96060, 9606, 960, 96 y 9 son todos divisibles por 3.
Definir las funciones
muyDivPor3 :: Integer -> Bool numeroMuyDivPor3Cifras :: Integer -> Integer
tales que
- (muyDivPor3 n) se verifica si n es muy divisible por 3. Por ejemplo,
muyDivPor3 96060 == True muyDivPor3 90616 == False
- (numeroMuyDivPor3CifrasC k) es la cantidad de números de k cifras muy divisibles por 3. Por ejemplo,
numeroMuyDivPor3Cifras 5 == 768 numeroMuyDivPor3Cifras 7 == 12288 numeroMuyDivPor3Cifras (10^6) `rem` (10^6) == 332032
Soluciones
import Data.List (genericLength) muyDivPor3 :: Integer -> Bool muyDivPor3 n | n < 10 = n `rem` 3 == 0 | otherwise = n `rem` 3 == 0 && muyDivPor3 (n `div` 10) -- 1ª definición numeroMuyDivPor3Cifras :: Integer -> Integer numeroMuyDivPor3Cifras k = genericLength [x | x <- [10^(k-1)..10^k-1], muyDivPor3 x] -- 2ª definición numeroMuyDivPor3Cifras2 :: Integer -> Integer numeroMuyDivPor3Cifras2 k = genericLength [x | x <- [n,n+3..10^k-1], muyDivPor3 x] where n = k*10^(k-1) -- 3ª definición -- ============= numeroMuyDivPor3Cifras3 :: Integer -> Integer numeroMuyDivPor3Cifras3 k = genericLength (numeroMuyDivPor3Cifras3' k) numeroMuyDivPor3Cifras3' :: Integer -> [Integer] numeroMuyDivPor3Cifras3' 1 = [3,6,9] numeroMuyDivPor3Cifras3' k = [10*x+y | x <- numeroMuyDivPor3Cifras3' (k-1), y <- [0,3..9]] -- 4ª definición -- ============= numeroMuyDivPor3Cifras4 :: Integer -> Integer numeroMuyDivPor3Cifras4 1 = 3 numeroMuyDivPor3Cifras4 k = 4 * numeroMuyDivPor3Cifras4 (k-1) -- 5ª definición numeroMuyDivPor3Cifras5 :: Integer -> Integer numeroMuyDivPor3Cifras5 k = 3 * 4^(k-1) -- Comparación de eficiencia -- ========================= -- λ> numeroMuyDivPor3Cifras 6 -- 3072 -- (3.47 secs, 534,789,608 bytes) -- λ> numeroMuyDivPor3Cifras2 6 -- 2048 -- (0.88 secs, 107,883,432 bytes) -- λ> numeroMuyDivPor3Cifras3 6 -- 3072 -- (0.01 secs, 0 bytes) -- -- λ> numeroMuyDivPor3Cifras2 7 -- 0 -- (2.57 secs, 375,999,336 bytes) -- λ> numeroMuyDivPor3Cifras3 7 -- 12288 -- (0.02 secs, 0 bytes) -- λ> numeroMuyDivPor3Cifras4 7 -- 12288 -- (0.00 secs, 0 bytes) -- λ> numeroMuyDivPor3Cifras5 7 -- 12288 -- (0.01 secs, 0 bytes) -- -- λ> numeroMuyDivPor3Cifras4 (10^5) `rem` 100000 -- 32032 -- (5.74 secs, 1,408,600,592 bytes) -- λ> numeroMuyDivPor3Cifras5 (10^5) `rem` 100000 -- 32032 -- (0.02 secs, 0 bytes)