Productos de N números consecutivos
La semana pasada se planteó en Twitter el siguiente problema
Se observa que
|
1 2 |
1x2x3x4 = 2x3x4 2x3x4x5 = 4x5x6 |
¿Existen ejemplos de otros productos de cuatro enteros consecutivos iguales a un producto de tres enteros consecutivos?
Definir la función
|
1 |
esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer |
tal que (esProductoDeNconsecutivos n x) es (Just m) si x es el producto de n enteros consecutivos a partir de m y es Nothing si x no es el producto de n enteros consecutivos. Por ejemplo,
|
1 2 3 4 5 6 |
esProductoDeNconsecutivos 3 6 == Just 1 esProductoDeNconsecutivos 4 6 == Nothing esProductoDeNconsecutivos 4 24 == Just 1 esProductoDeNconsecutivos 3 24 == Just 2 esProductoDeNconsecutivos 3 120 == Just 4 esProductoDeNconsecutivos 4 120 == Just 2 |
Para ejemplos mayores,
|
1 2 3 4 5 6 |
λ> esProductoDeNconsecutivos 3 (product [10^20..2+10^20]) Just 100000000000000000000 λ> esProductoDeNconsecutivos2 4 (product [10^20..2+10^20]) Nothing λ> esProductoDeNconsecutivos2 4 (product [10^20..3+10^20]) Just 100000000000000000000 |
Usando la función esProductoDeNconsecutivos resolver el problema.
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 |
import Data.Maybe -- 1ª definición esProductoDeNconsecutivos1 :: Integer -> Integer -> Maybe Integer esProductoDeNconsecutivos1 n x | null productos = Nothing | otherwise = Just (head productos) where productos = [m | m <- [1..x-n], product [m..m+n-1] == x] -- 2ª definición esProductoDeNconsecutivos2 :: Integer -> Integer -> Maybe Integer esProductoDeNconsecutivos2 n x = aux k where k = floor (fromIntegral x ** (1/(fromIntegral n))) - (n `div` 2) aux m | y == x = Just m | y < x = aux (m+1) | otherwise = Nothing where y = product [m..m+n-1] -- Comparación de eficiencia -- λ> esProductoDeNconsecutivos1 3 (product [10^7..2+10^7]) -- Just 10000000 -- (12.37 secs, 5678433692 bytes) -- λ> esProductoDeNconsecutivos2 3 (product [10^7..2+10^7]) -- Just 10000000 -- (0.00 secs, 1554932 bytes) -- Solución del problema -- ===================== soluciones :: [Integer] soluciones = [x | x <- [121..] , isJust (esProductoDeNconsecutivos2 4 x) , isJust (esProductoDeNconsecutivos2 3 x)] -- El cálculo es -- λ> head soluciones -- 175560 -- λ> esProductoDeNconsecutivos2 4 175560 -- Just 19 -- λ> esProductoDeNconsecutivos2 3 175560 -- Just 55 -- λ> product [19,20,21,22] -- 175560 -- λ> product [55,56,57] -- 175560 -- λ> product [19,20,21,22] == product [55,56,57] -- True -- Se puede definir una función para automatizar el proceso anterior: soluciones2 :: [(Integer,[Integer],[Integer])] soluciones2 = [(x,[a..a+3],[b..b+2]) | x <- [121..] , let y = esProductoDeNconsecutivos2 4 x , isJust y , let z = esProductoDeNconsecutivos2 3 x , isJust z , let a = fromJust y , let b = fromJust z ] -- El cálculo es -- λ> head soluciones2 -- (175560,[19,20,21,22],[55,56,57]) |