Menu Close

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)

Nuevas soluciones

  • En los comentarios se pueden escribir nuevas soluciones.
  • El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>

Una solución de “Potencias con mismos finales

  1. Joaquín Infante Rodríguez
    import Data.List
     
    potenciasMismoFinales :: Integer -> [(Integer,Integer)]
    potenciasMismoFinales x = [(m,n) | n<-[1..], m<-[1..n-1],
                                       take 3 (reverse (digitos (x^m)))
                                    == take 3 (reverse (digitos (x^n)))]
     
    digitos :: Integer -> [Integer]
    digitos n = [read [x] | x<-show n]
     
     
    -- λ> head (potenciasMismoFinales 1978) == (3,103) (0.40 secs, 409,509,768 bytes)

Leave a Reply

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.