I1M2012: Números sin coprimos no primos
En la primera parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell del problema propuesto la Olimpiada Internacional de Matemáticas (IMO) de 1978 cuyo enunciado es
Calcular todos los números naturales n < 1978 con la siguiente propiedad: Si m es un número natural, 1 < m < n, y m y n son coprimos (es decir, el máximo común divisor de m y n es 1), entonces m es un número primo.
La representación matemática del enunciado es
{n∈ℕ | n<1978, ∀m∈ℕ (1 < m < n ∧ mcd(n,m) = 1 ⟶ m es primo}
y su traducción a Haskell es
|
1 2 3 |
solP2 :: [Integer] solP2 = [n | n <- [1..1977], and [primo m | m <- [2..n-1], gcd n m == 1]] |
donde (primo m) se verifica si m es primo
|
1 2 |
primo :: Integer -> Bool primo n = factores n == [1,n] |
y (factores n) es la lista de los números que dividen a n
|
1 2 |
factores :: Integer -> [Integer] factores n = [m | m <- [1..n], n `rem` m == 0] |
La solución del problema se calcula con
|
1 2 |
ghci> solP2 [1,2,3,4,6,8,12,18,24,30] |
Se puede generalizar solP2 a una función solP2′ tal que (solP2′ x) es el conjunto de los números naturales n < x tales que si m es un número natural, 1 < m < n, y m y n son coprimos, entonces m es un número primo.
|
1 2 3 |
solP2' :: Integer -> [Integer] solP2' x = [n | n <- [1..x], and [primo m | m <- [2..n-1], gcd n m == 1]] |
Por ejemplo,
|
1 2 3 4 |
ghci> solP2' 2012 [1,2,3,4,6,8,12,18,24,30] ghci> solP2' 3000 [1,2,3,4,6,8,12,18,24,30] |
A la vista de los cálculos anteriores se conjetura que el conjunto de los números naturales n tales que si m es un número natural, 1 < m < n, y m y n son coprimos, entonces m es un número primo es [1,2,3,4,6,8,12,18,24,30].
Queda pendiente la demostración de la conjetura.