Productos de N números consecutivos

PorJosé A. Alonso 17-noviembre-201526-marzo-2022

La semana pasada se planteó en Twitter el siguiente problema

Se observa que

      1x2x3x4 = 2x3x4 
      2x3x4x5 = 4x5x6

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

   esProductoDeNconsecutivos :: Integer -> Integer -> Maybe Integer

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,

   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

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

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

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

4 Comentarios

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

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

Responder

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

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

Responder

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

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

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

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

Responder

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)

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)

Responder

Productos de N números consecutivos

Soluciones

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

4 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico