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
1 2 |
muyDivPor3 :: Integer -> Bool numeroMuyDivPor3Cifras :: Integer -> Integer |
tales que
- (muyDivPor3 n) se verifica si n es muy divisible por 3. Por ejemplo,
1 2 |
muyDivPor3 96060 == True muyDivPor3 90616 == False |
- (numeroMuyDivPor3CifrasC k) es la cantidad de números de k cifras muy divisibles por 3. Por ejemplo,
1 2 3 |
numeroMuyDivPor3Cifras 5 == 768 numeroMuyDivPor3Cifras 7 == 12288 numeroMuyDivPor3Cifras (10^6) `rem` (10^6) == 332032 |
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 |
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 (numeroMuyDivPor3Cifras3a k) numeroMuyDivPor3Cifras3a :: Integer -> [Integer] numeroMuyDivPor3Cifras3a 1 = [3,6,9] numeroMuyDivPor3Cifras3a k = [10*x+y | x <- numeroMuyDivPor3Cifras3a (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) |
Un número es divisible por 3 si la suma de sus cifras es divisible por 3. Aplicando esta propiedad de la divisibilidad, por inducción se puede comprobar que para un «número muy divisible por 3» todas y cada una de sus cifras tienen que ser divisibles por
3
, o ser'0'
.Los «números muy divisibles por 3» se construyen con cuatro cifras,
"0369"
. La cantidad de estos números sería4^n
, a los que habría que restar los que empiezan por ‘0’: