Menu Close

Números como sumas de primos consecutivos

En el artículo Integers as a sum of consecutive primes in 2,3,4,.. ways se presentan números que se pueden escribir como sumas de primos consecutivos de varias formas. Por ejemplo, el 41 se puede escribir de dos formas distintas

   41 =  2 +  3 +  5 + 7 + 11 + 13
   41 = 11 + 13 + 17

el 240 se puede escribir de tres formas

   240 =  17 +  19 + 23 + 29 + 31 + 37 + 41 + 43
   240 =  53 +  59 + 61 + 67
   240 = 113 + 127

y el 311 se puede escribir de 4 formas

   311 =  11 +  13 +  17 + 19 + 23 + 29 + 31 + 37 + 41 + 43 + 47
   311 =  31 +  37 +  41 + 43 + 47 + 53 + 59
   311 =  53 +  59 +  61 + 67 + 71
   311 = 101 + 103 + 107

Definir la función

   sumas :: Integer -> [[Integer]]

tal que (sumas x) es la lista de las formas de escribir x como suma
de dos o más números primos consecutivos. Por ejemplo,

   ghci> sumas 41
   [[2,3,5,7,11,13],[11,13,17]]
   ghci> sumas 240
   [[17,19,23,29,31,37,41,43],[53,59,61,67],[113,127]]
   ghci> sumas 311
   [[11,13,17,19,23,29,31,37,41,43,47],[31,37,41,43,47,53,59],[53,59,61,67,71],[101,103,107]]
   ghci> maximum [length (sumas n) | n <- [1..600]]
   4

Soluciones

import Data.Numbers.Primes (primes)
import Data.List (span)
 
sumas :: Integer -> [[Integer]]
sumas x = [ys | n <- takeWhile (< x) primes, 
                let ys = sumaDesde x n,
                not (null ys)]
 
-- (sumaDesde x n) es la lista de al menos dos números primos
-- consecutivos a partir del número primo n cuya suma es x, si existen y
-- la lista vacía en caso contrario. Por ejemplo,
--    sumaDesde 15 3  ==  [3,5,7]
--    sumaDesde  7 3  ==  []
sumaDesde :: Integer -> Integer -> [Integer]
sumaDesde x n | x == y    = take (1 + length us) ys
              | otherwise = []
    where ys       = dropWhile (<n) primes
          (us,y:_) = span (<x) (scanl1 (+) ys)
Avanzado

7 soluciones de “Números como sumas de primos consecutivos

  1. abrdelrod
    sumas :: Integer -> [[Integer]]
    sumas n = filter (not.null) (map (aux n) $ takeWhile (<n) primes)
     
    aux :: Integer -> Integer -> [Integer]
    aux n p | null xs || last xs /= n = []
            | otherwise = take (length xs) ys
            where xs = takeWhile (<=n) $ scanl1 (+) ys
                  ys = dropWhile (<p) primes
  2. josejuan

    Coste cuadrático

    sumas :: ℤ → [[]]
    sumas n = filter ((n ≡) ∘ ∑) $ concatMap tails $ inits $ takeWhile (<n) primes
  3. josejuan

    Coste lineal

    import Data.Numbers.Primes
    import Data.Sequence
    import Data.Foldable (toList)
    import Control.Monad (when)
    import Control.Monad.Trans.Writer (execWriter, tell)
     
    sumas :: ℤ → [[]]
    sumas n = execWriter $ it 0$ takeWhile (<n) primes
      where it s q ps | s ≤ n = do
                                   when (s  ≡  n) $ tell [toList q]
                                   when (ps ≢ []) $ it (s + head ps) (q |> head ps) (tail ps)
                      | s > n = it (s - z) q' ps where z :< q' = viewl q
     
    {- en un Atom
    > sumas 654321
    [[93427,93463,93479,93481,93487,93491,93493]]
    (2.70 secs, 340,211,456 bytes)
    -}
  4. fracruzam
    import Data.Numbers.Primes
     
    sumas :: Integer -> [[Integer]]
    sumas n = map reverse (conteo n xs xs [] 0)
      where xs = takeWhile (< n) primes
     
    conteo :: Integer -> [Integer] -> [Integer] -> [Integer] 
              -> Integer -> [[Integer]]
    conteo n (x:xs) (y:ys) zs s 
        | k >  n =         conteo n    xs  xs    []  0
        | k == n = (y:zs): conteo n    xs  xs    []  0
        | k <  n =         conteo n (x:xs) ys (y:zs) k
      where k = y + s
    conteo _  _      _     _   _  = []
  5. josejuan

    Coste lineal recorriendo con dos iteradores

    sumas :: ℤ → [[]]
    sumas n = it 0 ps ps
      where ps = takeWhile (≤n) primes
            it s uss@(u:us) dss@(d:ds) = case s `compare` n of
                                           EQ → takeWhile (<u) dss: it (s + u) us dss
                                           LT →                     it (s + u) us dss
                                           GT →                     it (s - d) uss ds
            it _ _ _ = []
     
    {- en el mismo Atom
    > zumas 654321
    [[93427,93463,93479,93481,93487,93491,93493]]
    (1.51 secs, 247,605,440 bytes)
    -}
  6. manvermor
    import Data.List
     
    sumas :: Integer -> [[Integer]]
    sumas n = nub [ xs | xs <- xss, sum xs == n]
       where xss = concatMap inits $ tails $ takeWhile (<n) primes
  7. Paola Cabrera Perza
    import Data.List
    import Data.Numbers.Primes
     
    primosMenores :: Integer-> [Integer]
    primosMenores n = takeWhile (<n) (primes)
     
    secuenciasConsecutivas :: Integer->[[Integer]]
    secuenciasConsecutivas n = 
        [xs | xs <- subsequences (primosMenores n),
              xs `isInfixOf` (primosMenores n)]
     
    sumas :: Integer-> [[Integer]]
    sumas n = [xs | xs <- secuenciasConsecutivas n, sum xs == n]

    (Muy poco eficiente)

Escribe tu solución

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