Potencias con mismos finales
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)]
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)]
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)