Exercitium

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)

Caminos reducidos

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

Un camino es una sucesión de pasos en una de las cuatros direcciones Norte, Sur, Este, Oeste. Ir en una dirección y a continuación en la opuesta es un esfuerzo que se puede reducir, Por ejemplo, el camino [Norte,Sur,Este,Sur] se puede reducir a [Este,Sur].

Un camino se dice que es reducido si no tiene dos pasos consecutivos en direcciones opuesta. Por ejemplo, [Este,Sur] es reducido y [Norte,Sur,Este,Sur] no lo es.

En Haskell, las direcciones y los caminos se pueden definir por

   data Direccion = N | S | E | O deriving (Show, Eq)
   type Camino = [Direccion]

1 2	data Direccion = N \| S \| E \| O deriving (Show, Eq) type Camino = [Direccion]

Definir la función

   reducido :: Camino -> Camino

1	reducido :: Camino -> Camino

tal que (reducido ds) es el camino reducido equivalente al camino ds. Por ejemplo,

   reducido []                              ==  []
   reducido [N]                             ==  [N]
   reducido [N,O]                           ==  [N,O]
   reducido [N,O,E]                         ==  [N]
   reducido [N,O,E,S]                       ==  [] 
   reducido [N,O,S,E]                       ==  [N,O,S,E]
   reducido [S,S,S,N,N,N]                   ==  []
   reducido [N,S,S,E,O,N]                   ==  []
   reducido [N,S,S,E,O,N,O]                 ==  [O]
   reducido (take (10^7) (cycle [N,E,O,S])) ==  []

reducido [] == []

reducido [N] == [N]

reducido [N,O] == [N,O]

reducido [N,O,E] == [N]

reducido [N,O,E,S] == []

reducido [N,O,S,E] == [N,O,S,E]

reducido [S,S,S,N,N,N] == []

reducido [N,S,S,E,O,N] == []

reducido [N,S,S,E,O,N,O] == [O]

reducido (take (10^7) (cycle [N,E,O,S])) == []

Nótese que en el penúltimo ejemplo las reducciones son

       [N,S,S,E,O,N,O]  
   --> [S,E,O,N,O]  
   --> [S,N,O]  
   --> [O]

[N,S,S,E,O,N,O]

--> [S,E,O,N,O]

--> [S,N,O]

--> [O]

Soluciones

data Direccion = N | S | E | O deriving (Show, Eq)

type Camino = [Direccion]

-- 1ª solución (por recursión):
reducido1 :: Camino -> Camino
reducido1 [] = []
reducido1 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido1 ds

opuesta :: Direccion -> Direccion
opuesta N = S
opuesta S = N
opuesta E = O
opuesta O = E

-- 2ª solución (por plegado)
reducido2 :: Camino -> Camino
reducido2 = foldr aux []
    where aux N (S:xs) = xs
          aux S (N:xs) = xs
          aux E (O:xs) = xs
          aux O (E:xs) = xs
          aux x xs     = x:xs

-- 3ª solución 
reducido3 :: Camino -> Camino
reducido3 []       = []
reducido3 (N:S:ds) = reducido3 ds
reducido3 (S:N:ds) = reducido3 ds
reducido3 (E:O:ds) = reducido3 ds
reducido3 (O:E:ds) = reducido3 ds
reducido3 (d:ds) | null ds'                = [d]
                 | d == opuesta (head ds') = tail ds'
                 | otherwise               = d:ds'
    where ds' = reducido3 ds

-- 4ª solución
reducido4 :: Camino -> Camino
reducido4 ds = reverse (aux ([],ds)) where 
    aux (N:xs, S:ys) = aux (xs,ys)
    aux (S:xs, N:ys) = aux (xs,ys)
    aux (E:xs, O:ys) = aux (xs,ys)
    aux (O:xs, E:ys) = aux (xs,ys)
    aux (  xs, y:ys) = aux (y:xs,ys)
    aux (  xs,   []) = xs

-- Comparación de eficiencia
--    ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (3.87 secs, 460160736 bytes)
--    ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (1.16 secs, 216582880 bytes)
--    ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.58 secs, 98561872 bytes)
--    ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))
--    []
--    (0.64 secs, 176154640 bytes)
--    
--    ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (5.43 secs, 962694784 bytes)
--    ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))
--    []
--    (9.29 secs, 1722601528 bytes)
-- 
--    ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (4.52 secs, 547004960 bytes)
--    ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])
--    400002
--    (2.17 secs, 379049224 bytes)

data Direccion = N | S | E | O deriving (Show, Eq)

type Camino = [Direccion]

-- 1ª solución (por recursión):

reducido1 :: Camino -> Camino

reducido1 [] = []

reducido1 (d:ds) | null ds' = [d]

| d == opuesta (head ds') = tail ds'

| otherwise = d:ds'

where ds' = reducido1 ds

opuesta :: Direccion -> Direccion

opuesta N = S

opuesta S = N

opuesta E = O

opuesta O = E

-- 2ª solución (por plegado)

reducido2 :: Camino -> Camino

reducido2 = foldr aux []

where aux N (S:xs) = xs

aux S (N:xs) = xs

aux E (O:xs) = xs

aux O (E:xs) = xs

aux x xs = x:xs

-- 3ª solución

reducido3 :: Camino -> Camino

reducido3 [] = []

reducido3 (N:S:ds) = reducido3 ds

reducido3 (S:N:ds) = reducido3 ds

reducido3 (E:O:ds) = reducido3 ds

reducido3 (O:E:ds) = reducido3 ds

reducido3 (d:ds) | null ds' = [d]

| d == opuesta (head ds') = tail ds'

| otherwise = d:ds'

where ds' = reducido3 ds

-- 4ª solución

reducido4 :: Camino -> Camino

reducido4 ds = reverse (aux ([],ds)) where

aux (N:xs, S:ys) = aux (xs,ys)

aux (S:xs, N:ys) = aux (xs,ys)

aux (E:xs, O:ys) = aux (xs,ys)

aux (O:xs, E:ys) = aux (xs,ys)

aux ( xs, y:ys) = aux (y:xs,ys)

aux ( xs, []) = xs

-- Comparación de eficiencia

-- ghci> reducido1 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (3.87 secs, 460160736 bytes)

-- ghci> reducido2 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (1.16 secs, 216582880 bytes)

-- ghci> reducido3 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (0.58 secs, 98561872 bytes)

-- ghci> reducido4 (take (10^6) (cycle [N,E,O,S]))

-- []

-- (0.64 secs, 176154640 bytes)

-- ghci> reducido3 (take (10^7) (cycle [N,E,O,S]))

-- []

-- (5.43 secs, 962694784 bytes)

-- ghci> reducido4 (take (10^7) (cycle [N,E,O,S]))

-- []

-- (9.29 secs, 1722601528 bytes)

-- ghci> length $ reducido3 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])

-- 400002

-- (4.52 secs, 547004960 bytes)

-- ghci> length $ reducido4 (take 2000000 $ cycle [N,O,N,S,E,N,S,O,S,S])

-- 400002

-- (2.17 secs, 379049224 bytes)

Primos permutables

PorJosé A. Alonso 11-abril-201618-abril-2016

Un primo permutable es un número primo tal que todos los números obtenidos permutando sus cifras son primos. Por ejemplo, 337 es un primo permutable ya que 337, 373 y 733 son primos.

Definir las funciones

   esPrimoPermutable :: Integer -> Bool
   primosPermutables :: [Integer]

1 2	esPrimoPermutable :: Integer -> Bool primosPermutables :: [Integer]

tales que

(esPrimoPermutable x) se verifica si x es un primo permutable. Por ejemplo,

     esPrimoPermutable 97  ==  True
     esPrimoPermutable 337 ==  True
     esPrimoPermutable 23  ==  False

esPrimoPermutable 97 == True

esPrimoPermutable 337 == True

esPrimoPermutable 23 == False

primosPermutables es la lista de los primos permutables. Por ejemplo,

     λ> take 20 primosPermutables
     [2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,199,311,337,373,733]

1 2	λ> take 20 primosPermutables [2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,199,311,337,373,733]

Soluciones

import Data.List (nub, permutations)
import Data.Numbers.Primes (primes, isPrime)

-- 1ª solución
-- ===========
    
esPrimoPermutable :: Integer -> Bool
esPrimoPermutable x =
    all isPrime (permutacionesN x)

permutacionesN :: Integer -> [Integer]
permutacionesN x =
    [read ys | ys <- nub (permutations xs)]
    where xs = show x
          n  = length xs
        
primosPermutables :: [Integer]
primosPermutables =
    [x | x <- primes, esPrimoPermutable x]

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

esPrimoPermutable2 :: Integer -> Bool
esPrimoPermutable2 = all isPrime . map read . nub . permutations . show
 
primosPermutables2 :: [Integer]
primosPermutables2 = filter esPrimoPermutable2 primes

import Data.List (nub, permutations)

import Data.Numbers.Primes (primes, isPrime)

-- 1ª solución

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

esPrimoPermutable :: Integer -> Bool

esPrimoPermutable x =

all isPrime (permutacionesN x)

permutacionesN :: Integer -> [Integer]

permutacionesN x =

[read ys | ys <- nub (permutations xs)]

where xs = show x

n = length xs

primosPermutables :: [Integer]

primosPermutables =

[x | x <- primes, esPrimoPermutable x]

-- 2ª solución

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

esPrimoPermutable2 :: Integer -> Bool

esPrimoPermutable2 = all isPrime . map read . nub . permutations . show

primosPermutables2 :: [Integer]

primosPermutables2 = filter esPrimoPermutable2 primes

Referencias

Permutable prime en Wikipedia.
Sucesión A003459 de la OEIS.

Raíz entera

PorJosé A. Alonso 8-abril-20161-mayo-2016

Definir la función

   raizEnt :: Integer -> Integer -> Integer

1	raizEnt :: Integer -> Integer -> Integer

tal que (raizEnt x n) es la raíz entera n-ésima de x; es decir, el mayor número entero y tal que y^n <= x. Por ejemplo,

   raizEnt  8 3      ==  2
   raizEnt  9 3      ==  2
   raizEnt 26 3      ==  2
   raizEnt 27 3      ==  3
   raizEnt (10^50) 2 ==  10000000000000000000000000

raizEnt 8 3 == 2

raizEnt 9 3 == 2

raizEnt 26 3 == 2

raizEnt 27 3 == 3

raizEnt (10^50) 2 == 10000000000000000000000000

Comprobar con QuickCheck que para todo número natural n,

    raizEnt (10^(2*n)) 2 == 10^n

1	raizEnt (10^(2*n)) 2 == 10^n

Soluciones

import Test.QuickCheck

-- 1ª definición
raizEnt1 :: Integer -> Integer -> Integer
raizEnt1 x n =
    last (takeWhile (\y -> y^n <= x) [0..])

-- 2ª definición         
raizEnt2 :: Integer -> Integer -> Integer
raizEnt2 x n =
    floor ((fromIntegral x)**(1 / fromIntegral n))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,
--    λ> raizEnt2 (10^50) 2 == 10^25
--    False
          
-- 3ª definición          
raizEnt3 :: Integer -> Integer -> Integer
raizEnt3 x n = aux (1,x)
    where aux (a,b) | d == x    = c
                    | c == a    = c
                    | d < x     = aux (c,b)
                    | otherwise = aux (a,c) 
              where c = (a+b) `div` 2
                    d = c^n

-- Comparación de eficiencia
--    λ> raizEnt1 (10^14) 2
--    10000000
--    (6.15 secs, 6,539,367,976 bytes)
--    λ> raizEnt2 (10^14) 2
--    10000000
--    (0.00 secs, 0 bytes)
--    λ> raizEnt3 (10^14) 2
--    10000000
--    (0.00 secs, 25,871,944 bytes)
--    
--    λ> raizEnt2 (10^50) 2
--    9999999999999998758486016
--    (0.00 secs, 0 bytes)
--    λ> raizEnt3 (10^50) 2
--    10000000000000000000000000
--    (0.00 secs, 0 bytes)
                        
-- La propiedad es                        
prop_raizEnt :: Integer -> Bool
prop_raizEnt n =
    raizEnt3 (10^(2*m)) 2 == 10^m
    where m = abs n

-- La comprobación es              
--    λ> quickCheck prop_raizEnt
--    +++ OK, passed 100 tests.

import Test.QuickCheck

-- 1ª definición

raizEnt1 :: Integer -> Integer -> Integer

raizEnt1 x n =

last (takeWhile (\y -> y^n <= x) [0..])

-- 2ª definición

raizEnt2 :: Integer -> Integer -> Integer

raizEnt2 x n =

floor ((fromIntegral x)**(1 / fromIntegral n))

-- Nota. La definición anterior falla para números grandes. Por ejemplo,

-- λ> raizEnt2 (10^50) 2 == 10^25

-- False

-- 3ª definición

raizEnt3 :: Integer -> Integer -> Integer

raizEnt3 x n = aux (1,x)

where aux (a,b) | d == x = c

| c == a = c

| d < x = aux (c,b)

| otherwise = aux (a,c)

where c = (a+b) `div` 2

d = c^n

-- Comparación de eficiencia

-- λ> raizEnt1 (10^14) 2

-- 10000000

-- (6.15 secs, 6,539,367,976 bytes)

-- λ> raizEnt2 (10^14) 2

-- 10000000

-- (0.00 secs, 0 bytes)

-- λ> raizEnt3 (10^14) 2

-- 10000000

-- (0.00 secs, 25,871,944 bytes)

-- λ> raizEnt2 (10^50) 2

-- 9999999999999998758486016

-- (0.00 secs, 0 bytes)

-- λ> raizEnt3 (10^50) 2

-- 10000000000000000000000000

-- (0.00 secs, 0 bytes)

-- La propiedad es

prop_raizEnt :: Integer -> Bool

prop_raizEnt n =

raizEnt3 (10^(2*m)) 2 == 10^m

where m = abs n

-- La comprobación es

-- λ> quickCheck prop_raizEnt

-- +++ OK, passed 100 tests.

Soluciones en Maxima

raizEnt (x,n) := inrt (x,n)$

1	raizEnt (x,n) := inrt (x,n)$

Números de Lucas

PorJosé A. Alonso 7-abril-201614-abril-2016

Los números de Lucas son los elementos de la sucesión L(n) definida por

   L(0) = 2
   L(1) = 1
   L(n) = L(n-1) + L(n-2), si n > 1.

L(0) = 2

L(1) = 1

L(n) = L(n-1) + L(n-2), si n > 1.

Los primeros números de Lucas son

   2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...

1	2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, ...

Definir las funciones

   nLucas :: Integer -> Integer 
   lucas  :: [Integer]

1 2	nLucas :: Integer -> Integer lucas :: [Integer]

tales que

(nLucas n) es el n-ésimo número de Lucas. Por ejemplo,

   nLucas 5                       ==  11
   nLucas 32                      ==  4870847
   length (show (nLucas (10^5)))  ==  20899

nLucas 5 == 11

nLucas 32 == 4870847

length (show (nLucas (10^5))) == 20899

lucas es la lista de los números de Lucas. Por ejemplo,

   take 11 lucas ==  [2,1,3,4,7,11,18,29,47,76,123]

1	take 11 lucas == [2,1,3,4,7,11,18,29,47,76,123]

Soluciones

import Data.List (genericIndex)

-- 1ª definición
-- =============

nLucas1 :: Integer -> Integer
nLucas1 0 = 2
nLucas1 1 = 1
nLucas1 n = nLucas1 (n-1) + nLucas1 (n-2)

lucas1 :: [Integer]
lucas1 = [nLucas1 n | n <- [0..]]

-- 2ª definición
-- =============

lucas2 :: [Integer]
lucas2 = 2 : 1 : zipWith (+) lucas2 (tail lucas2)

nLucas2 :: Integer -> Integer
nLucas2 n = lucas2 `genericIndex` n

-- 3ª definición
-- =============

lucas3  :: [Integer]
lucas3 = 2 : scanl (+) 1 lucas3
 
nLucas3 :: Integer -> Integer
nLucas3 = genericIndex lucas3
            
-- Comparación de eficiencia
-- =========================

--    λ> nLucas1 32
--    4870847
--    (3.22 secs, 1,467,677,208 bytes)
--    λ> nLucas2 32
--    4870847
--    (0.00 secs, 0 bytes)
--    λ> nLucas3 32
--    4870847
--    (0.00 secs, 0 bytes)
--    
--    λ> length (show (nLucas2 230000))
--    48068
--    (1.57 secs, 2,415,008,392 bytes)
--    λ> length (show (nLucas3 230000))
--    48068
--    (2.08 secs, 2,411,107,352 bytes)

import Data.List (genericIndex)

-- 1ª definición

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

nLucas1 :: Integer -> Integer

nLucas1 0 = 2

nLucas1 1 = 1

nLucas1 n = nLucas1 (n-1) + nLucas1 (n-2)

lucas1 :: [Integer]

lucas1 = [nLucas1 n | n <- [0..]]

-- 2ª definición

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

lucas2 :: [Integer]

lucas2 = 2 : 1 : zipWith (+) lucas2 (tail lucas2)

nLucas2 :: Integer -> Integer

nLucas2 n = lucas2 `genericIndex` n

-- 3ª definición

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

lucas3 :: [Integer]

lucas3 = 2 : scanl (+) 1 lucas3

nLucas3 :: Integer -> Integer

nLucas3 = genericIndex lucas3

-- Comparación de eficiencia

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

-- λ> nLucas1 32

-- 4870847

-- (3.22 secs, 1,467,677,208 bytes)

-- λ> nLucas2 32

-- 4870847

-- (0.00 secs, 0 bytes)

-- λ> nLucas3 32

-- 4870847

-- (0.00 secs, 0 bytes)

-- λ> length (show (nLucas2 230000))

-- 48068

-- (1.57 secs, 2,415,008,392 bytes)

-- λ> length (show (nLucas3 230000))

-- 48068

-- (2.08 secs, 2,411,107,352 bytes)

Soluciones en Maxima

nLucas (n) := lucas (n)$

1	nLucas (n) := lucas (n)$

La evaluación de los ejemplos es

(%i5) nLucas (5);
(%o5) 11
(%i6) nLucas (32);
(%o6) 4870847

(%i5) nLucas (5);

(%o5) 11

(%i6) nLucas (32);

(%o6) 4870847

Números como sumas de primos consecutivos

Soluciones

Caminos reducidos

Soluciones

Primos permutables

Soluciones

Referencias

Raíz entera

Soluciones

Soluciones en Maxima

Números de Lucas

Soluciones

Soluciones en Maxima

Entradas recientes

Buscar

Correo electrónico