Números como sumas de primos consecutivos

PorJosé A. Alonso 27-marzo-20206-abril-2020

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

1 2	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

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

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]]

1	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

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]]

Soluciones

import Data.Numbers.Primes (primes)

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)

import Data.Numbers.Primes (primes)

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)

Otras soluciones

Se pueden escribir otras soluciones en los comentarios.
El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Pensamiento

«El desarrollo de las matemáticas hacia una mayor precisión ha llevado, como es bien sabido, a la formalización de grandes partes de las mismas, de modo que se puede probar cualquier teorema usando nada más que unas pocas reglas mecánicas.»

Kurt Gödel.

4 Comentarios

import Data.Numbers.Primes
import Data.List (genericTake)

sumas :: Integer -> [[Integer]]
sumas n = [y | y <- recopilaL (recopila n xs 1) xs, sum y == n]
  where xs = takeWhile (<=n) primes

recopilaL :: [Integer] ->  [Integer] -> [[Integer]]
recopilaL [] _          = []
recopilaL (x:xs) (y:ys) = genericTake x (y:ys) : recopilaL xs ys

recopila :: Integer ->  [Integer] -> Integer-> [Integer]
recopila _ [x] _ = []
recopila n xs _ | sum xs < n = [] 
recopila n (x:xs) z =
  until (\ z -> (sum (genericTake z (x:xs))) >= n) f z : recopila n xs z
  where f z = z+1

import Data.Numbers.Primes

import Data.List (genericTake)

sumas :: Integer -> [[Integer]]

sumas n = [y | y <- recopilaL (recopila n xs 1) xs, sum y == n]

where xs = takeWhile (<=n) primes

recopilaL :: [Integer] -> [Integer] -> [[Integer]]

recopilaL [] _ = []

recopilaL (x:xs) (y:ys) = genericTake x (y:ys) : recopilaL xs ys

recopila :: Integer -> [Integer] -> Integer-> [Integer]

recopila _ [x] _ = []

recopila n xs _ | sum xs < n = []

recopila n (x:xs) z =

until (\ z -> (sum (genericTake z (x:xs))) >= n) f z : recopila n xs z

where f z = z+1

Responder

import Data.Numbers.Primes

sumas :: Integer -> [[Integer]]
sumas n =
  [xs | xs <- listaCons (takeWhile (<= (div n 2)) primes
                         ++ [(head (dropWhile(<= (div n 2)) primes))])
      , sum xs == n]

listaCons :: [Integer] -> [[Integer]]
listaCons []     = []
listaCons (x:xs) = scanl (++) [x] [[n] | n <- xs] ++ listaCons xs

import Data.Numbers.Primes

sumas :: Integer -> [[Integer]]

sumas n =

[xs | xs <- listaCons (takeWhile (<= (div n 2)) primes

++ [(head (dropWhile(<= (div n 2)) primes))])

, sum xs == n]

listaCons :: [Integer] -> [[Integer]]

listaCons [] = []

listaCons (x:xs) = scanl (++) [x] [[n] | n <- xs] ++ listaCons xs

Responder

-- import Data.Numbers.Primes
import Data.List

sumas :: Integer -> [[Integer]]
sumas n = sumas' n (takeWhile (<n) primes)

sumas' :: Integer -> [Integer] -> [[Integer]]
sumas' n listaPrimos
  | listaPrimos == [] = []
  | otherwise         = [xs | xs <- inits listaPrimos, sum xs == n]
                        ++ sumas' n (tail listaPrimos)

-- import Data.Numbers.Primes

import Data.List

sumas :: Integer -> [[Integer]]

sumas n = sumas' n (takeWhile (<n) primes)

sumas' :: Integer -> [Integer] -> [[Integer]]

sumas' n listaPrimos

| listaPrimos == [] = []

| otherwise = [xs | xs <- inits listaPrimos, sum xs == n]

++ sumas' n (tail listaPrimos)

Responder

import Data.Numbers.Primes

sumas :: Integer -> [[Integer]]
sumas k = reverse $ aux k (takeWhile (< k-1) primes) []

aux2 :: Integer -> [Integer] -> Int -> [Integer]
aux2 k [] n = []
aux2 k xs n | n > length xs = []
            | s == k        = take n xs
            | s < k         = aux2 k xs (n+1)
            | otherwise     = []
  where s = sum (take n xs)

aux :: Integer -> [Integer] -> [[Integer]] -> [[Integer]]                    
aux k [] ys = ys
aux k xs ys | not (null zs) = aux k (tail xs) (zs:ys)
            | otherwise     = aux k (tail xs) ys
  where zs = aux2 k xs 2

import Data.Numbers.Primes

sumas :: Integer -> [[Integer]]

sumas k = reverse $ aux k (takeWhile (< k-1) primes) []

aux2 :: Integer -> [Integer] -> Int -> [Integer]

aux2 k [] n = []

aux2 k xs n | n > length xs = []

| s == k = take n xs

| s < k = aux2 k xs (n+1)

| otherwise = []

where s = sum (take n xs)

aux :: Integer -> [Integer] -> [[Integer]] -> [[Integer]]

aux k [] ys = ys

aux k xs ys | not (null zs) = aux k (tail xs) (zs:ys)

| otherwise = aux k (tail xs) ys

where zs = aux2 k xs 2

Responder

Números como sumas de primos consecutivos

Soluciones

Otras soluciones

Pensamiento

4 Comentarios

Leave a Reply to fercarnavCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Otras soluciones

Pensamiento

Se puede imprimir o compartir con

4 Comentarios

Leave a Reply to fercarnavCancel reply

Entradas recientes

Buscar

Correo electrónico