Menu Close

Números como sumas de primos consecutivos

José A. Alonso,

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)
Posted in Avanzado
Tagged , , , , , , , , ,

7 Comments

  1. eliguivil
    Responder 
    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
    Responder 
    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
      Responder

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