Definir las funciones

multiplosDeLaLongitud :: [Int] -> [Int]
multiplosDeLaLongitudDeConsecutivos :: Int -> Int -> [Int]

tales que

• (multiplosDeLaLongitud xs) es la lista de los elementos de xs que son múltiplos de la longitud de xs. Por ejemplo,

multiplosDeLaLongitud [2,4,6,8] == [4,8]

• (multiplosDeLaLongitudDeConsecutivos n m) es la lista de elementos de [n..n+m-1] que son múltiplos de n. Por ejemplo,

multiplosDeLaLongitudDeConsecutivos 9 2  ==  [10]
multiplosDeLaLongitudDeConsecutivos 9 12 ==  [12]

Comprobar con QuickCheck si se verifican las siguientes propiedades

• En cualquier conjunto de m elementos consecutivos, m divide exactamente a uno de dichos elementos. En otras palabras, si n y m son enteros positivos, entonces (multiplosDeLaLongitudDeConsecutivos n m) tiene exactamente un elemento.
• Si n es un entero positivo y m >= n, entonces (multiplosDeLaLongitudDeConsecutivos n m) es igual a [m]
• Si n y n son enteros positivos y m < n, entonces (multiplosDeLaLongitudDeConsecutivos n m) es igual a [m * ceiling (n' / m')] donde n' y m' son las formas decimales de n y m respectivamente.

Leer más…

La conjetura de Catalan, enunciada en 1844 por Eugène Charles Catalan y demostrada 2002 por Preda Mihăilescu1, afirma que

Las únicas dos potencias de números enteros consecutivos son 8 y 9 (que son respectivamente 2³ y 3²).

En otras palabras, la única solución entera de la ecuación

x^a - y^b = 1

para x, a, y, b > 1 es x = 3, a = 2, y = 2, b = 3.

La conjetura de Pillai, propuesta por S.S. Pillai en 1942, generaliza este resultado y es un problema abierto. Afirma que cada entero se puede escribir sólo un número finito de veces como una diferencia de dos potencias perfectas. En otras palabras, para todo entero positivo n, el conjunto de soluciones de

x^a - y^b = n

para x, a, y, b > 1 es finito.

Por ejemplo, para n = 4, hay 3 soluciones

(2,3, 2,2) ya que 2³ -  2² =   8 -   4 = 4
(6,2, 2,5) ya que 6² -  2⁵ =  36 -  32 = 4
(5,3,11,2) ya que 5³ - 11² = 125 - 121 = 4

Las soluciones se pueden representar por la menor potencia (en el caso anterior, por 4, 32 y 121) ya que dado n (en el caso anterior es 4), la potencia mayor es la menor más n.

Definir las funciones

potenciasPerfectas :: [Integer]
solucionesPillati :: Integer -> [Integer]
solucionesPillatiAcotadas :: Integer -> Integer -> [Integer]

tales que

• potenciasPerfectas es la lista de las potencias perfectas (es decir, de los números de la forma x^a con x y a mayores que 1). Por ejemplo,

take 10 potenciasPerfectas  ==  [4,8,9,16,25,27,32,36,49,64]
potenciasPerfectas !! 200   ==  28224

• (solucionesPillati n) es la lista de las menores potencias de las soluciones de la ecuación de Pillati x^a - y^b = n; es decir, es la lista de los u tales que u y u+n son potencias perfectas. Por ejemplo,

take 3 (solucionesPillati 4)  ==  [4,32,121]
take 2 (solucionesPillati 5)  ==  [4,27]
take 4 (solucionesPillati 7)  ==  [9,25,121,32761]

• (solucionesPillatiAcotadas c n) es la lista de elementos de (solucionesPillati n) menores que n. Por ejemplo,

solucionesPillatiAcotadas (10^3) 1  ==  [8]
solucionesPillatiAcotadas (10^3) 2  ==  [25]
solucionesPillatiAcotadas (10^3) 3  ==  [125]
solucionesPillatiAcotadas (10^3) 4  ==  [4,32,121]
solucionesPillatiAcotadas (10^3) 5  ==  [4,27]
solucionesPillatiAcotadas (10^3) 6  ==  []
solucionesPillatiAcotadas (10^3) 7  ==  [9,25,121]
solucionesPillatiAcotadas (10^5) 7  ==  [9,25,121,32761]

Leer más…

La 40ª Conferencia General de la UNESCO ha proclamado el de enero el Día mundial de la Lógica. La fecha del 14 de enero se ha eligido para rendir homenaje a dos grandes lógicos del siglo XX: Kurt Gödel (que falleció el 14 de enero de 1978) y Alfred Tarski (que nació el 14 de enero de 1901).

Gödel demostró en 1931 los teoremas de incompletitud y para su demostración introdujo la actualmente conocida como codificación de Gödel que asigna a cada fórmula de un lenguaje formal un número único.

En este ejercicio aplicaremos la codificación de Gödel a las listas de números enteros.

Dada una lista de números naturales xs, la codificación de Gödel de xs se obtiene multiplicando las potencias de los primos sucesivos, siendo los exponentes los sucesores de los elementos de xs. Por ejemplo, si xs es [6,0,4], la codificación de xs es

2^(6+1) * 3^(0+1) * 5^(4+1) = 1200000

Definir las funciones

codificaG   :: [Integer] -> Integer
decodificaG :: Integer -> [Integer]

tales que

• (codificaG xs) es la codificación de Gödel de xs. Por ejemplo,

codificaG [6,0,4]            ==  1200000
codificaG [3,1,1]            ==  3600
codificaG [3,1,0,0,0,0,0,1]  ==  4423058640
codificaG [1..6]             ==  126111168580452537982500

• (decodificaG n) es la lista xs cuya codificación es n. Por ejemplo,

decodificaG 1200000                   ==  [6,0,4]
decodificaG 3600                      ==  [3,1,1]
decodificaG 4423058640                ==  [3,1,0,0,0,0,0,1]
decodificaG 126111168580452537982500  ==  [1,2,3,4,5,6]

Comprobar con QuickCheck que decodificaG es la inversa por la izquierda de codificaG; es decir, para toda lista xs de números enteros, se verifica que

decodificaG (codificaG ys) == ys

donde ys es la lista de los valores absolutos de los elementos de xs.

Leer más…

Un número de Munchausen es un número entero positivo tal que es igual a la suma de sus dígitos elevados a sí mismo. Por ejemplo, 3435 es un número de Munchausen ya que

3³ + 4⁴ + 3³ + 5⁵ = 27 + 256 + 27 + 3125 = 3435

Definir la función

esMunchausen :: Integer -> Bool

tal que (esMunchausen n) se verifica si n es un número de Munchausen. Por ejemplo,

esMunchausen 3435  ==  True
esMunchausen 2020  ==  False

Comprobar con QuickCheck que que los únicos números de Munchausen son 1 y 3435.

Nota 1: No usar la propiedad en la definición.

Nota 2: El ejercicio está basado en el artículo ¿Por qué 3435 es uno de mis números favoritos? de Miguel Ángel Morales en El Aleph.

Leer más…

El teorema de existencia de divisores afirma que

En cualquier subconjunto de {1, 2, ..., 2m} con al menos m+1 elementos existen números distintos a, b tales que a divide a b.

Un conjunto de números naturales xs es mayoritario si existe un m tal que la lista de xs es un subconjunto de {1,2,...,2m} con al menos m+1 elementos. Por ejemplo, {2,3,5,6} porque es un subconjunto de {1,2,...,6} con más de 3 elementos.

Definir las funciones

divisoresMultiplos :: [Integer] -> [(Integer,Integer)]
esMayoritario :: [Integer] -> Bool

tales que

• (divisores xs) es la lista de pares de elementos distintos de (a,b) tales que a divide a b. Por ejemplo,

divisoresMultiplos [2,3,5,6]  ==  [(2,6),(3,6)]
divisoresMultiplos [2,3,5]    ==  []
divisoresMultiplos [4..8]     ==  [(4,8)]

• (esMayoritario xs) se verifica xs es mayoritario. Por ejemplo,

esMayoritario [2,3,5,6]  ==  True
esMayoritario [2,3,5]    ==  False

Comprobar con QuickCheck el teorema de existencia de divisores; es decir, en cualquier conjunto mayoritario existen números distintos a, b tales que a divide a b. Para la comprobación se puede usar el siguiente generador de conjuntos mayoritarios

mayoritario :: Gen [Integer]
mayoritario = do
  m' <- arbitrary
  let m = 1 + abs m'
  xs' <- sublistOf [1..2*m] `suchThat` (\ys -> genericLength ys > m)
  return xs'

con lo que la propiedad que hay que comprobar con QuickCheck es

teorema_de_existencia_de_divisores :: Property
teorema_de_existencia_de_divisores =
  forAll mayoritario (not . null . divisoresMultiplos)

Leer más…

El problema de Waring, propuesto por Edward Waring consiste en determinar si, para cada número entero k mayor que 1, existe un número n tal que todo entero positivo se puede escribir como una suma de k-potencias de números positivos con n sumandos como máximo.

La respuesta afirmativa al problema, aportada por David Hilbert, se conoce como el teorema de Hilbert-Waring. Su enunciado es

Para cada número entero k, con k ≥ 2, existe un entero positivo g(k) tal que todo entero positivo se puede expresar como una suma de a lo más g(k) k-ésimas potencias.

Definir las funciones

descomposiciones :: Integer -> Integer -> Integer -> [[Integer]]
orden :: Integer -> Integer -> Integer

tales que

• (descomposiciones x k n) es la lista de descomposiciones de x como suma de n potencias con exponente k de números enteros positivos.

descomposiciones 9   2 1  ==  [[9]]
descomposiciones 9   3 1  ==  []
descomposiciones 9   3 2  ==  [[1,8]]
descomposiciones 9   4 9  ==  [[1,1,1,1,1,1,1,1,1]]
descomposiciones 25  2 2  ==  [[9,16]]
descomposiciones 133 2 3  ==  [[8,125]]
descomposiciones 38  3 2  ==  [[1,1,36],[4,9,25]]

• (orden x k) es el menor número de sumandos necesario para expresar x como suma de k-ésimas potencias. Por ejemplo,

orden 9  2  ==  1
orden 9  3  ==  2
orden 9  4  ==  9
orden 10 2  ==  2
orden 10 3  ==  3
orden 10 4  ==  10
[maximum [orden x k | x <- [1..1000]] | k <- [1..6]] == [1,4,9,19,37,73]

Comprobar el teorema de Hilbert-Waring para k hasta 7; es decir, para todo número x positivo se verifica que

orden x 2 <= 4
orden x 3 <= 9
orden x 4 <= 19
orden x 5 <= 37
orden x 6 <= 73
orden x 7 <= 143

y, en general,

orden x k <= 2^k + floor ((3/2)^k) - 2

Leer más…

Dos números enteros son coprimos (o primos entre sí) si no tienen ningún factor primo en común. Por ejemplo, 4 y 15 son coprimos.

Una terna coprima es una terna (a,b,c) tal que

• a y b son coprimos,
• a y c son coprimos y
• b y c son coprimos.

Por ejemplo, (3,4,5) es una terna coprima.

Definir la función

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

tal que (sumas3coprimos n) es la lista de las ternas coprimas cuya suma es n. Por ejemplo,

sumas3coprimos 10  ==  [(2,3,5)]
sumas3coprimos 11  ==  []
sumas3coprimos 12  ==  [(2,3,7),(3,4,5)]
length (sumas3coprimos 4000)  ==  546146

Comprobar con QuickCheck que todo número entero mayor que 15 se puede escribir como suma de alguna terna coprima; es decir, para todo entero n, (sumas3coprimos2 (18 + abs n)) tiene algún elemento.

Leer más…

Para cada número entero positivo n, se define el conjunto

S(n) = {1, 2, 3, ..., n}

de los números desde el 1 hasta n.

Definir la función

mayorPotenciaDeDosEnS :: Integer -> Integer

tal que (mayorPotenciaDeDosEnS n) es la mayor potencia de 2 en S(n). Por ejemplo,

mayorPotenciaDeDosEnS 3  ==  2
mayorPotenciaDeDosEnS 4  ==  4

Comprobar con QuickCheck que la mayor potencia de 2 en S(n) no divide a ningún otro elemento de S(n).

Leer más…

Sea S el conjunto

S = {1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, ...}

de los enteros positivos congruentes con 1 módulo 4; es decir,

S = {4n+1 | n ∈ N}

Un elemento n de S es irreducible si sólo es divisible por dos elementos de S: 1 y n. Por ejemplo, 9 es irreducible; pero 45 no lo es (ya que es el proctos de 5 y 9 que son elementos de S).

Definir las funciones

esIrreducible :: Integer -> Bool
factorizaciones :: Integer -> [[Integer]]
conFactorizacionNoUnica :: [Integer]

tales que

• (esIrreducible n) se verifica si n es irreducible. Por ejemplo,

esIrreducible 9   ==  True
esIrreducible 45  ==  False

• (factorizaciones n) es la lista de conjuntos de elementos irreducibles de S cuyo producto es n. Por ejemplo,

factorizaciones 9     ==  [[9]]
factorizaciones 693   ==  [[9,77],[21,33]]
factorizaciones 4389  ==  [[21,209],[33,133],[57,77]]

• conFactorizacionNoUnica es la lista de elementos de S cuya factorización no es única. Por ejemplo,

λ> take 10 conFactorizacionNoUnica
[441,693,1089,1197,1449,1617,1881,1953,2205,2277]

Leer más…

Una lista CuCu es una lista de números enteros positivos tales que la suma de sus Cubos es igual al Cuadrado de su suma. Por ejemplo, [1, 2, 3, 2, 4, 6] es una lista CuCu ya que

1³ + 2³ + 3³ + 2³ + 4³ + 6³ = (1 + 2 + 3 + 2 + 4 + 6)²

La lista de Liouville correspondiente al número entero positivo n es la lista formada por el número de divisores de cada divisor de n. Por ejemplo, para el número 20 se tiene que sus divisores son

1, 2, 4, 5, 10, 20

puesto que el número de sus divisores es

• El 1 tiene 1 divisor (el 1 solamente).
• El 2 tiene 2 divisores (el 1 y el 2).
• El 4 tiene 3 divisores (el 1, el 2 y el 4).
• El 5 tiene 2 divisores (el 1 y el 5).
• El 10 tiene 4 divisores (el 1, el 2, el 5 y el 10).
• El 20 tiene 6 divisores (el 1, el 2, el 4, el 5, el 10 y el 20).

la lista de Liouville de 20 es [1, 2, 3, 2, 4, 6] que, como se comentó anteriormente, es una lista CuCu.

El teorema de Lioville afirma que todas las lista de Lioville son CuCu.

Definir las funciones

esCuCu :: [Integer] -> Bool
liouville :: Integer -> [Integer]

tales que

• (esCuCu xs) se verifica si la lista xs es CuCu; es decir, la suma de los cubos de sus elementos es igual al cuadrado de su suma. Por ejemplo,

esCuCu [1,2,3]        ==  True
esCuCu [1,2,3,2]      ==  False
esCuCu [1,2,3,2,4,6]  ==  True

• (liouville n) es la lista de Lioville correspondiente al número n. Por ejemplo,

liouville 20  ==  [1,2,3,2,4,6]
liouville 60  ==  [1,2,2,3,2,4,4,6,4,6,8,12]
length (liouville (product [1..25]))  ==  340032

Comprobar con QuickCheck

• que para todo entero positivo n, (liouville (2^n)) es la lista [1,2,3,...,n+1] y
• el teorema de Lioville; es decir, para todo entero positivo n, (liouville n) es una lista CuCu.

Nota: Este ejercicio está basado en Cómo generar conjuntos CuCu de Gaussianos.

Leer más…