IMO – Página 2 – Vestigium

I1M2012: Último dígito del producto de números de Fermat

PorJosé A. Alonso 20 noviembre 20128 marzo 2013

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de un problema propuesto para la Olimpiada Internacional de Matemáticas (IMO) de 1971. Su enunciado es

Sea $x_n = 2^{2^n} + 1$ y sea $m$ el producto de $x_2, x_3, \dots, x_{1971}$ . Calcular el último dígito de $m$ .

La primera definición es la traducción directa del enunciado

sol1 :: Integer
sol1 = ultimo (product [x n | n <- [2..1971]])

1 2	sol1 :: Integer sol1 = ultimo (product [x n \| n <- [2..1971]])

donde (x n) es el n-ésimo término de la sucesión

x :: Int -> Integer 
x n = 2^(2^n) + 1

1 2	x :: Int -> Integer x n = 2^(2^n) + 1

y (ultimo x) es el último dígito de x

ultimo :: Integer -> Integer
ultimo x = rem x 10

1 2	ultimo :: Integer -> Integer ultimo x = rem x 10

Aunque la primera solución es simple, tiene un inconveniente: Haskell no puede calcular números tan grandes. Una estrategia para resolverlo es considerar casos menores y buscar alguna regularidad. Para ello, generalizamos la primera solución sustituyendo 1971 por una variable.

sol2 :: Int -> Integer
sol2 a = ultimo (product [x n | n <- [2..a]])

1 2	sol2 :: Int -> Integer sol2 a = ultimo (product [x n \| n <- [2..a]])

Con la 2ª definición calculamos el último dígito de los primeros productos

ghci> [sol2 a | a <- [2..20]] 
[7,9,3,1,7,9,3,1,7,9,3,1,7,9,3,1,7,9,3]

1 2	ghci> [sol2 a \| a <- [2..20]] [7,9,3,1,7,9,3,1,7,9,3,1,7,9,3,1,7,9,3]

Se observa que el resultado está formado por la repetición de los números 7, 9, 3 y 1. A partir de la observación conjeturamos una nueva definición

sol3 :: Int -> Integer
sol3 a | b == 2 = 7
       | b == 3 = 9
       | b == 0 = 3
       | b == 1 = 1
       where b = rem a 4

sol3 :: Int -> Integer

sol3 a | b == 2 = 7

| b == 3 = 9

| b == 0 = 3

| b == 1 = 1

where b = rem a 4

Podemos comprobar, para pequeños valores, que las 2 definiciones son equivalentes

ghci> [sol2 a | a <- [2..20]] == [sol3 a | a <- [2..20]] 
True

1 2	ghci> [sol2 a \| a <- [2..20]] == [sol3 a \| a <- [2..20]] True

Además, con la 3ª definición se puede calcular la solución del problema original

ghci> sol3 1971
9

1 2	ghci> sol3 1971 9

es decir, el último dígito del producto $x_2x_3 \dots x_{1971}$ es 9.

Para justificar la solución, hay que demostrar que la definición sol3 es correcta; es decir, que los últimos dígitos de los productos forman la sucesión 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, 1, 7, 9, 3, … Para ello, observamos el último dígito de los $x_n$

ghci> [ultimo (x n) | n <- [2..20]]
[7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7]

1 2	ghci> [ultimo (x n) \| n <- [2..20]] [7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7]

Se observa que todos son 7. Esto justifica la sucesión de los productos, ya que cada término es el último dígito del producto del anterior por 7. Además, permite una nueva definición de la solución por recursión

sol4 :: Int -> Integer
sol4 a | a == 2    = 7
       | otherwise = ultimo (7 * sol4 (a-1))

sol4 :: Int -> Integer

sol4 a | a == 2 = 7

| otherwise = ultimo (7 * sol4 (a-1))

Podemos comprobar, para pequeños valores, que es equivalente a la anterior

ghci> [sol3 a | a <- [2..20]] == [sol4 a | a <- [2..20]] 
True

1 2	ghci> [sol3 a \| a <- [2..20]] == [sol4 a \| a <- [2..20]] True

Para terminar, sólo queda demostrar que si $n>1$ , entonces el último dígito de $2^{2^n} + 1$ es 7 o, equivalentemente, que el último dígito de $2^{2^n}$ es 6. Lo que se tiene ya que $2^{2^n} = 2^{2\cdot2^{n-1}} = (2^2)^{2^{n-1}} = 4^{2^{n-1}}$ . Además, como $n>1$ se tiene que $2^{n-1}$ es un número par mayor que 0 y, por tanto, el último dígito de $4^{2^{n-1}}$ es 6.

I1M2012: Potencias con el último dígito invariante

PorJosé A. Alonso 13 noviembre 20128 marzo 2013

En la segunda parte de la clase de hoy de Informática de 1º del Grado en Matemáticas hemos comentado la solución con Haskell de siguiente problema

Calcular el menor número natural n, mayor que 1, tal que para cualquier número entero x se verifique que x y xⁿ terminan en el mismo dígito.

La especificación matemática del enunciado es

min {n∈ℕ | n>1 ∧ ∀x∈ℤ (U(xⁿ) = U(x))}

donde U(x) es el último dígito de x. La especificación se puede reducir a

min {n∈ℕ | n>1 ∧ ∀x∈{0,…,9} (U(xⁿ) = U(x))}

Su traducción a Haskell es

solP3 :: Integer
solP3 = head [n | n <- [2..], 
                  and [ultimo (x^n) == ultimo x | x <- [0..9]]]

solP3 :: Integer

solP3 = head [n | n <- [2..],

and [ultimo (x^n) == ultimo x | x <- [0..9]]]

donde (ultimo x) es el último dígito de x

ultimo :: Integer -> Integer 
ultimo x = x `rem` 10

1 2	ultimo :: Integer -> Integer ultimo x = x `rem` 10

La solución del problema se calcula con

ghci> solP3
5

1 2	ghci> solP3 5

Se puede generalizar solP3 a una función solP3′ que calcula todos los números naturales n, mayores que 1, tales que para cualquier número entero x se verifique que x y xⁿ terminan en el mismo dígito. Para ello, basta eliminar head en la definición de solP3

solP3' :: [Integer]
solP3' = [n | n <- [2..], 
              and [ultimo (x^n) == ultimo x | x <- [0..9]]]

solP3' :: [Integer]

solP3' = [n | n <- [2..],

and [ultimo (x^n) == ultimo x | x <- [0..9]]]

El cálculo de los 20 primeros es

ghci> take 20 solP3'
[5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81]

1 2	ghci> take 20 solP3' [5,9,13,17,21,25,29,33,37,41,45,49,53,57,61,65,69,73,77,81]

Se observa que forman una progresión aritmética de diferencia 4. Basándonos en esta observación se puede redefinir solP3′ como sigue

solP3'' :: [Integer]
solP3'' = [5,9..]

1 2	solP3'' :: [Integer] solP3'' = [5,9..]

Se puede comprobar experimentalmente la conjetura definiendo la función comprobacion tal que (comprobacion n) se verifica si los n primeros elementos de solP3′ son los mismos que los de solP3”.

comprobacion :: Int -> Bool
comprobacion n = 
    take n solP3' == take n solP3''

comprobacion :: Int -> Bool

comprobacion n =

take n solP3' == take n solP3''

La comprobación para los 1000 primeros elementos es

ghci> comprobacion 1000
True

1 2	ghci> comprobacion 1000 True

Queda pendiente la demostración de la conjetura.

I1M2012: Números sin coprimos no primos

PorJosé A. Alonso 13 noviembre 20128 marzo 2013

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

solP2 :: [Integer]
solP2 = [n | n <- [1..1977], 
             and [primo m | m <- [2..n-1], gcd n m == 1]]

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

primo :: Integer -> Bool
primo n = factores n == [1,n]

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

factores :: Integer -> [Integer]
factores n = [m | m <- [1..n], n `rem` m == 0]

1 2	factores :: Integer -> [Integer] factores n = [m \| m <- [1..n], n `rem` m == 0]

La solución del problema se calcula con

ghci> solP2
[1,2,3,4,6,8,12,18,24,30]

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.

solP2' :: Integer -> [Integer]
solP2' x = [n | n <- [1..x], 
                and [primo m | m <- [2..n-1], gcd n m == 1]]

solP2' :: Integer -> [Integer]

solP2' x = [n | n <- [1..x],

and [primo m | m <- [2..n-1], gcd n m == 1]]

Por ejemplo,

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]

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.