take

Números como sumas de primos consecutivos

PorJosé A. Alonso 15-abril-201625-abril-2021

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

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)

Números cuyos dígitos coinciden con los de sus factores primos

PorJosé A. Alonso 30-marzo-201625-marzo-2022

Un número n es especial si al unir los dígitos de sus factores primos, se obtienen exactamente los dígitos de n, aunque puede ser en otro orden. Por ejemplo, 1255 es especial, pues los factores primos de 1255 son 5 y 251.

Definir la función

   esEspecial :: Integer -> Bool

1	esEspecial :: Integer -> Bool

tal que (esEspecial n) se verifica si un número n es especial. Por ejemplo,

   esEspecial 1255 == True
   esEspecial 125  == False
   esEspecial 132  == False

esEspecial 1255 == True

esEspecial 125 == False

esEspecial 132 == False

Comprobar con QuickCheck que todo número primo es especial.

Calcular los 5 primeros números especiales que no son primos.

Soluciones

import Data.List (nub, sort)
import Data.Numbers.Primes (isPrime, primeFactors)
import Test.QuickCheck

esEspecial :: Integer -> Bool
esEspecial n = 
    sort (show n) == sort (concatMap show (nub (primeFactors n)))

-- La propiedad es
prop_primos:: Integer -> Property
prop_primos n = 
    isPrime (abs n) ==> esEspecial (abs n)

-- La comprobación es
--    ghci> quickCheck prop_primos
--    +++ OK, passed 100 tests.

-- El cálculo es
--    ghci> take 5 [n | n <- [2..], esEspecial n, not (isPrime n)]
--    [735,1255,3792,7236,11913]

import Data.List (nub, sort)

import Data.Numbers.Primes (isPrime, primeFactors)

import Test.QuickCheck

esEspecial :: Integer -> Bool

esEspecial n =

sort (show n) == sort (concatMap show (nub (primeFactors n)))

-- La propiedad es

prop_primos:: Integer -> Property

prop_primos n =

isPrime (abs n) ==> esEspecial (abs n)

-- La comprobación es

-- ghci> quickCheck prop_primos

-- +++ OK, passed 100 tests.

-- El cálculo es

-- ghci> take 5 [n | n <- [2..], esEspecial n, not (isPrime n)]

-- [735,1255,3792,7236,11913]

Comportamiento del último dígito en primos consecutivos

PorJosé A. Alonso 18-marzo-20162-mayo-2016

El pasado 11 de marzo se ha publicado el artículo Unexpected biases in the distribution of consecutive primes en el que muestra que los números primos repelen a otros primos que terminan en el mismo dígito.

La lista de los últimos dígitos de los 30 primeros números es

   [2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1,3,9,3,9,7,1,3,7,9,3]

1	[2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1,3,9,3,9,7,1,3,7,9,3]

Se observa que hay 6 números que su último dígito es un 1 y de sus consecutivos 4 terminan en 3 y 2 terminan en 7.

Definir la función

   distribucionUltimos :: Int -> M.Matrix Integer

1	distribucionUltimos :: Int -> M.Matrix Integer

tal que (distribucionUltimos n) es la matriz cuyo elemento (i,j) indica cuántos de los n primeros números primos terminan en i y su siguiente número primo termina en j. Por ejemplo,

   λ> distribucionUltimos 30
   ( 0 0 4 0 0 0 2 0 0 )
   ( 0 0 1 0 0 0 0 0 0 )
   ( 0 0 0 0 1 0 4 0 4 )
   ( 0 0 0 0 0 0 0 0 0 )
   ( 0 0 0 0 0 0 1 0 0 )
   ( 0 0 0 0 0 0 0 0 0 )
   ( 4 0 1 0 0 0 0 0 2 )
   ( 0 0 0 0 0 0 0 0 0 )
   ( 2 0 3 0 0 0 1 0 0 )
   
   λ> distribucionUltimos (10^5)
   ( 4104    0 7961    0    0    0 8297    0 4605 )
   (    0    0    1    0    0    0    0    0    0 )
   ( 5596    0 3604    0    1    0 7419    0 8387 )
   (    0    0    0    0    0    0    0    0    0 )
   (    0    0    0    0    0    0    1    0    0 )
   (    0    0    0    0    0    0    0    0    0 )
   ( 6438    0 6928    0    0    0 3627    0 8022 )
   (    0    0    0    0    0    0    0    0    0 )
   ( 8830    0 6513    0    0    0 5671    0 3995 )

λ> distribucionUltimos 30

( 0 0 4 0 0 0 2 0 0 )

( 0 0 1 0 0 0 0 0 0 )

( 0 0 0 0 1 0 4 0 4 )

( 0 0 0 0 0 0 0 0 0 )

( 0 0 0 0 0 0 1 0 0 )

( 0 0 0 0 0 0 0 0 0 )

( 4 0 1 0 0 0 0 0 2 )

( 0 0 0 0 0 0 0 0 0 )

( 2 0 3 0 0 0 1 0 0 )

λ> distribucionUltimos (10^5)

( 4104 0 7961 0 0 0 8297 0 4605 )

( 0 0 1 0 0 0 0 0 0 )

( 5596 0 3604 0 1 0 7419 0 8387 )

( 0 0 0 0 0 0 0 0 0 )

( 0 0 0 0 0 0 1 0 0 )

( 0 0 0 0 0 0 0 0 0 )

( 6438 0 6928 0 0 0 3627 0 8022 )

( 0 0 0 0 0 0 0 0 0 )

( 8830 0 6513 0 0 0 5671 0 3995 )

Nota: Se observa cómo se «repelen» ya que en las filas del 1, 3, 7 y 9 el menor elemento es el de la diagonal.

Soluciones

import Data.Numbers.Primes
import Data.Array
import qualified Data.Matrix as M

-- (ultimo n) es el último dígito de n.    
ultimo :: Integer -> Integer
ultimo n = n `mod` 10

-- ultimos es la lista de el último dígito de los primos.
--    λ> take 20 ultimos
--    [2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1]
ultimos :: [Integer]
ultimos = map ultimo primes

-- ultimosConsecutivos es la lista de los últimos dígitos de los primos
-- consecutivos. 
--    λ> take 10 ultimosConsecutivos
--    [(2,3),(3,5),(5,7),(7,1),(1,3),(3,7),(7,9),(9,3),(3,9),(9,1)]
ultimosConsecutivos :: [(Integer,Integer)]
ultimosConsecutivos = zip ultimos (tail ultimos)

-- (histograma r is) es el vector formado contando cuantas veces
-- aparecen los elementos del rango r en la lista de índices is. Por
-- ejemplo, 
--    ghci> histograma (0,5) [3,1,4,1,5,4,2,7]
--    array (0,5) [(0,0),(1,2),(2,1),(3,1),(4,2),(5,1)]
histograma :: (Ix a, Num b) => (a,a) -> [a] -> Array a b
histograma r is = 
    accumArray (+) 0 r [(i,1) | i <- is, inRange r i]

distribucionUltimos :: Int -> M.Matrix Integer
distribucionUltimos n =
    M.fromList 9 9 (elems (histograma ((1,1),(9,9)) (take n ultimosConsecutivos)))

import Data.Numbers.Primes

import Data.Array

import qualified Data.Matrix as M

-- (ultimo n) es el último dígito de n.

ultimo :: Integer -> Integer

ultimo n = n `mod` 10

-- ultimos es la lista de el último dígito de los primos.

-- λ> take 20 ultimos

-- [2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1]

ultimos :: [Integer]

ultimos = map ultimo primes

-- ultimosConsecutivos es la lista de los últimos dígitos de los primos

-- consecutivos.

-- λ> take 10 ultimosConsecutivos

-- [(2,3),(3,5),(5,7),(7,1),(1,3),(3,7),(7,9),(9,3),(3,9),(9,1)]

ultimosConsecutivos :: [(Integer,Integer)]

ultimosConsecutivos = zip ultimos (tail ultimos)

-- (histograma r is) es el vector formado contando cuantas veces

-- aparecen los elementos del rango r en la lista de índices is. Por

-- ejemplo,

-- ghci> histograma (0,5) [3,1,4,1,5,4,2,7]

-- array (0,5) [(0,0),(1,2),(2,1),(3,1),(4,2),(5,1)]

histograma :: (Ix a, Num b) => (a,a) -> [a] -> Array a b

histograma r is =

accumArray (+) 0 r [(i,1) | i <- is, inRange r i]

distribucionUltimos :: Int -> M.Matrix Integer

distribucionUltimos n =

M.fromList 9 9 (elems (histograma ((1,1),(9,9)) (take n ultimosConsecutivos)))

Solución en Maxima

distribucionUltimos (n) := block (
  [r : zeromatrix (9,9),
   xs : ultimos (n),
   i, j],
  unless length (xs) < 2 do
    ( i : first (xs),
      j : second (xs),
      r[i,j] : 1 + r[i,j],
      xs : rest (xs)),
  r)$

/* ultimos(n) es la lista del último dígito de los n primeros primos.
      (%i5) ultimos (30);
      (%o5) [2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1,3,9,3,9,7,1,3,7,9,3,7]
*/
ultimos (n) := block ([r:[], p:2],
  for k from 0 thru n do
    ( r : cons (mod (p,10), r),
      p : next_prime (p) ),
  reverse (r))$

distribucionUltimos (n) := block (

[r : zeromatrix (9,9),

xs : ultimos (n),

i, j],

unless length (xs) < 2 do

( i : first (xs),

j : second (xs),

r[i,j] : 1 + r[i,j],

xs : rest (xs)),

r)$

/* ultimos(n) es la lista del último dígito de los n primeros primos.

(%i5) ultimos (30);

(%o5) [2,3,5,7,1,3,7,9,3,9,1,7,1,3,7,3,9,1,7,1,3,9,3,9,7,1,3,7,9,3,7]

ultimos (n) := block ([r:[], p:2],

for k from 0 thru n do

( r : cons (mod (p,10), r),

p : next_prime (p) ),

reverse (r))$

Sumas digitales de primos consecutivos

PorJosé A. Alonso 22-enero-20161-mayo-2016

Definir la función

   primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]

1	primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]

tal que (primosConsecutivosConSumasDigitalesPrimas k) es la sucesión de listas de k primos consecutivos tales que las sumas ordenadas de sus dígitos también son primos consecutivos. Por ejemplo,

   λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 2)
   [[2,3],[3,5],[5,7],[41,43],[43,47]]
   λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 3)
   [[2,3,5],[3,5,7],[41,43,47],[191,193,197],[193,197,199]]
   λ> take 4 (primosConsecutivosConSumasDigitalesPrimas 4)
   [[2,3,5,7],[3,5,7,11],[191,193,197,199],[821,823,827,829]]
   λ> primosConsecutivosConSumasDigitalesPrimas 4 !! 50
   [129197,129209,129221,129223]

λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 2)

[[2,3],[3,5],[5,7],[41,43],[43,47]]

λ> take 5 (primosConsecutivosConSumasDigitalesPrimas 3)

[[2,3,5],[3,5,7],[41,43,47],[191,193,197],[193,197,199]]

λ> take 4 (primosConsecutivosConSumasDigitalesPrimas 4)

[[2,3,5,7],[3,5,7,11],[191,193,197,199],[821,823,827,829]]

λ> primosConsecutivosConSumasDigitalesPrimas 4 !! 50

[129197,129209,129221,129223]

Soluciones

import Data.Char (digitToInt)
import Data.List (isPrefixOf, sort, tails)
import Data.Numbers.Primes

primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]
primosConsecutivosConSumasDigitalesPrimas k = 
    [xs | xs <- map (take k) (tails primes),
          primosConsecutivos (sort (map sumaDigital xs))]

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,
--    digitos 325  ==  [3,2,5]
digitos :: Integer -> [Integer]
digitos n = [read [d] | d <- show n]

-- (sumaDigital n) es la suma de los dígitos de n. Por ejemplo, 
--    sumaDigital 325  ==  10
sumaDigital :: Integer -> Integer
sumaDigital = sum . digitos

-- (primosConsecutivos xs) se verifica si xs es una lista de primos
-- consecutivos. Por ejemplo,
--    primosConsecutivos [5,7,11]  ==  True
--    primosConsecutivos [5,7,17]  ==  False
primosConsecutivos :: [Integer] -> Bool
primosConsecutivos (x:xs) =
    isPrefixOf (x:xs) (dropWhile (<x) primes)

import Data.Char (digitToInt)

import Data.List (isPrefixOf, sort, tails)

import Data.Numbers.Primes

primosConsecutivosConSumasDigitalesPrimas :: Int -> [[Integer]]

primosConsecutivosConSumasDigitalesPrimas k =

[xs | xs <- map (take k) (tails primes),

primosConsecutivos (sort (map sumaDigital xs))]

-- (digitos n) es la lista de los dígitos de n. Por ejemplo,

-- digitos 325 == [3,2,5]

digitos :: Integer -> [Integer]

digitos n = [read [d] | d <- show n]

-- (sumaDigital n) es la suma de los dígitos de n. Por ejemplo,

-- sumaDigital 325 == 10

sumaDigital :: Integer -> Integer

sumaDigital = sum . digitos

-- (primosConsecutivos xs) se verifica si xs es una lista de primos

-- consecutivos. Por ejemplo,

-- primosConsecutivos [5,7,11] == True

-- primosConsecutivos [5,7,17] == False

primosConsecutivos :: [Integer] -> Bool

primosConsecutivos (x:xs) =

isPrefixOf (x:xs) (dropWhile (<x) primes)

Referencias

Basado en el artículo DigitSums of some consecutive primes del blog Fun With Num3ers.

Inserciones por posición

PorJosé A. Alonso 25-diciembre-20151-enero-2016

Definir la función

   inserta :: [a] -> [[a]] -> [[a]]

1	inserta :: [a] -> [[a]] -> [[a]]

tal que (inserta xs yss) es la lista obtenida insertando

el primer elemento de xs como primero en la primera lista de yss,
el segundo elemento de xs como segundo en la segunda lista de yss (si la segunda lista de yss tiene al menos un elemento),
el tercer elemento de xs como tercero en la tercera lista de yss (si la tercera lista de yss tiene al menos dos elementos),

y así sucesivamente. Por ejemplo,

   inserta [1,2,3] [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,3,8]]
   inserta [1,2,3] [[4,7],[] ,[9,5,8]]  ==  [[1,4,7],[],   [9,5,3,8]]
   inserta [1,2]   [[4,7],[6],[9,5,8]]  ==  [[1,4,7],[6,2],[9,5,8]]
   inserta [1,2,3] [[4,7],[6]]          ==  [[1,4,7],[6,2]]
   inserta "tad"   ["odo","pra","naa"]  ==  ["todo","para","nada"]

inserta [1,2,3] [[4,7],[6],[9,5,8]] == [[1,4,7],[6,2],[9,5,3,8]]

inserta [1,2,3] [[4,7],[] ,[9,5,8]] == [[1,4,7],[], [9,5,3,8]]

inserta [1,2] [[4,7],[6],[9,5,8]] == [[1,4,7],[6,2],[9,5,8]]

inserta [1,2,3] [[4,7],[6]] == [[1,4,7],[6,2]]

inserta "tad" ["odo","pra","naa"] == ["todo","para","nada"]

Nota: Este ejercicio es parte del examen del grupo 2 del 4 de diciembre.

Soluciones

-- 1ª solución
-- ===========

inserta :: [a] -> [[a]] -> [[a]]
inserta xs yss = aux xs yss 0 where
    aux [] yss _ = yss
    aux xs []  _ = []
    aux (x:xs) (ys:yss) n 
        | length us == n = (us ++ x : vs) : aux xs yss (n+1)
        | otherwise      = ys : aux xs yss (n+1)
        where (us,vs) = splitAt n ys

-- 2ª solución
-- ===========

inserta2 :: [a] -> [[a]] -> [[a]]
inserta2 xs yss =  
    [ins n x ys | (n,x,ys) <- zip3 [0..] xs yss] ++ drop (length xs) yss
 
ins :: Int -> a -> [a] -> [a]
ins n x ys | length ys < n  = ys
           | otherwise      = take n ys ++ x : drop n ys

-- Comparación de eficiencia
-- =========================

--    λ> let n = 10000 in length (inserta [1..n] (replicate n (replicate n 0)))
--    10000
--    (3.28 secs, 6,400,568,776 bytes)
--    λ> let n = 10000 in length (inserta2 [1..n] (replicate n (replicate n 0)))
--    10000
--    (0.02 secs, 0 bytes)

-- 1ª solución

-- ===========

inserta :: [a] -> [[a]] -> [[a]]

inserta xs yss = aux xs yss 0 where

aux [] yss _ = yss

aux xs [] _ = []

aux (x:xs) (ys:yss) n

| length us == n = (us ++ x : vs) : aux xs yss (n+1)

| otherwise = ys : aux xs yss (n+1)

where (us,vs) = splitAt n ys

-- 2ª solución

-- ===========

inserta2 :: [a] -> [[a]] -> [[a]]

inserta2 xs yss =

[ins n x ys | (n,x,ys) <- zip3 [0..] xs yss] ++ drop (length xs) yss

ins :: Int -> a -> [a] -> [a]

ins n x ys | length ys < n = ys

| otherwise = take n ys ++ x : drop n ys

-- Comparación de eficiencia

-- =========================

-- λ> let n = 10000 in length (inserta [1..n] (replicate n (replicate n 0)))

-- 10000

-- (3.28 secs, 6,400,568,776 bytes)

-- λ> let n = 10000 in length (inserta2 [1..n] (replicate n (replicate n 0)))

-- 10000

-- (0.02 secs, 0 bytes)

Números como sumas de primos consecutivos

Soluciones

Números cuyos dígitos coinciden con los de sus factores primos

Soluciones

Comportamiento del último dígito en primos consecutivos

Soluciones

Solución en Maxima

Sumas digitales de primos consecutivos

Soluciones

Referencias

Inserciones por posición

Soluciones

Entradas recientes

Buscar

Correo electrónico