Menu Close

Productos de N números consecutivos

La semana pasada se planteó en Twitter el siguiente problema

Se observa que

      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

   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,

   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,

   λ> 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

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])
Medio

4 soluciones de “Productos de N números consecutivos

  1. fracruzam
    -- Realiza todas las listas de n elementos consecutivos de una lista
    -- de enteros dada:
    consecutivos :: Integer -> [Integer] -> [[Integer]]
    consecutivos 0 _ = []
    consecutivos n xs 
        | length xs > fromIntegral n = [(xs !! fromIntegral 0)..
                      (xs !! fromIntegral n-1)]:(consecutivos n (tail xs))
        | otherwise = [xs]
     
    -- Filtramos la lista de n números consecutivos cuyo producto es x:
    aux :: Integer -> Integer -> [[Integer]]
    aux n x = filter (xs -> product xs == x) (consecutivos n [1..x])
     
    -- Comprobamos si el resultado de aux es o no nulo, y definimos:
    esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer
    esProductoDeNconsecutivos n x | null (aux n x) = Nothing
                                  | otherwise      = Just ((head.head) (aux n x))
    • fracruzam
      -- Aprovechando el hecho de que los números que buscamos son divisores
      -- del dado, podemos definir:
      divisores :: Integer -> [Integer]
      divisores n = filter (x -> (n `mod` x)  == 0) [1..n]
       
      -- Realizamos la lista de c números divisores de n consecutivos según el
      -- orden creciente:
      aux2 :: Integer -> Integer -> [[Integer]]
      aux2 c n = aux2' c (divisores n)
         where aux2' :: Integer -> [Integer] -> [[Integer]]
               aux2' 0 _      = []
               aux2' _ []     = []
               aux2' c (n:ns) | length (n:ns) > fromIntegral c = 
                                   (take (fromIntegral c) (n:ns)):(aux2' c ns)
                              | otherwise         = [n:ns]
       
      -- Filtramos los que son, en parte, consecutivos y cuyo producto es n:
      divisorProdConsecutivo :: Integer -> Integer -> [[Integer]]
      divisorProdConsecutivo c n = filter (xs -> product xs == n) 
           (filter (xs -> head xs == last xs - (c-1)) (aux2 c n))
       
      -- La función final, más eficiente que la anterior, es:
      esProductoDeNconsecutivos2 :: Integer -> Integer -> Maybe Integer
      esProductoDeNconsecutivos2 c n 
            | null (divisorProdConsecutivo c n) = Nothing
            | otherwise      = Just ((head.head) (divisorProdConsecutivo c n))
  2. Chema Cortés
    -- Función producto
    pk :: Integer -> Integer -> Integer
    pk n x = product [x..x+n-1]
     
    -- Definición directa
    esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer
    esProductoDeNconsecutivos n x =
        lookup x [ (pk n i, i) | i <- [1..x]]

    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).

    -- Aplicando búsqueda dicotómica
    esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer
    esProductoDeNconsecutivos n x = busqDicotomica comp 1 x
        where comp z = compare x (pk n z)
     
    -- Búsqueda dicotómica O(log n)
    -- Aplicable en conjuntos ordenados 
    busqDicotomica :: (Integer -> Ordering) -> Integer -> Integer -> Maybe Integer
    busqDicotomica comp a b | comp a == EQ      = Just a
                            | medio <= a        = Nothing
                            | comp medio == LT  = busqDicotomica comp a medio
                            | otherwise         = busqDicotomica comp medio b
        where medio = a + (b-a) `div` 2

    Para resolver el problema, probamos con los primeros 1000 primeros números naturales:

    soluciones :: [([Integer], [Integer])]
    soluciones = [ ([i..i+3],[j..j+2]) | (Just i,j) <- zip xs [1..limite] ]
        where xs = map (esProductoDeNconsecutivos 4 . pk 3) [1..]
              limite = 10000

    Se obtiene una nueva solución: 55x56x57 == 19x20x21x22

  3. manpende
    esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer
    esProductoDeNconsecutivos n x | productos n x == [] = Nothing
                                  | otherwise = Just (head (productos n x))
     
    productos :: Integer -> Integer -> [Integer]
    productos n x = [ m | m <- [1..(x-n)], productoRec m n == x]
        where productoRec m 1 = m * 1
              productoRec m n = (m+(n-1)) * productoRec m (n-1)

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.