Ejercicio

Productos de sumas de progresiones aritméticas

PorJosé A. Alonso 10-junio-202126-enero-2022

El enunciado de un problema para la IMO (Olimpiada Internacional de Matemáticas) de 1978 es

Para cada número entero d ≥ 1, sea M(d) el conjunto de todos enteros positivos que no se pueden escribir como una suma de una progresión aritmética de diferencia d, teniendo al menos dos sumandos y formadas por enteros positivos. Sean A = M(1), B = M(2)-{2} y C = M(3). Demostrar que todo c ∈ C se puede escribir de una única manera como c = ab con a ∈ A, b ∈ B.

Definir las funciones

   conjuntoA   :: [Integer]
   conjuntoB   :: [Integer]
   conjuntoC   :: [Integer]
   productosAB :: Integer -> [(Integer,Integer)]

conjuntoA :: [Integer]

conjuntoB :: [Integer]

conjuntoC :: [Integer]

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

tales que

conjuntoA es la lista de los elementos del conjunto A; es decir, de los números que no se pueden escribir como sumas de progresiones aritméticas de diferencia uno, con al menos dos términos, de números enteros positivos. Por ejemplo,

     conjuntoA !! 2                      ==  4
     length (show (conjuntoA !! (10^7))) == 3010300

1 2	conjuntoA !! 2 == 4 length (show (conjuntoA !! (10^7))) == 3010300

conjuntoB es la lista de los elementos del conjunto B; es decir, los números (distintos de dos) que no se pueden escribir como sumas de progresiones aritméticas de diferencia dos, con al menos dos términos, de números enteros positivos. Por ejemplo,

     conjuntoB !! 3       ==  5
     conjuntoB !! (10^6)  ==  15485863

1 2	conjuntoB !! 3 == 5 conjuntoB !! (10^6) == 15485863

conjuntoC es la lista de los elementos del conjunto C; es decir, los números que no se pueden escribir como sumas de progresiones aritméticas de diferencia tres, con al menos dos términos, de números enteros positivos. Por ejemplo,

     conjuntoC !! 4  ==  6

1	conjuntoC !! 4 == 6

(productosAB x) es la lista de los pares (a,b) tales que a es un elementos del conjunto A, b es un elemento del conjunto B y su producto es x. Por ejemplo,

     productosAB 10  ==  [(2,5)]
     productosAB 15  ==  []

1 2	productosAB 10 == [(2,5)] productosAB 15 == []

Comprobar con QuickCheck la propiedad del problema de la Olimpiada; es decir, para todo c ∈ C la lista (productosAB c) tiene exactamente un elemento.

Soluciones

import Data.List (foldr1)
import Data.Numbers.Primes (primes,primeFactors)
import Test.QuickCheck

-- Nota: Se usarán las funciones definidas en los ejercicios
-- anteriores.

conjuntoA :: [Integer]
conjuntoA = [2^k | k <- [0..]]

conjuntoB :: [Integer]
conjuntoB = 1 : tail primes

conjuntoC :: [Integer]
conjuntoC = noSonSumasDePADeDiferencia 3

noSonSumasDePADeDiferencia :: Integer -> [Integer]
noSonSumasDePADeDiferencia d =
  diferencia [1..] (sonSumasDePADeDiferencia d)

sonSumasDePADeDiferencia :: Integer -> [Integer]
sonSumasDePADeDiferencia d =
  mezclaTodas [sumasDePADeDiferencia d a | a <- [1..]]

sumasDePADeDiferencia :: Integer -> Integer -> [Integer]
sumasDePADeDiferencia d a =
  tail (scanl1 (+) [a,a+d..])

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

diferencia :: [Integer] -> [Integer] -> [Integer]
diferencia (x:xs) (y:ys)
  | x == y    = diferencia xs ys
  | otherwise = x : diferencia xs (y:ys)

productosAB :: Integer -> [(Integer,Integer)]
productosAB c =
  [(a,b) | a <- takeWhile (<= c) conjuntoA,
           c `mod` a == 0,
           let b = c `div` a,
           b `pertenece` conjuntoB]

pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (< x) ys)

-- La propiedad es
prop_productosAB :: Int -> Property
prop_productosAB k =
  k >= 0 ==>
  length (productosAB (conjuntoC !! k)) == 1

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

import Data.List (foldr1)

import Data.Numbers.Primes (primes,primeFactors)

import Test.QuickCheck

-- Nota: Se usarán las funciones definidas en los ejercicios

-- anteriores.

conjuntoA :: [Integer]

conjuntoA = [2^k | k <- [0..]]

conjuntoB :: [Integer]

conjuntoB = 1 : tail primes

conjuntoC :: [Integer]

conjuntoC = noSonSumasDePADeDiferencia 3

noSonSumasDePADeDiferencia :: Integer -> [Integer]

noSonSumasDePADeDiferencia d =

diferencia [1..] (sonSumasDePADeDiferencia d)

sonSumasDePADeDiferencia :: Integer -> [Integer]

sonSumasDePADeDiferencia d =

mezclaTodas [sumasDePADeDiferencia d a | a <- [1..]]

sumasDePADeDiferencia :: Integer -> Integer -> [Integer]

sumasDePADeDiferencia d a =

tail (scanl1 (+) [a,a+d..])

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

diferencia :: [Integer] -> [Integer] -> [Integer]

diferencia (x:xs) (y:ys)

| x == y = diferencia xs ys

| otherwise = x : diferencia xs (y:ys)

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

productosAB c =

[(a,b) | a <- takeWhile (<= c) conjuntoA,

c `mod` a == 0,

let b = c `div` a,

b `pertenece` conjuntoB]

pertenece :: Integer -> [Integer] -> Bool

pertenece x ys =

x == head (dropWhile (< x) ys)

-- La propiedad es

prop_productosAB :: Int -> Property

prop_productosAB k =

k >= 0 ==>

length (productosAB (conjuntoC !! k)) == 1

-- La comprobación es

-- λ> quickCheck prop_productosAB

-- +++ OK, passed 100 tests.

Nuevas soluciones

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

Números que no son sumas de progresiones aritméticas de diferencia dada

PorJosé A. Alonso 8-junio-202126-enero-2022

El número 5 es la suma de números enteros positivos en progresión aritmética de diferencia tres (ya que es 1+4) y también lo es el 7 (ya que es 2+5) y el 12 (ya que es (1+4+7), pero el 6 no lo es.

Definir la función

   noSonSumasDePADeDiferencia :: Integer -> [Integer]

1	noSonSumasDePADeDiferencia :: Integer -> [Integer]

tal que (noSonSumasDePADeDiferencia d) es la lista de los números no se pueden escribir como sumas de progresiones aritméticas de diferencia d, con al menos términos, de números enteros positivos. Por ejemplo,

   (noSonSumasDePADeDiferencia 3) !! 4    ==  6
   (noSonSumasDePADeDiferencia 3) !! 100  ==  6848
   (noSonSumasDePADeDiferencia 9) !! 200  ==  6752

(noSonSumasDePADeDiferencia 3) !! 4 == 6

(noSonSumasDePADeDiferencia 3) !! 100 == 6848

(noSonSumasDePADeDiferencia 9) !! 200 == 6752

Soluciones

import Data.List (foldr1)

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

noSonSumasDePADeDiferencia :: Integer -> [Integer]
noSonSumasDePADeDiferencia d =
  diferencia [1..] (sonSumasDePADeDiferencia d)

-- (sonSumasDePADeDiferencia d) es la lista de los números que se pueden
-- escribir como sumas de progresiones aritméticas de diferencia d,
-- con al menos dos términos, de números enteros positivos. Por ejemplo,
--    λ> take 15 (sonSumasDePADeDiferencia 3)
--    [5,7,9,11,12,13,15,17,18,19,21,22,23,24,25]
sonSumasDePADeDiferencia :: Integer -> [Integer]
sonSumasDePADeDiferencia d =
  mezclaTodas [sumasDePADeDiferencia d a | a <- [1..]]

-- (sumasDePADeDiferencia a) es la lista de las sumas de la
-- progresión aritmética de término inicial a y diferencia . Por
-- ejemplo,
--    take 7 (sumasDePADeDiferencia 3 1)  ==  [5,12,22,35,51,70,92]
--    take 7 (sumasDePADeDiferencia 3 2)  ==  [7,15,26,40,57,77,100]
--    take 7 (sumasDePADeDiferencia 3 3)  ==  [9,18,30,45,63,84,108]
sumasDePADeDiferencia :: Integer -> Integer -> [Integer]
sumasDePADeDiferencia d a =
  tail (scanl1 (+) [a,a+d..])

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
-- sus elementos son listas infinitas ordenadas. Por ejemplo,
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
--    [2,3,4,5,6,7,8,9,10,11]
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
--    [2,4,6,8,9,10,12,14,16,18]
mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys

-- (mezcla xs ys) es la lista obtenida mezclando las  lista infinitas
-- ordenadas crecientes xs e ys. Por ejemplo,
--    λ> take 20 (mezcla [1,3..] [2,5..])
--    [1,2,3,5,7,8,9,11,13,14,15,17,19,20,21,23,25,26,27,29]
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

-- (diferencia xs ys) es la diferencia las listas infinitas ordenadas
-- crecientes xs e ys. Por ejemplo,
--    λ> take 8 (diferencia [1..] [2,4..])
--    [1,3,5,7,9,11,13,15]
diferencia :: [Integer] -> [Integer] -> [Integer]
diferencia (x:xs) (y:ys)
  | x == y    = diferencia xs ys
  | otherwise = x : diferencia xs (y:ys)

import Data.List (foldr1)

-- 1ª solución

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

noSonSumasDePADeDiferencia :: Integer -> [Integer]

noSonSumasDePADeDiferencia d =

diferencia [1..] (sonSumasDePADeDiferencia d)

-- (sonSumasDePADeDiferencia d) es la lista de los números que se pueden

-- escribir como sumas de progresiones aritméticas de diferencia d,

-- con al menos dos términos, de números enteros positivos. Por ejemplo,

-- λ> take 15 (sonSumasDePADeDiferencia 3)

-- [5,7,9,11,12,13,15,17,18,19,21,22,23,24,25]

sonSumasDePADeDiferencia :: Integer -> [Integer]

sonSumasDePADeDiferencia d =

mezclaTodas [sumasDePADeDiferencia d a | a <- [1..]]

-- (sumasDePADeDiferencia a) es la lista de las sumas de la

-- progresión aritmética de término inicial a y diferencia . Por

-- ejemplo,

-- take 7 (sumasDePADeDiferencia 3 1) == [5,12,22,35,51,70,92]

-- take 7 (sumasDePADeDiferencia 3 2) == [7,15,26,40,57,77,100]

-- take 7 (sumasDePADeDiferencia 3 3) == [9,18,30,45,63,84,108]

sumasDePADeDiferencia :: Integer -> Integer -> [Integer]

sumasDePADeDiferencia d a =

tail (scanl1 (+) [a,a+d..])

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como

-- sus elementos son listas infinitas ordenadas. Por ejemplo,

-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])

-- [2,3,4,5,6,7,8,9,10,11]

-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])

-- [2,4,6,8,9,10,12,14,16,18]

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

mezclaTodas = foldr1 xmezcla

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

-- (mezcla xs ys) es la lista obtenida mezclando las lista infinitas

-- ordenadas crecientes xs e ys. Por ejemplo,

-- λ> take 20 (mezcla [1,3..] [2,5..])

-- [1,2,3,5,7,8,9,11,13,14,15,17,19,20,21,23,25,26,27,29]

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

-- (diferencia xs ys) es la diferencia las listas infinitas ordenadas

-- crecientes xs e ys. Por ejemplo,

-- λ> take 8 (diferencia [1..] [2,4..])

-- [1,3,5,7,9,11,13,15]

diferencia :: [Integer] -> [Integer] -> [Integer]

diferencia (x:xs) (y:ys)

| x == y = diferencia xs ys

| otherwise = x : diferencia xs (y:ys)

Nuevas soluciones

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

Números que no son sumas de progresiones aritméticas de diferencia dos

PorJosé A. Alonso 4-junio-202126-enero-2022

El número 4 es la suma de números enteros positivos en progresión aritmética de diferencia dos (ya que es 1+3) y también lo es el 6 (ya que es 2+4) y el 9 (ya que es (1+3+5), pero el 5 no lo es.

Definir la función

   noSonSumasDePADeDiferenciaDos :: [Integer]

1	noSonSumasDePADeDiferenciaDos :: [Integer]

cuyos elementos son los números que no se pueden escribir como sumas de progresiones aritméticas de diferencia dos, con al menos dos términos, de números enteros positivos. Por ejemplo,

   noSonSumasDePADeDiferenciaDos !! 3  ==  5
   noSonSumasDePADeDiferenciaDos !! (10^6)  ==  15485863

1 2	noSonSumasDePADeDiferenciaDos !! 3 == 5 noSonSumasDePADeDiferenciaDos !! (10^6) == 15485863

Soluciones

import Data.List (foldr1)
import Data.Numbers.Primes (primes)

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

noSonSumasDePADeDiferenciaDos :: [Integer]
noSonSumasDePADeDiferenciaDos =
  diferencia [1..] sonSumasDePADeDiferenciaDos

-- sonSumasDePADeDiferenciaDos es la lista de los números que se pueden
-- escribir como sumas de progresiones aritméticas de diferencia dos,
-- con al menos dos términos, de números enteros positivos. Por ejemplo,
--    λ> take 10 sonSumasDePADeDiferenciaDos
--    [4,6,8,9,10,12,14,15,16,18]
sonSumasDePADeDiferenciaDos :: [Integer]
sonSumasDePADeDiferenciaDos =
  mezclaTodas [sumasDePADeDiferenciaDos a | a <- [1..]]

-- (sumasDePADeDiferenciaDos a) es la lista de las sumas de la
-- progresión aritmética de término inicial a y diferencia dos. Por
-- ejemplo,
--    take 7 (sumasDePADeDiferenciaDos 1)  ==  [4,9,16,25,36,49,64]
--    take 7 (sumasDePADeDiferenciaDos 2)  ==  [6,12,20,30,42,56,72]
--    take 7 (sumasDePADeDiferenciaDos 3)  ==  [8,15,24,35,48,63,80]
sumasDePADeDiferenciaDos :: Integer -> [Integer]
sumasDePADeDiferenciaDos a =
  tail (scanl1 (+) [a,a+2..])

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
-- sus elementos son listas infinitas ordenadas. Por ejemplo,
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
--    [2,3,4,5,6,7,8,9,10,11]
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
--    [2,4,6,8,9,10,12,14,16,18]
mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys

-- (mezcla xs ys) es la lista obtenida mezclando las dos lista infinitas
-- ordenadas crecientes xs e ys. Por ejemplo,
--    λ> take 20 (mezcla [1,3..] [2,5..])
--    [1,2,3,5,7,8,9,11,13,14,15,17,19,20,21,23,25,26,27,29]
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

-- (diferencia xs ys) es la diferencia las listas infinitas ordenadas
-- crecientes xs e ys. Por ejemplo,
--    λ> take 8 (diferencia [1..] [2,4..])
--    [1,3,5,7,9,11,13,15]
diferencia :: [Integer] -> [Integer] -> [Integer]
diferencia (x:xs) (y:ys)
  | x == y    = diferencia xs ys
  | otherwise = x : diferencia xs (y:ys)

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

-- Observando el siguiente cálculo
--    λ> take 15 noSonSumasDePADeDiferenciaDos
--    [1,2,3,5,7,11,13,17,19,23,29,31,37,41,43]
noSonSumasDePADeDiferenciaDos2 :: [Integer]
noSonSumasDePADeDiferenciaDos2 = 1 : primes

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

-- La comparación es
--    λ> noSonSumasDePADeDiferenciaDos !! 1000
--    7919
--    (3.58 secs, 3,304,841,840 bytes)
--    λ> noSonSumasDePADeDiferenciaDos2 !! 1000
--    7919
--    (0.01 secs, 2,316,896 bytes)

import Data.List (foldr1)

import Data.Numbers.Primes (primes)

-- 1ª solución

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

noSonSumasDePADeDiferenciaDos :: [Integer]

noSonSumasDePADeDiferenciaDos =

diferencia [1..] sonSumasDePADeDiferenciaDos

-- sonSumasDePADeDiferenciaDos es la lista de los números que se pueden

-- escribir como sumas de progresiones aritméticas de diferencia dos,

-- con al menos dos términos, de números enteros positivos. Por ejemplo,

-- λ> take 10 sonSumasDePADeDiferenciaDos

-- [4,6,8,9,10,12,14,15,16,18]

sonSumasDePADeDiferenciaDos :: [Integer]

sonSumasDePADeDiferenciaDos =

mezclaTodas [sumasDePADeDiferenciaDos a | a <- [1..]]

-- (sumasDePADeDiferenciaDos a) es la lista de las sumas de la

-- progresión aritmética de término inicial a y diferencia dos. Por

-- ejemplo,

-- take 7 (sumasDePADeDiferenciaDos 1) == [4,9,16,25,36,49,64]

-- take 7 (sumasDePADeDiferenciaDos 2) == [6,12,20,30,42,56,72]

-- take 7 (sumasDePADeDiferenciaDos 3) == [8,15,24,35,48,63,80]

sumasDePADeDiferenciaDos :: Integer -> [Integer]

sumasDePADeDiferenciaDos a =

tail (scanl1 (+) [a,a+2..])

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como

-- sus elementos son listas infinitas ordenadas. Por ejemplo,

-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])

-- [2,3,4,5,6,7,8,9,10,11]

-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])

-- [2,4,6,8,9,10,12,14,16,18]

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

mezclaTodas = foldr1 xmezcla

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

-- (mezcla xs ys) es la lista obtenida mezclando las dos lista infinitas

-- ordenadas crecientes xs e ys. Por ejemplo,

-- λ> take 20 (mezcla [1,3..] [2,5..])

-- [1,2,3,5,7,8,9,11,13,14,15,17,19,20,21,23,25,26,27,29]

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

-- (diferencia xs ys) es la diferencia las listas infinitas ordenadas

-- crecientes xs e ys. Por ejemplo,

-- λ> take 8 (diferencia [1..] [2,4..])

-- [1,3,5,7,9,11,13,15]

diferencia :: [Integer] -> [Integer] -> [Integer]

diferencia (x:xs) (y:ys)

| x == y = diferencia xs ys

| otherwise = x : diferencia xs (y:ys)

-- 2ª solución

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

-- Observando el siguiente cálculo

-- λ> take 15 noSonSumasDePADeDiferenciaDos

-- [1,2,3,5,7,11,13,17,19,23,29,31,37,41,43]

noSonSumasDePADeDiferenciaDos2 :: [Integer]

noSonSumasDePADeDiferenciaDos2 = 1 : primes

-- Comparación de eficiencia

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

-- La comparación es

-- λ> noSonSumasDePADeDiferenciaDos !! 1000

-- 7919

-- (3.58 secs, 3,304,841,840 bytes)

-- λ> noSonSumasDePADeDiferenciaDos2 !! 1000

-- 7919

-- (0.01 secs, 2,316,896 bytes)

Nuevas soluciones

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

Números que no son sumas de progresiones aritméticas de diferencia uno

PorJosé A. Alonso 3-junio-202126-enero-2022

El número 3 es la suma de números enteros positivos en progresión aritmética de diferencia uno (ya que es 1+2) y también lo es el 5 (ya que es 2+3) y el 6 (ya que es (1+2+3), pero el 4 no lo es.

Definir la función

   noSonSumasDePADeDiferenciaUno :: [Integer]

1	noSonSumasDePADeDiferenciaUno :: [Integer]

cuyos elementos son los números que no se pueden escribir como de progresiones aritméticas de diferencia uno, con al menos dos términos, de números enteros positivos. Por ejemplo,

   noSonSumasDePADeDiferenciaUno !! 2  ==  4
   length (show (noSonSumasDePADeDiferenciaUno !! (10^7))) == 3010300

1 2	noSonSumasDePADeDiferenciaUno !! 2 == 4 length (show (noSonSumasDePADeDiferenciaUno !! (10^7))) == 3010300

Soluciones

import Data.List (foldr1)

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

noSonSumasDePADeDiferenciaUno :: [Integer]
noSonSumasDePADeDiferenciaUno =
  diferencia [1..] sonSumasDePADeDiferenciaUno

-- sonSumasDePADeDiferenciaUno es la lista de los números que se pueden
-- escribir como sumas de progresiones aritméticas de diferencia uno,
-- con al menos dos términos, de números enteros positivos. Por ejemplo,
--    λ> take 10 sonSumasDePADeDiferenciaUno
--    [3,5,6,7,9,10,11,12,13,14]
sonSumasDePADeDiferenciaUno :: [Integer]
sonSumasDePADeDiferenciaUno =
  mezclaTodas [sumasDePADeDiferenciaUno a | a <- [1..]]

-- (sumasDePADeDiferenciaUno a) es la lista de las sumas de la
-- progresión aritmética de término inicial a y diferencia uno. Por
-- ejemplo,
--    take 7 (sumasDePADeDiferenciaUno 1)  ==  [3,6,10,15,21,28,36]
--    take 7 (sumasDePADeDiferenciaUno 2)  ==  [5,9,14,20,27,35,44]
--    take 7 (sumasDePADeDiferenciaUno 3)  ==  [7,12,18,25,33,42,52]
sumasDePADeDiferenciaUno :: Integer -> [Integer]
sumasDePADeDiferenciaUno a =
  tail (scanl1 (+) [a,a+1..])

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como
-- sus elementos son listas infinitas ordenadas. Por ejemplo,
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])
--    [2,3,4,5,6,7,8,9,10,11]
--    λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])
--    [2,4,6,8,9,10,12,14,16,18]
mezclaTodas :: Ord a => [[a]] -> [a]
mezclaTodas = foldr1 xmezcla
  where xmezcla (x:xs) ys = x : mezcla xs ys

-- (mezcla xs ys) es la lista obtenida mezclando las dos lista infinitas
-- ordenadas crecientes xs e ys. Por ejemplo,
--    λ> take 20 (mezcla [1,3..] [2,5..])
--    [1,2,3,5,7,8,9,11,13,14,15,17,19,20,21,23,25,26,27,29]
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

-- (diferencia xs ys) es la diferencia las listas infinitas ordenadas
-- crecientes xs e ys. Por ejemplo,
--    λ> take 8 (diferencia [1..] [2,4..])
--    [1,3,5,7,9,11,13,15]
diferencia :: [Integer] -> [Integer] -> [Integer]
diferencia (x:xs) (y:ys)
  | x == y    = diferencia xs ys
  | otherwise = x : diferencia xs (y:ys)

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

-- Observando el siguiente cálculo
--    λ> take 10 noSonSumasDePADeDiferenciaUno
--    [1,2,4,8,16,32,64,128,256,512]
noSonSumasDePADeDiferenciaUno2 :: [Integer]
noSonSumasDePADeDiferenciaUno2 = [2^k | k <- [0..]]

-- 3ª solución
-- ===========

noSonSumasDePADeDiferenciaUno3 :: [Integer]
noSonSumasDePADeDiferenciaUno3 =
  iterate (*2) 1

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

-- La comparación es
--    λ> noSonSumasDePADeDiferenciaUno !! 14
--    16384
--    (36.00 secs, 28,609,441,984 bytes)
--    λ> noSonSumasDePADeDiferenciaUno2 !! 14
--    16384
--    (0.01 secs, 102,712 bytes)
--    λ> noSonSumasDePADeDiferenciaUno3 !! 14
--    16384
--    (0.00 secs, 102,432 bytes)
--
--    λ> length (show (noSonSumasDePADeDiferenciaUno3 !! (3*10^5)))
--    90309
--    (2.78 secs, 5,770,583,328 bytes)
--    λ> length (show (noSonSumasDePADeDiferenciaUno2 !! (3*10^5)))
--    90309
--    (0.09 secs, 60,840,304 bytes)
--
--    λ> length (show (noSonSumasDePADeDiferenciaUno2 !! (10^7)))
--    3010300
--    (3.55 secs, 2,030,646,392 bytes)

import Data.List (foldr1)

-- 1ª solución

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

noSonSumasDePADeDiferenciaUno :: [Integer]

noSonSumasDePADeDiferenciaUno =

diferencia [1..] sonSumasDePADeDiferenciaUno

-- sonSumasDePADeDiferenciaUno es la lista de los números que se pueden

-- escribir como sumas de progresiones aritméticas de diferencia uno,

-- con al menos dos términos, de números enteros positivos. Por ejemplo,

-- λ> take 10 sonSumasDePADeDiferenciaUno

-- [3,5,6,7,9,10,11,12,13,14]

sonSumasDePADeDiferenciaUno :: [Integer]

sonSumasDePADeDiferenciaUno =

mezclaTodas [sumasDePADeDiferenciaUno a | a <- [1..]]

-- (sumasDePADeDiferenciaUno a) es la lista de las sumas de la

-- progresión aritmética de término inicial a y diferencia uno. Por

-- ejemplo,

-- take 7 (sumasDePADeDiferenciaUno 1) == [3,6,10,15,21,28,36]

-- take 7 (sumasDePADeDiferenciaUno 2) == [5,9,14,20,27,35,44]

-- take 7 (sumasDePADeDiferenciaUno 3) == [7,12,18,25,33,42,52]

sumasDePADeDiferenciaUno :: Integer -> [Integer]

sumasDePADeDiferenciaUno a =

tail (scanl1 (+) [a,a+1..])

-- (mezclaTodas xss) es la mezcla ordenada de xss, donde tanto xss como

-- sus elementos son listas infinitas ordenadas. Por ejemplo,

-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2..]])

-- [2,3,4,5,6,7,8,9,10,11]

-- λ> take 10 (mezclaTodas [[n,2*n..] | n <- [2,9..]])

-- [2,4,6,8,9,10,12,14,16,18]

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

mezclaTodas = foldr1 xmezcla

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

-- (mezcla xs ys) es la lista obtenida mezclando las dos lista infinitas

-- ordenadas crecientes xs e ys. Por ejemplo,

-- λ> take 20 (mezcla [1,3..] [2,5..])

-- [1,2,3,5,7,8,9,11,13,14,15,17,19,20,21,23,25,26,27,29]

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

-- (diferencia xs ys) es la diferencia las listas infinitas ordenadas

-- crecientes xs e ys. Por ejemplo,

-- λ> take 8 (diferencia [1..] [2,4..])

-- [1,3,5,7,9,11,13,15]

diferencia :: [Integer] -> [Integer] -> [Integer]

diferencia (x:xs) (y:ys)

| x == y = diferencia xs ys

| otherwise = x : diferencia xs (y:ys)

-- 2ª solución

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

-- Observando el siguiente cálculo

-- λ> take 10 noSonSumasDePADeDiferenciaUno

-- [1,2,4,8,16,32,64,128,256,512]

noSonSumasDePADeDiferenciaUno2 :: [Integer]

noSonSumasDePADeDiferenciaUno2 = [2^k | k <- [0..]]

-- 3ª solución

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

noSonSumasDePADeDiferenciaUno3 :: [Integer]

noSonSumasDePADeDiferenciaUno3 =

iterate (*2) 1

-- Comparación de eficiencia

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

-- La comparación es

-- λ> noSonSumasDePADeDiferenciaUno !! 14

-- 16384

-- (36.00 secs, 28,609,441,984 bytes)

-- λ> noSonSumasDePADeDiferenciaUno2 !! 14

-- 16384

-- (0.01 secs, 102,712 bytes)

-- λ> noSonSumasDePADeDiferenciaUno3 !! 14

-- 16384

-- (0.00 secs, 102,432 bytes)

-- λ> length (show (noSonSumasDePADeDiferenciaUno3 !! (3*10^5)))

-- 90309

-- (2.78 secs, 5,770,583,328 bytes)

-- λ> length (show (noSonSumasDePADeDiferenciaUno2 !! (3*10^5)))

-- 90309

-- (0.09 secs, 60,840,304 bytes)

-- λ> length (show (noSonSumasDePADeDiferenciaUno2 !! (10^7)))

-- 3010300

-- (3.55 secs, 2,030,646,392 bytes)

Nuevas soluciones

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

Productos de elementos de dos conjuntos

PorJosé A. Alonso 2-junio-202126-enero-2022

Definir la función

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

1	productos :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)]

tal que (productos as bs c) es la lista de pares (a,b) tales que a un elementos de as, b es un elemento de bs y su producto es x, donde as y bs son listas (posiblemente infinitas) ordenadas crecientes. Por ejemplo,

   productos [3,5..] [2,4..] 2000  ==  [(5,400),(25,80),(125,16)]
   productos [3,5..] [2,4..] 2001  ==  []
   length (productos [3,5..] [2,4..] (product [1..11]))  ==  59

productos [3,5..] [2,4..] 2000 == [(5,400),(25,80),(125,16)]

productos [3,5..] [2,4..] 2001 == []

length (productos [3,5..] [2,4..] (product [1..11])) == 59

Soluciones

import Data.List (group, inits, nub, sort, subsequences)
import Data.Numbers.Primes (primeFactors)

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

productos :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)]
productos as bs c =
  [(a,b) | a <- takeWhile (<= c) as,
           c `mod` a == 0,
           let b = c `div` a,
           b `pertenece` bs]

-- (pertenece x ys) se verifica si x pertenece a la lista ordenada
-- creciente ys. Por ejemplo,
--    pertenece 15 [1,3..]  ==  True
--    pertenece 16 [1,3..]  ==  False
pertenece :: Integer -> [Integer] -> Bool
pertenece x ys =
  x == head (dropWhile (< x) ys)

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

productos2 :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)]
productos2 as bs c =
  [(a,b) | a <- as',
           let b = c `div` a,
           b `pertenece` bs']
  where cs  = divisores c
        as' = interseccion cs (takeWhile (<=c) as)
        bs' = interseccion cs (takeWhile (<=c) bs)

-- (divisores x) es el conjunto de divisores de los x. Por ejemplo,
--   divisores 30  ==  [1,2,3,5,6,10,15,30]
divisores :: Integer -> [Integer]
divisores = sort
          . map (product . concat)
          . sequence
          . map inits
          . group
          . primeFactors

-- (interseccion xs ys) es la intersección entre las listas ordenadas
-- crecientes xs e ys. Por ejemplo,
--    λ> take 10 (interseccion [1,3..] [2,5..])
--    [5,11,17,23,29,35,41,47,53,59]
interseccion :: Ord a => [a] -> [a] -> [a]
interseccion = aux
  where aux as@(x:xs) bs@(y:ys) = case compare x y of
                                    LT ->     aux xs bs
                                    EQ -> x : aux xs ys
                                    GT ->     aux as ys
        aux _         _         = []

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

productos3 :: [Integer] -> [Integer] -> Integer -> [(Integer,Integer)]
productos3 as bs c = aux as' bs'
  where aux (x:xs) (y:ys) | x * y == c = (x,y) : aux xs ys
                          | x * y >  c = aux (x:xs) ys
                          | otherwise  = aux xs (y:ys)
        aux _ _           = []
        cs  = divisores c
        as' = interseccion cs (takeWhile (<=c) as)
        bs' = reverse (interseccion cs (takeWhile (<=c) bs))

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

-- La compactación es
--    λ> length (productos [3,5..] [2,4..] (product [1..11]))
--    59
--    (9.83 secs, 5,588,474,408 bytes)
--    λ> length (productos2 [3,5..] [2,4..] (product [1..11]))
--    59
--    (10.48 secs, 8,942,746,480 bytes)
--    λ> length (productos3 [3,5..] [2,4..] (product [1..11]))
--    59
--    (17.39 secs, 13,413,570,800 bytes)

import Data.List (group, inits, nub, sort, subsequences)

import Data.Numbers.Primes (primeFactors)

-- 1ª solución

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

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

productos as bs c =

[(a,b) | a <- takeWhile (<= c) as,

c `mod` a == 0,

let b = c `div` a,

b `pertenece` bs]

-- (pertenece x ys) se verifica si x pertenece a la lista ordenada

-- creciente ys. Por ejemplo,

-- pertenece 15 [1,3..] == True

-- pertenece 16 [1,3..] == False

pertenece :: Integer -> [Integer] -> Bool

pertenece x ys =

x == head (dropWhile (< x) ys)

-- 2ª solución

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

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

productos2 as bs c =

[(a,b) | a <- as',

let b = c `div` a,

b `pertenece` bs']

where cs = divisores c

as' = interseccion cs (takeWhile (<=c) as)

bs' = interseccion cs (takeWhile (<=c) bs)

-- (divisores x) es el conjunto de divisores de los x. Por ejemplo,

-- divisores 30 == [1,2,3,5,6,10,15,30]

divisores :: Integer -> [Integer]

divisores = sort

. map (product . concat)

. sequence

. map inits

. group

. primeFactors

-- (interseccion xs ys) es la intersección entre las listas ordenadas

-- crecientes xs e ys. Por ejemplo,

-- λ> take 10 (interseccion [1,3..] [2,5..])

-- [5,11,17,23,29,35,41,47,53,59]

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

interseccion = aux

where aux as@(x:xs) bs@(y:ys) = case compare x y of

LT -> aux xs bs

EQ -> x : aux xs ys

GT -> aux as ys

aux _ _ = []

-- 2ª solución

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

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

productos3 as bs c = aux as' bs'

where aux (x:xs) (y:ys) | x * y == c = (x,y) : aux xs ys

| x * y > c = aux (x:xs) ys

| otherwise = aux xs (y:ys)

aux _ _ = []

cs = divisores c

as' = interseccion cs (takeWhile (<=c) as)

bs' = reverse (interseccion cs (takeWhile (<=c) bs))

-- Comparación de eficiencia

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

-- La compactación es

-- λ> length (productos [3,5..] [2,4..] (product [1..11]))

-- 59

-- (9.83 secs, 5,588,474,408 bytes)

-- λ> length (productos2 [3,5..] [2,4..] (product [1..11]))

-- 59

-- (10.48 secs, 8,942,746,480 bytes)

-- λ> length (productos3 [3,5..] [2,4..] (product [1..11]))

-- 59

-- (17.39 secs, 13,413,570,800 bytes)

Nuevas soluciones

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

Productos de sumas de progresiones aritméticas

Soluciones

Nuevas soluciones

Números que no son sumas de progresiones aritméticas de diferencia dada

Soluciones

Nuevas soluciones

Números que no son sumas de progresiones aritméticas de diferencia dos

Soluciones

Nuevas soluciones

Números que no son sumas de progresiones aritméticas de diferencia uno

Soluciones

Nuevas soluciones

Productos de elementos de dos conjuntos

Soluciones

Nuevas soluciones

Entradas recientes

Buscar

Correo electrónico