junio 2021 – Página 2

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>

Potencias con mismos finales

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

El enunciado del primer problema de la IMO (Olimpiada Internacional de Matemáticas) de 1978 es

Sean n > m ≥ 1 números naturales tales que los 3 últimos dígitos de 1978^m y 1978^n coinciden. Calcular el par (m,n) de dichos pares para el que m+n es mínimo.

Definir la función

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

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

tal que (potenciasMismoFinales x) es la lista de los pares de naturales (m,n) tales que n > m ≥ 1 y los 3 últimos dígitos de x^m y x^n coinciden (además, la lista está ordenada por la suma de las componentes de sus elementos). Por ejemplo,

   take 3 (potenciasMismoFinales 1001) == [(1,2),(1,3),(1,4)]
   take 3 (potenciasMismoFinales 1002) == [(3,103),(4,104),(5,105)]
   take 3 (potenciasMismoFinales 1003) == [(1,101),(2,102),(3,103)]
   take 3 (potenciasMismoFinales 1004) == [(2,52),(3,53),(4,54)]
   take 3 (potenciasMismoFinales 1005) == [(3,5),(3,7),(4,6)]
   take 3 (potenciasMismoFinales 1006) == [(3,28),(4,29),(5,30)]
   take 3 (potenciasMismoFinales 1007) == [(1,21),(2,22),(3,23)]
   take 3 (potenciasMismoFinales 1008) == [(1,101),(2,102),(3,103)]
   take 3 (potenciasMismoFinales 1009) == [(1,51),(2,52),(3,53)]

take 3 (potenciasMismoFinales 1001) == [(1,2),(1,3),(1,4)]

take 3 (potenciasMismoFinales 1002) == [(3,103),(4,104),(5,105)]

take 3 (potenciasMismoFinales 1003) == [(1,101),(2,102),(3,103)]

take 3 (potenciasMismoFinales 1004) == [(2,52),(3,53),(4,54)]

take 3 (potenciasMismoFinales 1005) == [(3,5),(3,7),(4,6)]

take 3 (potenciasMismoFinales 1006) == [(3,28),(4,29),(5,30)]

take 3 (potenciasMismoFinales 1007) == [(1,21),(2,22),(3,23)]

take 3 (potenciasMismoFinales 1008) == [(1,101),(2,102),(3,103)]

take 3 (potenciasMismoFinales 1009) == [(1,51),(2,52),(3,53)]

Usando la función potenciasMismoFinales, calcular la respuesta al problema de la Olimpiada.

Soluciones

potenciasMismoFinales :: Integer -> [(Integer,Integer)]
potenciasMismoFinales x =
   [(m,n) | (m,n) <- pares,
            x^m `mod` 1000 == x^n `mod` 1000]

-- pares el lista de pares de enteros positivos, con el primero menor que
-- el segundo, ordenados por su suma y primer elemento. Por ejemplo,
--    λ> take 10 pares
--    [(1,2),(1,3),(1,4),(2,3),(1,5),(2,4),(1,6),(2,5),(3,4),(1,7)]
pares :: [(Integer,Integer)]
pares = [(m,n) | x <- [1..],
                 m <- [1..x],
                 let n = x-m,
                 n > m]

-- Cálculo de la respuesta
-- =======================

-- El cálculo es
--    λ> head (potenciasMismoFinales 1978)
--    (3,103)

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

potenciasMismoFinales x =

[(m,n) | (m,n) <- pares,

x^m `mod` 1000 == x^n `mod` 1000]

-- pares el lista de pares de enteros positivos, con el primero menor que

-- el segundo, ordenados por su suma y primer elemento. Por ejemplo,

-- λ> take 10 pares

-- [(1,2),(1,3),(1,4),(2,3),(1,5),(2,4),(1,6),(2,5),(3,4),(1,7)]

pares :: [(Integer,Integer)]

pares = [(m,n) | x <- [1..],

m <- [1..x],

let n = x-m,

n > m]

-- Cálculo de la respuesta

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

-- El cálculo es

-- λ> head (potenciasMismoFinales 1978)

-- (3,103)

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>

Meses: junio 2021

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

Potencias con mismos finales

Soluciones

Nuevas soluciones

Entradas recientes

Buscar

Correo electrónico