Menu Close

Sucesiones de números consecutivos con suma dada

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