Cantidad de números oblongos en un intervalo
Un número oblongo es un número que es el producto de dos números naturales consecutivos; es decir, n es un número oblongo si existe un número natural x tal que n = x(x+1). Por ejemplo, 42 es un número oblongo porque 42 = 6 x 7.
La sucesión de los números oblongos es
1 |
0, 2, 6, 12, 20, 30, 42, 56, 72, 90, 110, 132, 156, 182, 210, ... |
En el intervalo [10,30] hay 3 números oblongos (el 12, el 20 y el 30).
Definir las funciones
1 2 |
oblongos :: [Integer] oblongosEnIntervalo :: Integer -> Integer -> Int |
tales que
- oblongos es la sucesión de los números oblongos. Por ejemplo,
1 2 3 4 5 |
take 15 oblongos == [0,2,6,12,20,30,42,56,72,90,110,132,156,182,210] oblongos !! 50 == 2550 oblongos !! (10^5) == 10000100000 oblongos !! (10^6) == 1000001000000 oblongos !! (10^7) == 100000010000000 |
- (oblongosEnIntervalo a b) es la cantidad de números oblongos en el intervalo [a,b]. Por ejemplo,
1 2 3 4 |
oblongosEnIntervalo 10 30 == 3 oblongosEnIntervalo (10^3) (10^10) == 99968 oblongosEnIntervalo (10^3) (10^12) == 999968 oblongosEnIntervalo (10^3) (10^14) == 9999968 |
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 |
-- 1ª definición de oblongos oblongos1 :: [Integer] oblongos1 = [n*(n+1) | n <- [0..]] -- 2ª definición de oblongos oblongos2 :: [Integer] oblongos2 = zipWith (*) [0..] [1..] -- 3ª definición de oblongos oblongos3 :: [Integer] oblongos3 = scanl1 (+) [0,2..] -- Comparación de eficiencia -- ========================= -- λ> oblongos1 !! (10^7) -- 100000010000000 -- (3.05 secs, 1,840,112,008 bytes) -- λ> oblongos2 !! (10^7) -- 100000010000000 -- (0.90 secs, 2,480,112,304 bytes) -- λ> oblongos3 !! (10^7) -- 100000010000000 -- (3.38 secs, 2,252,411,640 bytes) -- Definición de oblongos -- ====================== -- En lo que sigue, usaremos la 2ª. oblongos :: [Integer] oblongos = oblongos2 -- 1ª definición de oblongosEnIntervalo -- ==================================== oblongosEnIntervalo1 :: Integer -> Integer -> Int oblongosEnIntervalo1 a b = length [x | x <- [a..b] , x `elem` takeWhile (<=b) oblongos] -- 2ª definición de oblongosEnIntervalo -- ==================================== oblongosEnIntervalo2 :: Integer -> Integer -> Int oblongosEnIntervalo2 a b = length (takeWhile (<=b) (dropWhile (< a) oblongos)) -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> oblongosEnIntervalo1 100 (10^5) -- 306 -- (2.43 secs, 1,784,537,632 bytes) -- λ> oblongosEnIntervalo2 100 (10^5) -- 306 -- (0.01 secs, 119,112 bytes) |
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>
4 Comentarios