Menu Close

Números como sumas de primos consecutivos

José A. Alonso,

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