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
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
oblongos :: [Integer] oblongosEnIntervalo :: Integer -> Integer -> Int
tales que
- oblongos es la sucesión de los números oblongos. Por ejemplo,
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,
oblongosEnIntervalo 10 30 == 3 oblongosEnIntervalo (10^3) (10^10) == 99968 oblongosEnIntervalo (10^3) (10^12) == 999968 oblongosEnIntervalo (10^3) (10^14) == 9999968
Soluciones
-- 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)