Menu Close

Sucesiones de números consecutivos con suma dada

José A. Alonso,

El número 15 se puede escribir de 5 formas como suma de números naturales consecutivos:

   15 = 0+1+2+3+4+5 = 1+2+3+4+5 = 4+5+6 = 7+8 = 15.

Definir las funciones

   sucesionesConSuma        :: Int -> [(Int,Int)]
   graficaSucesionesConSuma :: Int -> IO ()

tales que

  • (sucesionesConSuma n) es la lista de los pares formados por el primero y por el último elemento de las sucesiones de números naturales consecutivos con suma n. Por ejemplo, 
     sucesionesConSuma 15             ==  [(0,5),(1,5),(4,6),(7,8),(15,15)]
     length (sucesionesConSuma 3000)  ==  8
  • (graficaSucesionesConSuma n) dibuja la gráfica del número de formas de escribir los n primeros números como suma de números naturales consecutivos. Por ejemplo, (graficaSucesionesConSuma 100) dibuja
    Sucesiones_de_numeros_consecutivos_con_suma_dada

Soluciones

import Graphics.Gnuplot.Simple
 
-- 1ª solución
sucesionesConSuma :: Int -> [(Int,Int)]
sucesionesConSuma n =
  [(x,y) | y <- [0..n], x <- [0..y], sum [x..y] == n]
 
-- 2ª solución
sucesionesConSuma2 :: Int -> [(Int,Int)]
sucesionesConSuma2 n = 
    [(x,y) | y <- [0..n], x <- [0..y], (x+y)*(y-x+1) == 2*n]
 
-- Comparación de eficiencia
--    λ> sucesionesConSuma 700
--    [(3,37),(16,40),(84,91),(97,103),(138,142),(700,700)]
--    (2.71 secs, 7,894,718,264 bytes)
--    λ> sucesionesConSuma2 700
--    [(3,37),(16,40),(84,91),(97,103),(138,142),(700,700)]
--    (0.22 secs, 118,104,176 bytes)
 
-- Gráfica
graficaSucesionesConSuma :: Int -> IO ()
graficaSucesionesConSuma n =
  plotList [ Key Nothing
           , PNG "Sucesiones_de_numeros_consecutivos_con_suma_dada.png"]
           [length (sucesionesConSuma2 k) | k <- [0..n]]
Medio
, , , ,

7 soluciones de “Sucesiones de números consecutivos con suma dada”

  1. Responder
    alerodrod5 
     
import Graphics.Gnuplot.Simple
sucesionesConSuma        :: Int -> [(Int,Int)]
sucesionesConSuma n = [(x,y) | x<-[0..n],y<-[x..n] , sum [x..y]==n]
 
graficaSucesionesConSuma :: Int -> IO ()
graficaSucesionesConSuma x = plotList [Key Nothing] [length (sucesionesConSuma n) | n<-[0..x]]
  2. Responder
    josejuan 
    {-
 
  La suma consecutiva de un número `n` puede definirse
  a partir del número inicial `b` (base) y el número de
  elementos `s` (size). Haciendo cuentas, tenemos que:
 
    2 n = s^2 + s (2 b - 1) con b >= 0 y s >= 1
 
  Despejando la base, la longitud queda dada por
 
    b = (2 n - s^2 + s) / 2 s
 
  Como b >= 0 entonces el valor máximo de `s` es
 
    s = (1 + sqrt(1 + 8 n)) / 2
 
  Por ejemplo para 15, el valor máximo para `s` es 6.
 
  Entonces, podemos obtener las sumas consecutivas para
  cualquier `n` en O(n^1/2).
 
-}
 
sucesionesConSuma :: Integral a => a -> [(a, a)]
sucesionesConSuma n = [(b, b + s - 1) | s <- [1.. floor ((1 + sqrt(1 + 8 * fromIntegral n)) / 2)]
                                      , let (b, r) = (2 * n - s * s + s) `divMod` (2 * s)
                                      , r == 0]
  3. Responder
    jaibengue 
    import Data.Numbers.Primes (primeFactors)
import Data.List (group,sort)
 
sucesionesConSuma :: Integer -> [(Integer,Integer)]
sucesionesConSuma n = givCerosIni aux ++ aux
  where aux = (sort.map getInd.decompNice) n
 
givCerosIni :: [(Integer,Integer)] -> [(Integer,Integer)]
givCerosIni ((1,a):xs) = (0,a):givCerosIni xs
givCerosIni _ = []
 
getInd :: (Integer,Integer) -> (Integer,Integer)
getInd (a,b) = ((a-b+1) `div` 2,(a+b) `div` 2)
 
decompNice :: Integer -> [(Integer,Integer)]
decompNice n = map ((xs,ys) -> flipOrd (toaInteger (head aux : xs), toaInteger ys)) (decomp(tail aux))
  where aux = factAndExp (n*2)
 
flipOrd :: (Integer,Integer) -> (Integer,Integer)
flipOrd (a,b) | a < b = (b,a)
              | otherwise = (a,b)
 
decomp :: [(Integer,Integer)] -> [([(Integer,Integer)],[(Integer,Integer)])]
decomp ((a,b):xs) = concat [[((a,u):p,(a,b-u):q)] | (p,q) <- decomp xs, u <- [0..b]]
decomp [] = [([],[])]
 
factAndExp :: Integer -> [(Integer,Integer)]
factAndExp = map (p@(x:xs) -> (x,(fromIntegral (length p)))).group.primeFactors
 
toaInteger :: [(Integer,Integer)] -> Integer
toaInteger [] = 1
toaInteger ((a,b):xs) = (a^b)*(toaInteger xs)
  4. Responder
    anadebla 
     
import Data.List
import Graphics.Gnuplot.Simple
 
 
sonConsecutivos [] = True
sonConsecutivos [_] = True
sonConsecutivos [x,y] | y == x+1  = True
                      | otherwise = False
 
sonConsecutivos (x:y:xs) | y == x+1  = sonConsecutivos (y:xs)
                         | otherwise = False
 
 
sumas n = filter p (tail (subsequences [0..n]))
  where p = sonConsecutivos
 
 
sumaDeListas n = [sum x | x <- (sumas n)]
 
parejas n = [(x,y) | (x,y) <- zip (sumas n) (sumaDeListas n) ]
 
sucesionesFinales n = [fst (x,y)| (x,y) <- (parejas n), y == n]
 
 
sucesionesConSuma :: Int -> [(Int,Int)]
sucesionesConSuma n = [((head x), (last x)) | x <- (sucesionesFinales n)]
 
 
listaSucesionesHasta n = [length (f x) | x <- [0..n]]
  where f = sucesionesConSuma
 
 
graficaSucesionesConSuma :: Int -> IO ()
graficaSucesionesConSuma n =
  plotList
  [Key Nothing, Title "sucesionesConSuma"]
  (listaSucesionesHasta n)
  5. Responder
    guigornun 
     
import Graphics.Gnuplot.Simple
 
sucesionesConSuma :: Int -> [(Int,Int)]
sucesionesConSuma n = aux 0 0 0
 where aux b c ac | n == b = [(n,n)]
                  | n == ac = (b,c-1):aux (b+1) (b+1) 0
                  | n > ac = aux b (c+1) (ac+c)
                  | n < ac = aux (b+1) (b+1) 0
 
graficaSucesionesConSuma n = plotList [Key Nothing] ([length (sucesionesConSuma k) | k <- [0..n]])
  6. Responder
    Maria Ruiz 

    
import Data.List
import Data.Maybe
import Graphics.Gnuplot.Simple

-- Primera forma:
-- =============

-- Generando todas las sucesiones de elementos consecutivos menores o
-- iguales que n.

sucesionesConSuma1 :: Int -> [(Int,Int)]
sucesionesConSuma1 n = map (\ys -> (head ys, last ys)) yss
  where xss = concatMap inits $ init $ tails [0..n]
        yss = [ys | ys <- xss, sum ys == n]

-- Segunda forma:
-- =============

-- Desde 0, ver si hay una sucesión de elementos consecutivos que sumen
-- n.

-- (sumaConsecutivos a b) calcula la suma de [a..b]
sumaConsecutivos a b = (b*(b+1)) `div` 2 - (((a-1)*a) `div` 2)

-- (supSuma a n) devuelve (Just b) si la suma de [a..b] es n y Nothing
-- en caso contrario.
supSuma a n =  listToMaybe [b | b <-[a..n], sumaConsecutivos a b == n]

-- Segunda forma:
-- =============

-- Desde 0, ver si hay una sucesión de elementos consecutivos que sumen
-- n.

-- (sumaConsecutivos a b) calcula la suma de [a..b]
sumaConsecutivos a b = (b*(b+1)) `div` 2 - (((a-1)*a) `div` 2)

-- (supSuma a n) devuelve (Just b) si la suma de [a..b] es n y Nothing
-- en caso contrario.
supSuma a n =  listToMaybe [b | b <-[a..n], sumaConsecutivos a b == n]

sucesionesConSuma2 :: Int -> [(Int,Int)]
sucesionesConSuma2 n =
  [(x, fromJust y) | x <-[0..n], let y = supSuma x n, isJust y]

-- length (sucesionesConSuma2 3000) == 8
-- (8.46 secs, 4,738,912,224 bytes)

graficaSucesionesConSuma :: Int -> IO ()
graficaSucesionesConSuma x = plotList [Key Nothing] [length (sucesionesConSuma2 n) | n<-[0..x]]

  7. Responder
    Maria Ruiz 

    import Data.List
import Data.Maybe
import Graphics.Gnuplot.Simple

-- Primera forma:
-- =============

-- Generando todas las sucesiones de elementos consecutivos menores o
-- iguales que n.

sucesionesConSuma1 :: Int -> [(Int,Int)]
sucesionesConSuma1 n = map (\ys -> (head ys, last ys)) yss
  where xss = concatMap inits $ init $ tails [0..n]
        yss = [ys | ys <- xss, sum ys == n]

-- Segunda forma:
-- =============

-- Desde 0, ver si hay una sucesión de elementos consecutivos que sumen
-- n.

-- (sumaConsecutivos a b) calcula la suma de [a..b]
sumaConsecutivos a b = (b*(b+1)) `div` 2 - (((a-1)*a) `div` 2)

-- (supSuma a n) devuelve (Just b) si la suma de [a..b] es n y Nothing
-- en caso contrario.
supSuma a n =  listToMaybe [b | b <-[a..n], sumaConsecutivos a b == n]

sucesionesConSuma2 :: Int -> [(Int,Int)]
sucesionesConSuma2 n =
  [(x, fromJust y) | x <-[0..n], let y = supSuma x n, isJust y]

-- length (sucesionesConSuma2 3000) == 8
-- (8.46 secs, 4,738,912,224 bytes)

graficaSucesionesConSuma :: Int -> IO ()
graficaSucesionesConSuma x = plotList [Key Nothing] [length (sucesionesConSuma2 n) | n<-[0..x]]

Escribe tu solución

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