Menu Close

Números como sumas de primos consecutivos

El número 311 se puede escribir de 5 formas distintas como suma de 1 o más primos consecutivos

   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
   311 = 311

el número 41 se puede escribir de 4 formas

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

y el número 14 no se puede escribir como suma de primos consecutivos.

Definir la función

   sumas :: Integer -> [[Integer]]

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

   λ> 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],[311]]
   λ> sumas 41
   [[2,3,5,7,11,13],[11,13,17],[41]]
   λ> sumas 14
   []
   λ> [length (sumas n) | n <- [0..20]]
   [0,0,1,1,0,2,0,1,1,0,1,1,1,1,0,1,0,2,1,1,0]
   λ> maximum [length (sumas n) | n <- [1..600]]
   5

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)

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

  1. eliguivil
    sumas :: Integer -> [[Integer]]
    sumas n = filter (xs -> sum xs == n) ys
      where
        ys = sublistas $ takeWhile (<= n) primes
        sublistas [] = []
        sublistas [c] = [[c]]
        sublistas cs = inits cs ++ sublistas (tail cs)
  2. eliguivil
    import Data.List (inits)
     
    sumas :: Integer -> [[Integer]]
    sumas n = filter (xs -> sum xs == n) ys
      where
        ys = sublistas $ takeWhile (<= n) primes
        sublistas [] = []
        sublistas [c] = [[c]]
        sublistas cs = inits cs ++ sublistas (tail cs)
    • eliguivil

      corrección

      import Data.List (inits)
      import Data.Numbers.Primes (primes)
       
      sumas :: Integer -> [[Integer]]
      sumas n = filter (xs -> sum xs == n) ys
        where
          ys = sublistas $ takeWhile (<= n) primes
          sublistas [] = []
          sublistas [c] = [[c]]
          sublistas cs = inits cs ++ sublistas (tail cs)
  3. enrnarbej
    import Data.Numbers.Primes
    import Data.List
     
    sumas :: Integer -> [[Integer]]
    sumas n = (filter (x -> sum x == n) . subConsecutivos . takeWhile (<=n)) primes
     
    subConsecutivos :: [Integer] -> [[Integer]]
    subConsecutivos []     = []
    subConsecutivos (x:xs) = scanl (x y -> x ++ [y]) [x] xs ++ subConsecutivos xs
  4. albcercid
    import Data.Numbers.Primes
     
    sumas :: Integer -> [[Integer]]
    sumas 0 = []
    sumas n = aux (takeWhile (n>=) primes) []
        where aux [] zs | sum zs == n = [reverse zs]
                        | sum zs > n = aux [] (init zs)
                        | otherwise = []
              aux (x:xs) ys | t < n = aux xs (x:ys)
                            | t == n = (reverse ys):aux (x:xs) (init ys)
                            | otherwise = aux (x:xs) (init ys)
                            where t = sum ys
  5. marlobrip
    import Data.List
    import Data.Numbers.Primes
     
    sumas :: Integer -> [[Integer]]
    sumas n = [xs | xs <- (posibles n), sum xs == n, primosConsecutivos xs]
         where posibles n = subsequences [ x | x <-[2..n], isPrime x]
     
    primosConsecutivos :: [Integer] -> Bool
    primosConsecutivos (x:y:xs) | primosEntre x y == [] = primosConsecutivos (y:xs)
                                | otherwise = False
    primosConsecutivos [x] = True
    primosConsecutivos [] = True
     
    primosEntre :: Integer -> Integer -> [Integer]
    primosEntre x y = [ x | x <- [x+1..y-1], isPrime x]
  6. Juanjo Ortega (juaorture)
    import Data.Numbers.Primes
    import Data.List
     
    sumas :: Integer -> [[Integer]]
    sumas x | x < 2     = []
            | otherwise = nub $ sort <$> aux x 0 True
          where aux x n b | x == 0     = [[]]
                          | x < 0      = []
                          | null zs    = []
                          | b == False = [ a:xs | let a = head zs, xs <- aux (x-a) a b]
                          | otherwise  = [ a:xs | a <- zs, xs <- aux (x-a) a False]
                    where zs = dropWhile (<= n) (takeWhile (<= x) primes)

Escribe tu solución

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