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

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

  1. Pedro Martín Chávez
    import Data.Numbers.Primes (primes)
    import Data.List (isInfixOf)
     
    sumas :: Integer -> [[Integer]]
    sumas n =
        [xs | xs <- subs $ primos n, sum xs == n, xs `isInfixOf` (primos n)]
            where primos n = takeWhile (<n) primes
                  subs [] = [[]]
                  subs (x:xs) = subs xs ++ map (x:) (subs xs)
  2. Jesús Navas Orozco
    import Data.Numbers.Primes
     
    sumas x = [ys| ys<- concat $ map (init.tails) (tail $ inits xs),
                   sum ys == x]
            where xs = takeWhile (<x) primes
    • Jesús Navas Orozco

      Simplificando con concatMap:

      sumas :: Integer -> [[Integer]]
      sumas x = [ys| ys<- concatMap (init.tails) (tail $ inits xs),
                     sum ys == x]
              where xs = takeWhile (<x) primes
  3. Pedro Martín Chávez
    import Data.Numbers.Primes (primes)
    import Data.List (tails)
     
    sumas :: Integer -> [[Integer]]
    sumas n =
        [reverse (aux n xs []) | xs <- tails $ primos n, sum (aux n xs []) == n]
            where primos n = takeWhile (<n) primes
                  aux _ [] _ = []
                  aux n (x:xs) ys | n < sum (x:ys) = ys
                                  | otherwise = aux n xs (x:ys)
  4. Javier Linares Torres
    import Data.Numbers.Primes(primes)
    import Data.List(inits)
     
    sumas :: Integer -> [[Integer]]
    sumas n =
     [ xs | m <- [0..(length ys)-1] , xs <- inits (drop m ys), sum xs == n]
     where ys = takeWhile (<n) primes
  5. josejuan
    {-# Language ViewPatterns #-}
    import           Data.Sequence (ViewL(..), (|>))
    import qualified Data.Sequence as S
    import           Data.Foldable (toList)
    import           Control.Monad.Writer
    import           Control.Monad
    import           Data.Numbers.Primes
    import           System.Environment
    import           Control.Parallel
    import           Control.Parallel.Strategies
     
    -- Para cualquier secuencia no decreciente de números, coste O(n), usando FIFO
    nsum :: Integer -> [Integer] -> [[Integer]]
    nsum n = execWriter . foldM_ pushOne (0, S.empty)
      where check z q                     = when (z == n && S.length q > 1) $ tell [toList q]
            pushOne (z, q) x              = check z_ q_ >> popWhile z_ q_
                                            where (z_, q_) = (z + x, q |> x)
            popWhile z q@(S.viewl->x:<q_) = if (z > n) then check (z - x) q_ >> popWhile (z - x) q_
                                                       else return (z, q)
            popWhile z q                  = return (z, q)
     
    -- Aplicada a los primos mientras dos no superen
    sumas n = nsum n $ ps primes
              where m = n `div` 2
                    ps (x:y:xs) | x <= m     = x: ps (y:xs)
                                | x + y <= n = x: ps (y:xs)
                                | otherwise  = [x]
     
    -- Paralelizable a tramos
    main = getArgs >>= print . maximum . withStrategy (parListChunk 500 rseq) .
                                         map (length . sumas) . enumFromTo 1 . read . head
     
    {-
     
    $ ghc -O3 -threaded -rtsopts nsum.hs
    [1 of 1] Compiling Main             ( nsum.hs, nsum.o )
    Linking nsum ...
     
    $ for i in $(seq 10 5 20); do time -f "N: ${i}000, Cpu: %E, Mem: %M Kbytes" ./nsum ${i}000 +RTS -N6 > /dev/null ; done
    N: 10000, Cpu: 0:00.44, Mem: 16472 Kbytes
    N: 15000, Cpu: 0:00.84, Mem: 13536 Kbytes
    N: 20000, Cpu: 0:01.36, Mem: 17396 Kbytes
     
    -}

Escribe tu solución

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