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]) |
Considerando que el producto de N números consecutivos es una función estrictamente creciente, se puede acelerar la anterior búsqueda mediante una búsqueda dicotómica O(log n).
Para resolver el problema, probamos con los primeros 1000 primeros números naturales:
Se obtiene una nueva solución: 55x56x57 == 19x20x21x22