La conjetura de Grimm establece que a cada elemento de un conjunto de números compuestos se puede asignar número primo que lo divide, de forma que cada uno de los números primos elegidos es distinto de todos los demás. Más formalmente, si n+1, n+2, ..., n+k son números compuestos, entonces existen números primos p(i), distintos entre sí, tales que p(i) divide a n+i para 1 ≤ i ≤ k.

Diremos que la lista ps = [p(1),...,p(k)] es una sucesión de Grim para la lista xs = [x(1),...,x(k)] si p(i) son números primos distintos y p(i) divide a x(i), para 1 ≤ i ≤ k. Por ejemplo, 2, 5, 13, 3, 7 es una sucesión de Grim de 24, 25, 26, 27, 28.

Definir las funciones

compuestos :: Integer -> [Integer]
sucesionesDeGrim :: [Integer] -> [[Integer]]

tales que

• (compuestos n) es la mayor lista de números enteros consecutivos empezando en n. Por ejemplo,

compuestos 24  ==  [24,25,26,27,28]
compuestos  8  ==  [8,9,10]
compuestos 15  ==  [15,16]
compuestos 16  ==  [16]
compuestos 17  ==  []

• (sucesionesDeGrim xs) es la lista de las sucesiones de Grim de xs. Por ejemplo,

sucesionesDeGrim [15,16]          == [[3,2],[5,2]]
sucesionesDeGrim [8,9,10]         == [[2,3,5]]
sucesionesDeGrim [9,10]           == [[3,2],[3,5]]
sucesionesDeGrim [24,25,26,27,28] == [[2,5,13,3,7]]
sucesionesDeGrim [25,26,27,28]    == [[5,2,3,7],[5,13,3,2],[5,13,3,7]]

Comprobar con QuickCheck la conjetura de Grim; es decir, para todo número n > 1, (sucesionesDeGrim (compuestos n)) es una lista no vacía.

Leer más…

La sucesión de Fibonacci, F(n), es la siguiente sucesión infinita de números naturales:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

La sucesión comieanza con los números 0 y 1. A partir de estos, cada término es la suma de los dos anteriores.

El teorema de Carmichael establece que para todo n mayor que 12, el n-ésimo número de Fibonacci F(n) tiene al menos un factor primo que no es factor de ninguno de los términos anteriores de la sucesión.

Si un número primo p es un factor de F(n) y no es factor de ningún F(m) con m < n, entonces se dice que p es un factor característico o un divisor primitivo de F(n).

Definir la función

factoresCaracteristicos :: Int -> [Integer]

tal que (factoresCaracteristicos n) es la lista de los factores característicos de F(n). Por ejemplo,

factoresCaracteristicos  4  ==  [3]
factoresCaracteristicos  6  ==  []
factoresCaracteristicos 19  ==  [37,113]
factoresCaracteristicos 37  ==  [73,149,2221]

Comprobar con QuickCheck el teorema de Carmichael; es decir, para todo número entero (factoresCaracteristicos (13 + abs n)) es una lista no vacía.

Leer más…

La derivada aritmética es una función definida sobre los números naturales por analogía con la regla del producto para el cálculo de las derivadas usada en análisis.

Para un número natural n su derivada D(n) se define por

D(0)  = 0
D(1)  = 0
D(p)  = 1, si p es primo
D(ab) = D(a)b + aD(b) (regla de Leibniz para derivar productos)

Por ejemplo,

D(6)  = D(2*3) = D(2)*3 + 2*D(3) = 1*3 + 2*1 =  5
D(12) = D(2*6) = D(2)*6 + 2*D(6) = 1*6 + 2*5 = 16

Definir la función

derivada :: Integer -> Integer

tal que (derivada n) es la derivada aritmérica de n. Por ejemplo,

derivada  6  ==  5
derivada 12  ==  16
maximum [derivada n | n <- [1..60000]]  ==  380928

Comprobar con QuickCheck que si x es un número entero positivo y su descomposición en factores primos es

x = p(1)^e(1) + p(2)^e(2) +...+ p(n)^e(n)

entonces la derivada de x es

x * [e(1)/p(1) + e(2)/p(2) +...+ e(n)/p(n)]

Nota: No usar en la definición la propiedad que hay que comprobar.

Leer más…

El postulado de Bertrand afirma que para cualquier número entero n > 1, existe al menos un número primo p con n < p < 2n.

Definir la función

siguientePrimo :: Integer -> Integer

tal que (siguientePrimo n) es el menor primo mayor que n. Por ejemplo,

siguientePrimo 8   ==  11
siguientePrimo 11  ==  13

Comprobar con QuickCheck el postulado de Bertrand; es decir, para todo entero n > 1, se verifica que n < p < 2n, donde p es (siguientePrimo n).

Leer más…

En un ejercicio anterior se mostró que los conjuntos finitos de números naturales se pueden enumerar como sigue

 0: []
 1: [0]
 2: [1]
 3: [1,0]
 4: [2]
 5: [2,0]
 6: [2,1]
 7: [2,1,0]
 8: [3]
 9: [3,0]
10: [3,1]
11: [3,1,0]
12: [3,2]
13: [3,2,0]
14: [3,2,1]
15: [3,2,1,0]
16: [4]
17: [4,0]
18: [4,1]
19: [4,1,0]

en la que los elementos están ordenados de manera decreciente.

Además, se definió la constante

enumeracionCFN :: [[Integer]]

tal que sus elementos son los conjuntos de los números naturales con la ordenación descrita anteriormente. Por ejemplo,

λ> take 20 enumeracionCFN
[[],
 [0],
 [1],[1,0],
 [2],[2,0],[2,1],[2,1,0],
 [3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],
 [4],[4,0],[4,1],[4,1,0]]

Definir la función

posicion :: [Integer] -> Integer

tal que (posicion xs) es la posición del conjunto finito de números naturales xs, representado por una lista decreciente, en enumeracionCFN. Por ejemplo,

posicion [2,0]          ==  5
posicion [2,1]          ==  6
posicion [2,1,0]        ==  7
posicion [0]            ==  1
posicion [1,0]          ==  3
posicion [2,1,0]        ==  7
posicion [3,2,1,0]      ==  15
posicion [4,3,2,1,0]    ==  31
posicion [5,4,3,2,1,0]  ==  63

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

posicion [n,n-1..0] == 2^(n+1) - 1.

Leer más…

Dado un conjunto de números naturales, por ejemplo A = {0, 2, 3, 4}, calculamos las sumas de todos los pares de elementos de A. Como A tiene 4 elementos hay 16 pares, pero no todas sus sumas son distintas. En este caso solo hay 8 sumas distintas: {0, 2, 3, 4, 5, 6, 7, 8}. Procediendo análogamente hay 9 diferencias distinatas entre los pares de A: {-4, -3, -2, -1, 0, 1, 2, 3, 4}.

Experimentando con más conjuntos, se puede conjeturar que el número de restas es mayor que el de sumas y argumentar que que mientras que con dos números distintos sólo se produce una suma distints sin embargo se producen dos restas distintas. Por ejemplo, con 5 y 7 sólo se produce una suma (ya que 5+7 y 7+5 ambos dan 12) pero dos restas (ya que 5-7 y 7-5 dan -2 y 2, respectivamente).

Sin embargo, la conjetura es falsa. Un contraejemplo en el conjunto {0, 2, 3, 4, 7, 11, 12, 14}, que tiene 26 sumas distintas con sus pares de elementos pero sólo 25 restas.

Los conjuntos con más sumas distintas con sus pares de elementos que restas se llaman conjuntos MSQR (por "más sumas que restas").

El objetivo de este ejercicio es calcular los conjuntos MSQR.

Definir las funciones

tieneMSQR :: [Integer] -> Bool
conjuntosMSQR :: [[Integer]]

tales que

• (tieneMSQR xs) se verifica si el conjunto xs tiene más sumas que restas. Por ejemplo,

tieneMSQR [0, 2, 3, 4]                 ==  False
tieneMSQR [0, 2, 3, 4, 7, 11, 12, 14]  ==  True

• conjuntosMSQR es la lista de los conjuntos MSQR. Por ejemplo,

λ> take 5 conjuntosMSQR
[[14,12,11,7,4,3,2,0],
 [14,12,11,10,7,3,2,0],
 [14,13,12,9,5,4,2,1,0],
 [14,13,12,10,9,5,2,1,0],
 [15,13,12,8,5,4,3,1]]

 length (takeWhile (< [14]) conjuntosMSQR)   ==  0
 length (takeWhile (< [15]) conjuntosMSQR)   ==  4
 length (takeWhile (< [16]) conjuntosMSQR)   ==  10
 length (takeWhile (< [17]) conjuntosMSQR)   ==  30

Leer más…

Los conjuntos finitos de números naturales se pueden enumerar como sigue

 0: []
 1: [0]
 2: [1]
 3: [1,0]
 4: [2]
 5: [2,0]
 6: [2,1]
 7: [2,1,0]
 8: [3]
 9: [3,0]
10: [3,1]
11: [3,1,0]
12: [3,2]
13: [3,2,0]
14: [3,2,1]
15: [3,2,1,0]
16: [4]
17: [4,0]
18: [4,1]
19: [4,1,0]

en la que los elementos están ordenados de manera decreciente.

Definir la constante

enumeracionCFN :: [[Integer]]

tal que sus elementos son los conjuntos de los números naturales con la ordenación descrita anteriormente. Por ejemplo,

λ> take 20 enumeracionCFN
[[],
 [0],
 [1],[1,0],
 [2],[2,0],[2,1],[2,1,0],
 [3],[3,0],[3,1],[3,1,0],[3,2],[3,2,0],[3,2,1],[3,2,1,0],
 [4],[4,0],[4,1],[4,1,0]]

Comprobar con QuickCheck que

• si (xs,ys) es un par de elementos consecutivos de enumeracionCFN, entonces xs < ys;
• todo conjunto finito de números naturales, representado por una lista decreciente, está en enumeracionCFN.

Leer más…

Un par de números primos (p,q) es un par de números primos gemelos si su distancia de 2; es decir, si q = p+2. Por ejemplo, (17,19) es una par de números primos gemelos.

La conjetura de los primos gemelos postula la existencia de infinitos pares de primos gemelos.

Definir la constante

primosGemelos :: [(Integer,Integer)]

tal que sus elementos son los pares de primos gemelos. Por ejemplo,

λ> take 7 primosGemelos
[(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61)]
λ> primosGemelos !! (4*10^4)
(6381911,6381913)

Comprobar con QuickCheck la conjetura de los primos gemelos.

Leer más…

La sucesión de Fibonacci, F(n), es la siguiente sucesión infinita de números naturales:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ...

La sucesión comienza con los números 0 y 1. A partir de estos, cada término es la suma de los dos anteriores.

Definir la función

sumaFibsIndiceImpar :: Int -> Integer

tal que (sumaFibsIndiceImpar n) es la suma de los n primeros términos de la sucesión de Fibonacci no índice impar; es decir,

sumaFibsIndiceImpar n = F(1) + F(3) + ... + F(2*n-1)

Por ejemplo,

sumaFibsIndiceImpar 1  ==  1
sumaFibsIndiceImpar 2  ==  3
sumaFibsIndiceImpar 3  ==  8
sumaFibsIndiceImpar 4  ==  21
sumaFibsIndiceImpar 5  ==  55
sumaFibsIndiceImpar (10^4) `rem` (10^9)  ==  213093125

En los ejemplos anteriores se observa que

sumaFibsIndiceImpar 1  ==  F(2)
sumaFibsIndiceImpar 2  ==  F(4)
sumaFibsIndiceImpar 3  ==  F(6)
sumaFibsIndiceImpar 4  ==  F(8)
sumaFibsIndiceImpar 5  ==  F(10)

Comprobar con QuickCheck que (sumaFibsIndiceImpar n) es F(2n); es decir, el 2n-ésimo número de Fibonacci

Leer más…

El 25 de diciembre de 1640, en una carta a Mersenne, Fermat demostró la conjetura de Girard: todo primo de la forma 4n+1 puede expresarse de manera única como suma de dos cuadrados. Por eso es conocido como el Teorema de Navidad de Fermat.

Definir las funciones

representaciones :: Integer -> [(Integer,Integer)]
primosImparesConRepresentacionUnica :: [Integer]
primos4nM1 :: [Integer]

tales que

• (representaciones n) es la lista de pares de números naturales (x,y) tales que n = x^2 + y^2 con x <= y. Por ejemplo,

representaciones  20           ==  [(2,4)]
representaciones  25           ==  [(0,5),(3,4)]
representaciones 325           ==  [(1,18),(6,17),(10,15)]
representaciones 100000147984  ==  [(0,316228)]
length (representaciones (10^10))    ==  6
length (representaciones (4*10^12))  ==  7

• primosImparesConRepresentacionUnica es la lista de los números primos impares que se pueden escribir exactamente de una manera como suma de cuadrados de pares de números naturales (x,y) con x <= y. Por ejemplo,

λ> take 20 primosImparesConRepresentacionUnica
[5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

• primos4nM1 es la lista de los números primos que se pueden escribir como uno más un múltiplo de 4 (es decir, que son congruentes con 1 módulo 4). Por ejemplo,

λ> take 20 primos4nM1
[5,13,17,29,37,41,53,61,73,89,97,101,109,113,137,149,157,173,181,193]

El teorema de Navidad de Fermat afirma que un número primo impar p se puede escribir exactamente de una manera como suma de dos cuadrados de números naturales p = x² + y^2 (con x <= y) si, y sólo si, p se puede escribir como uno más un múltiplo de 4 (es decir, que es congruente con 1 módulo 4).

Comprobar con QuickCheck el teorema de Navidad de Fermat; es decir, que para todo número n, los n-ésimos elementos de primosImparesConRepresentacionUnica y de primos4nM1 son iguales.

Leer más…