null

Sucesiones de listas de números

PorJosé A. Alonso 20-mayo-201626-marzo-2022

En la Olimpiada Internacional de Matemáticas del 2012 se propuso el siguiente problema:

Varios enteros positivos se escriben en una lista. Iterativamente, Alicia elige dos números adyacentes x e y tales que x > y y x está a la izquierda de y y reemplaza el par (x,y) por (y+1,x) o (x-1,x). Demostrar que sólo puede aplicar un número finito de dichas iteraciones.

Por ejemplo, las transformadas de la lista [1,3,2] son [1,2,3] y [1,3,3] y las dos obtenidas son finales (es decir, no se les puede aplicar ninguna transformación).

Definir las funciones

   soluciones       :: [Int] -> [Estado]
   finales          :: [Int] -> [[Int]]
   finalesMaximales :: [Int] -> (Int,[[Int]])

soluciones :: [Int] -> [Estado]

finales :: [Int] -> [[Int]]

finalesMaximales :: [Int] -> (Int,[[Int]])

tales que

(soluciones xs) es la lista de pares (n,ys) tales que ys es una lista obtenida aplicándole n transformaciones a xs. Por ejemplo,

     λ> soluciones [1,3,2]
     [(1,[1,3,3]),(1,[1,2,3])]
     λ> sort (nub (soluciones [3,3,2]))
     [(1,[3,3,3]),(2,[2,3,3]),(2,[3,3,3])]
     λ> sort (nub (soluciones [3,2,1]))
     [(2,[2,2,3]),(3,[2,2,3]),(3,[2,3,3]),(3,[3,3,3]),(4,[2,3,3]),(4,[3,3,3])]

λ> soluciones [1,3,2]

[(1,[1,3,3]),(1,[1,2,3])]

λ> sort (nub (soluciones [3,3,2]))

[(1,[3,3,3]),(2,[2,3,3]),(2,[3,3,3])]

λ> sort (nub (soluciones [3,2,1]))

[(2,[2,2,3]),(3,[2,2,3]),(3,[2,3,3]),(3,[3,3,3]),(4,[2,3,3]),(4,[3,3,3])]

(finales xs) son las listas obtenidas transformando xs y a las que no se les puede aplicar más transformaciones. Por ejemplo,

     finales [1,2,3]               ==  [[1,2,3]]
     finales [1,3,2]               ==  [[1,2,3],[1,3,3]]
     finales [3,2,1]               ==  [[2,2,3],[2,3,3],[3,3,3]]
     finales [1,3,2,4]             ==  [[1,2,3,4],[1,3,3,4]]
     finales [1,3,2,3]             ==  [[1,2,3,3],[1,3,3,3]]
     length (finales [9,6,0,7,2])  ==  19
     length (finales [80,60..0])   ==  420

finales [1,2,3] == [[1,2,3]]

finales [1,3,2] == [[1,2,3],[1,3,3]]

finales [3,2,1] == [[2,2,3],[2,3,3],[3,3,3]]

finales [1,3,2,4] == [[1,2,3,4],[1,3,3,4]]

finales [1,3,2,3] == [[1,2,3,3],[1,3,3,3]]

length (finales [9,6,0,7,2]) == 19

length (finales [80,60..0]) == 420

(finalesMaximales xs) es el par (n,yss) tal que la longitud de las cadenas más largas de transformaciones a partir de xs e yss es la lista de los estados finales a partir de xs con n transformaciones. Por ejemplo,

     finalesMaximales [9,5,7]   ==  (2,[[6,8,9],[8,8,9]])
     finalesMaximales [3,2,1]   ==  (4,[[2,3,3],[3,3,3]])
     finalesMaximales [3,2..0]  ==  (10,[[2,3,3,3],[3,3,3,3]])
     finalesMaximales [4,3..0]  ==  (20,[[3,4,4,4,4],[4,4,4,4,4]])

finalesMaximales [9,5,7] == (2,[[6,8,9],[8,8,9]])

finalesMaximales [3,2,1] == (4,[[2,3,3],[3,3,3]])

finalesMaximales [3,2..0] == (10,[[2,3,3,3],[3,3,3,3]])

finalesMaximales [4,3..0] == (20,[[3,4,4,4,4],[4,4,4,4,4]])

Soluciones

import Data.List (nub, sort)
import I1M.BusquedaEnEspaciosDeEstados (buscaEE)

type Estado = (Int,[Int])

inicial :: [Int] -> Estado
inicial xs = (0,xs)

esFinal :: Estado -> Bool
esFinal e = null (sucesores e)

--    λ> sucesores [9,6,0,7,2]
--    [[7,9,0,7,2],[8,9,0,7,2],[9,1,6,7,2],[9,5,6,7,2],[9,6,0,3,7],[9,6,0,6,7]]
sucesores :: Estado -> [Estado]
sucesores (_,[])  = []
sucesores (_,[_]) = []
sucesores (n,x:y:xs) | x > y     = [(n+1,y+1:x:xs), (n+1,x-1:x:xs)] ++ yss
                     | otherwise = yss
    where yss = [(m,x:ys) | (m,ys) <- sucesores (n,y:xs)]
                       

soluciones :: [Int] -> [Estado]
soluciones xs =
    buscaEE sucesores esFinal (inicial xs)

finales :: [Int] -> [[Int]]
finales xs =
    sort (nub (map snd (soluciones xs)))
            
finalesMaximales :: [Int] -> (Int,[[Int]])
finalesMaximales xs =
    (m, [xs | (n,xs) <- es, n == m])
    where es    = sort (nub (soluciones xs))
          (m,_) = maximum es

import Data.List (nub, sort)

import I1M.BusquedaEnEspaciosDeEstados (buscaEE)

type Estado = (Int,[Int])

inicial :: [Int] -> Estado

inicial xs = (0,xs)

esFinal :: Estado -> Bool

esFinal e = null (sucesores e)

-- λ> sucesores [9,6,0,7,2]

-- [[7,9,0,7,2],[8,9,0,7,2],[9,1,6,7,2],[9,5,6,7,2],[9,6,0,3,7],[9,6,0,6,7]]

sucesores :: Estado -> [Estado]

sucesores (_,[]) = []

sucesores (_,[_]) = []

sucesores (n,x:y:xs) | x > y = [(n+1,y+1:x:xs), (n+1,x-1:x:xs)] ++ yss

| otherwise = yss

where yss = [(m,x:ys) | (m,ys) <- sucesores (n,y:xs)]

soluciones :: [Int] -> [Estado]

soluciones xs =

buscaEE sucesores esFinal (inicial xs)

finales :: [Int] -> [[Int]]

finales xs =

sort (nub (map snd (soluciones xs)))

finalesMaximales :: [Int] -> (Int,[[Int]])

finalesMaximales xs =

(m, [xs | (n,xs) <- es, n == m])

where es = sort (nub (soluciones xs))

(m,_) = maximum es

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)

Evaluación de expresiones aritméticas

PorJosé A. Alonso 29-marzo-201626-marzo-2022

Las expresiones aritméticas se pueden definir mediante el siguiente tipo de dato

   data Expr  = N Int | V Char | Sum Expr Expr | Mul Expr Expr 
                deriving Show

1 2	data Expr = N Int \| V Char \| Sum Expr Expr \| Mul Expr Expr deriving Show

Por ejemplo, (x+3)+(7*y) se representa por

   ejExpr :: Expr
   ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))

1 2	ejExpr :: Expr ejExpr = Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))

Definir la función

   valor :: Expr -> Maybe Int

1	valor :: Expr -> Maybe Int

tal que (valor e) es ‘Just v’ si la expresión e es numérica y v es su valor, o bien ‘Nothing’ si e no es numérica. Por ejemplo:

   valor (Sum (N 7) (N 9))                            == Just 16
   valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing
   valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2)))     == Just 18

valor (Sum (N 7) (N 9)) == Just 16

valor (Sum (Sum (V 'x') (N 3))(Mul (N 7) (V 'y'))) == Nothing

valor (Sum (Sum (N 1) (N 3))(Mul (N 7) (N 2))) == Just 18

Soluciones

data Expr  = N Int | V Char | Sum Expr Expr | Mul Expr Expr 
             deriving Show

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

valor1 :: Expr -> Maybe Int
valor1 e | null (aux e) = Nothing
         | otherwise    = Just (head (aux e))
    where aux (N x)       = [x]
          aux (V _)       = []
          aux (Sum e1 e2) = [x+y| x <- aux e1, y <- aux e2]
          aux (Mul e1 e2) = [x*y| x <- aux e1, y <- aux e2]

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

valor2 :: Expr -> Maybe Int
valor2 e | numerico e = Just (aux e)
         | otherwise  = Nothing
    where aux (N x)       = x
          aux (Sum e1 e2) = aux e1 + aux e2
          aux (Mul e1 e2) = aux e1 * aux e2

numerico :: Expr -> Bool
numerico (N _)       = True
numerico (V _)       = False
numerico (Sum e1 e2) = numerico e1 && numerico e2
numerico (Mul e1 e2) = numerico e1 && numerico e2

data Expr = N Int | V Char | Sum Expr Expr | Mul Expr Expr

deriving Show

-- 1ª solución

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

valor1 :: Expr -> Maybe Int

valor1 e | null (aux e) = Nothing

| otherwise = Just (head (aux e))

where aux (N x) = [x]

aux (V _) = []

aux (Sum e1 e2) = [x+y| x <- aux e1, y <- aux e2]

aux (Mul e1 e2) = [x*y| x <- aux e1, y <- aux e2]

-- 2ª solución

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

valor2 :: Expr -> Maybe Int

valor2 e | numerico e = Just (aux e)

| otherwise = Nothing

where aux (N x) = x

aux (Sum e1 e2) = aux e1 + aux e2

aux (Mul e1 e2) = aux e1 * aux e2

numerico :: Expr -> Bool

numerico (N _) = True

numerico (V _) = False

numerico (Sum e1 e2) = numerico e1 && numerico e2

numerico (Mul e1 e2) = numerico e1 && numerico e2

Primo suma de dos cuadrados

PorJosé A. Alonso 14-marzo-20161-abril-2016

Definir la sucesión

   primosSumaDe2Cuadrados :: [Integer]

1	primosSumaDe2Cuadrados :: [Integer]

cuyos elementos son los números primos que se pueden escribir como sumas de dos cuadrados. Por ejemplo,

   λ> take 20 primosSumaDe2Cuadrados
   [2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181]
   λ> primosSumaDe2Cuadrados !! (2*10^5)
   5803241

λ> take 20 primosSumaDe2Cuadrados

[2,5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181]

λ> primosSumaDe2Cuadrados !! (2*10^5)

5803241

En el ejemplo anterior,

13 está en la sucesión porque es primo y 13 = 2²+3².
11 no está en la sucesión porque no se puede escribir como suma de dos cuadrados (en efecto, 11-1=10, 11-2²=7 y 11-3²=2 no son cuadrados).
20 no está en la sucesión porque, aunque es suma de dos cuadrados (20=4²+2²), no es primo.

Soluciones

import Data.Numbers.Primes (primes)

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

primosSumaDe2Cuadrados1 :: [Integer]
primosSumaDe2Cuadrados1 =
    [n | n <- primes,
         esSumaDe2Cuadrados n]

esSumaDe2Cuadrados :: Integer -> Bool
esSumaDe2Cuadrados n = not (null (sumas2cuadrados n))

sumas2cuadrados :: Integer -> [(Integer,Integer)]
sumas2cuadrados n = 
    [(x,y) | x <- [1..ceiling (sqrt (fromIntegral n))],
             let z = n - x^2,
             esCuadrado z, 
             let y = raiz z,
             x <= y]
             
-- (esCuadrado x) se verifica si x es un número al cuadrado. Por
-- ejemplo,
--    esCuadrado 25  ==  True
--    esCuadrado 26  ==  False
esCuadrado :: Integer -> Bool
esCuadrado x = x == y * y
    where y = raiz x

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,
--    raiz 25  ==  5
--    raiz 24  ==  4
--    raiz 26  ==  5
raiz :: Integer -> Integer
raiz x = floor (sqrt (fromIntegral x))

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

primosSumaDe2Cuadrados2 :: [Integer]
primosSumaDe2Cuadrados2 =
    2 : [n | n <- primes,
             n `mod` 4 == 1]

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

--    λ> primosSumaDe2Cuadrados1 !! (2*10^3)
--    38153
--    (3.03 secs, 568,239,744 bytes)
--    λ> primosSumaDe2Cuadrados2 !! (2*10^3)
--    38153
--    (0.05 secs, 20,017,912 bytes)

import Data.Numbers.Primes (primes)

-- 1ª solución

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

primosSumaDe2Cuadrados1 :: [Integer]

primosSumaDe2Cuadrados1 =

[n | n <- primes,

esSumaDe2Cuadrados n]

esSumaDe2Cuadrados :: Integer -> Bool

esSumaDe2Cuadrados n = not (null (sumas2cuadrados n))

sumas2cuadrados :: Integer -> [(Integer,Integer)]

sumas2cuadrados n =

[(x,y) | x <- [1..ceiling (sqrt (fromIntegral n))],

let z = n - x^2,

esCuadrado z,

let y = raiz z,

x <= y]

-- (esCuadrado x) se verifica si x es un número al cuadrado. Por

-- ejemplo,

-- esCuadrado 25 == True

-- esCuadrado 26 == False

esCuadrado :: Integer -> Bool

esCuadrado x = x == y * y

where y = raiz x

-- (raiz x) es la raíz cuadrada entera de x. Por ejemplo,

-- raiz 25 == 5

-- raiz 24 == 4

-- raiz 26 == 5

raiz :: Integer -> Integer

raiz x = floor (sqrt (fromIntegral x))

-- 2ª solución

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

primosSumaDe2Cuadrados2 :: [Integer]

primosSumaDe2Cuadrados2 =

2 : [n | n <- primes,

n `mod` 4 == 1]

-- Comparación de eficiencia

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

-- λ> primosSumaDe2Cuadrados1 !! (2*10^3)

-- 38153

-- (3.03 secs, 568,239,744 bytes)

-- λ> primosSumaDe2Cuadrados2 !! (2*10^3)

-- 38153

-- (0.05 secs, 20,017,912 bytes)

Referencias

N.J.A. Sloane, Sucesión A002313 de la OEIS.
M. Bates, Primes of the form x² + ny²–
G. Xiao, Two squares.

Sumas de potencias de 3 primos

PorJosé A. Alonso 24-febrero-201625-marzo-2022

Los primeros números de la forma p²+q³+r⁴, con p, q y r primos son

   28 = 2² + 2³ + 2⁴
   33 = 3² + 2³ + 2⁴
   47 = 2² + 3³ + 2⁴
   49 = 5² + 2³ + 2⁴

28 = 2² + 2³ + 2⁴

33 = 3² + 2³ + 2⁴

47 = 2² + 3³ + 2⁴

49 = 5² + 2³ + 2⁴

Definir la sucesión

   sumas3potencias :: [Integer]

1	sumas3potencias :: [Integer]

cuyos elementos son los números que se pueden escribir de la forma p²+q³+r⁴, con p, q y r primos. Por ejemplo,

   λ> take 15 sumas3potencias
   [28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]
   λ> sumas3potencias !! 234567
   8953761

λ> take 15 sumas3potencias

[28,33,47,49,52,68,73,92,93,98,112,114,117,133,138]

λ> sumas3potencias !! 234567

8953761

Soluciones

import Data.Numbers.Primes (primes)

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

sumas3potencias1 :: [Integer]
sumas3potencias1 = filter esTripleSuma [1..]
 
-- (esTripleSuma n) se verifica si n se puede escribir de la forma
-- p²+q³+r⁴, con p, q y r primos. Por ejemplo, 
--    esTripleSuma 33  ==  True
--    esTripleSuma 45  ==  False
esTripleSuma :: Integer -> Bool
esTripleSuma = not . null . triplesSumas  

-- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales
-- que p²+q³+r⁴ = n. Por ejemplo,
--    triplesSumas 33   ==  [(3,2,2)]
--    triplesSumas 145  ==  [(11,2,2),(2,5,2)]
--    triplesSumas 45   ==  []
triplesSumas :: Integer -> [(Integer,Integer,Integer)]
triplesSumas n =  
    [(p,q,r) 
    | r <- xs, 
      q <- xs, 
      let p2 = n - q^3 - r^4,
      let p = (floor . sqrt . fromIntegral) p2,
      p*p == p2,
      isPrime p]
    where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes

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

sumas3potencias2 :: [Integer]
sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs)

sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer]
sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
    where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]
mezcla (x:xs) (y:ys) | x < y  = x : mezcla xs (y:ys)
                     | x == y = x : mezcla xs ys
                     | x > y  = y : mezcla (x:xs) ys
 
as = map (^2) primes
bs = map (^3) primes
cs = map (^4) primes

import Data.Numbers.Primes (primes)

-- 1ª solución

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

sumas3potencias1 :: [Integer]

sumas3potencias1 = filter esTripleSuma [1..]

-- (esTripleSuma n) se verifica si n se puede escribir de la forma

-- p²+q³+r⁴, con p, q y r primos. Por ejemplo,

-- esTripleSuma 33 == True

-- esTripleSuma 45 == False

esTripleSuma :: Integer -> Bool

esTripleSuma = not . null . triplesSumas

-- (triplesSumas n) es la lista de las ternas de primos (p,q,r) tales

-- que p²+q³+r⁴ = n. Por ejemplo,

-- triplesSumas 33 == [(3,2,2)]

-- triplesSumas 145 == [(11,2,2),(2,5,2)]

-- triplesSumas 45 == []

triplesSumas :: Integer -> [(Integer,Integer,Integer)]

triplesSumas n =

[(p,q,r)

| r <- xs,

q <- xs,

let p2 = n - q^3 - r^4,

let p = (floor . sqrt . fromIntegral) p2,

p*p == p2,

isPrime p]

where xs = takeWhile (< (ceiling $ sqrt $ fromIntegral n)) primes

-- 2ª solución

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

sumas3potencias2 :: [Integer]

sumas3potencias2 = sumaOrdenadaInf as (sumaOrdenadaInf bs cs)

sumaOrdenadaInf:: [Integer] -> [Integer] -> [Integer]

sumaOrdenadaInf xs ys = mezclaTodas [map (+x) ys | x <- xs]

mezclaTodas :: Ord a => [[a]] -> [a]

mezclaTodas = foldr1 xmezcla

where xmezcla (x:xs) ys = x : mezcla xs ys

mezcla :: Ord a => [a] -> [a] -> [a]

mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys)

| x == y = x : mezcla xs ys

| x > y = y : mezcla (x:xs) ys

as = map (^2) primes

bs = map (^3) primes

cs = map (^4) primes

Sucesiones de listas de números

Soluciones

Números como sumas de primos consecutivos

Soluciones

Evaluación de expresiones aritméticas

Soluciones

Primo suma de dos cuadrados

Soluciones

Referencias

Sumas de potencias de 3 primos

Soluciones

Entradas recientes

Buscar

Correo electrónico