Menu Close

Diferencias de potencias congruentes con 5 módulo 7

El enunciado de un problema 5 de la Fase Local de la Olimpiada Matemática Española del 2012 es

Consideremos el número entero positivo n = 2^r - 16^s, donde r y s son también enteros positivos. Hallar las condiciones que deben cumplir r y s para que el resto de la división de n por 7 sea 5. Hallar el menor número que cumple esta condición.

Definir la lista

   exponentes :: [(Integer,Integer)]

tal que sus elementos son los pares de enteros positivos (r,s) tales que 2^r - 16^s es un número entero positivo cuyo resto al dividirlo por 7 es 5. Por ejemplo,

   head exponentes       ==  (10,2)
   exponentes !! 23      ==  (43,8)
   exponentes !! (10^7)  ==  (26836,1826)

Usando la función exponentes, calcular la respuesta a la pregunta del problema; es decir, hallar el menor número que cumple la condición.

Soluciones

import Test.QuickCheck (Property, (==>), quickCheck)
 
-- 1ª solución
-- ===========
 
exponentes :: [(Integer,Integer)]
exponentes =
  [(r,s) | (r,s) <- pares,
           let n = 2^r - 16^s,
           n > 0,
           n `mod` 7 == 5]
 
-- pares el lista de pares de enteros positivos con el primero mayor que
-- el segundo. Por ejemplo,
--    λ> take 10 pares
--    [(2,1),(3,1),(3,2),(4,1),(4,2),(4,3),(5,1),(5,2),(5,3),(5,4)]
pares :: [(Integer,Integer)]
pares = [(a,b) | a <- [1..]
               , b <- [1..a-1]]
 
-- 2ª solución
-- ===========
 
-- Observando los siguientes cálculos
--    λ> take 28 exponentes
--    [(10,2),(13,2),(16,2),(19,2),(22,2),(22,5),(25,2),(25,5),(28,2),
--     (28,5),(31,2),(31,5),(34,2),(34,5),(34,8),(37,2),(37,5),(37,8),
--     (40,2),(40,5),(40,8),(43,2),(43,5),(43,8),(46,2),(46,5),(46,8),
--     (46,11)]
--    λ> [((x-1) `div` 3, (y-2) `div` 3) | (x,y) <- it]
--    [(3,0),(4,0),(5,0),(6,0),(7,0),(7,1),(8,0),(8,1),(9,0),(9,1),
--     (10,0),(10,1),(11,0),(11,1),(11,2),(12,0),(12,1),(12,2),(13,0),
--     (13,1),(13,2),(14,0),(14,1),(14,2),(15,0),(15,1),(15,2),(15,3)]
 
exponentes2 :: [(Integer,Integer)]
exponentes2 =
  concat [[(r,s) | s <- takeWhile (<= (r `div` 4)) ys] | r <- xs]
  where xs = [10,13..]
        ys = [2,5..]
 
-- 3ª solución
-- ===========
 
exponentes3 :: [(Integer,Integer)]
exponentes3 = [(r,s) | r <- [1,4..], s <- [2,5..r `div` 4]]
 
-- Comprobación de equivalencia
-- ============================
 
-- La propiedad es
prop_exponentes :: Int -> Property
prop_exponentes n =
  n >= 0 ==>
  all (== (exponentes !! n))
      [exponentes2 !! n,
       exponentes3 !! n]
 
-- La comprobación es
--    λ> quickCheck prop_exponentes
--    +++ OK, passed 100 tests.
 
-- Comparación de eficiencia
-- =========================
 
-- La comparación es
--    λ> exponentes !! (3*10^4)
--    (1471,332)
--    (5.21 secs, 7,844,582,216 bytes)
--    λ> exponentes2 !! (3*10^4)
--    (1471,332)
--    (0.04 secs, 6,551,432 bytes)
--    λ> exponentes3 !! (3*10^4)
--    (1471,332)
--    (0.01 secs, 5,512,056 bytes)
--
--    λ> exponentes2 !! (10^7)
--    (26836,1826)
--    (3.25 secs, 2,083,815,616 bytes)
--    λ> exponentes3 !! (10^7)
--    (26836,1826)
--    (2.57 secs, 1,757,467,216 bytes)
 
-- Cálculo de la respuesta
-- =======================
 
-- El cálculo es
--    λ> (r,s) = head exponentes
--    λ> 2^r - 16^s
--    768
-- Por tanto, el número pedido es el 768.

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>

2 soluciones de “Diferencias de potencias congruentes con 5 módulo 7

  1. Rubén Muñoz Mkrtchian
    -- Condición inicial:
    -- =================
    --
    -- El número n = 2^r - 16^s debe ser un número entero positivo. En definitiva,
    -- buscamos pares (r,s) tales que 2^r > 16^s = 2^(4s). Así pues, se tiene que
    -- r > 4s o, dicho de otra forma, s puede valer como mucho r/4.
    --
    -- Búsqueda de los pares:
    -- =====================
    --
    -- Vamos a tomar clases de equivalencia en Z modulo 7 para así hacer más fácil
    -- los cálculos.
    --
    --    2^r - 16^s = 5 mod 7
    --    2^r - 2^s = -2 mod 7
    --    2^r = -2 + 2^s mod 7
    --
    -- Dado que 2 y 7 son coprimos, sabemos por el pequeño teorema de Fermat que
    -- 2^6 = 1 mod 7. Distinguimos seis casos y estudiamos para dichos valores de r
    -- si existe algún s tal que se cumpla la ecuación.
    --
    --    + Caso 1: r = 6k
    --        2^(6k) = 1 mod 7
    --        2^s = 1 + 2 = 3 mod 7
    --        No hay solución.
    --
    --    + Caso 2: r = 6k + 1
    --        2^(6k + 1) = 2 mod 7
    --        2^s = 2 + 2 = 4 mod 7
    --        s = 3t + 2
    --
    --    + Caso 3: r = 6k + 2
    --        2^(6k + 2) = 1 mod 7
    --        2^s = 4 + 2 = 6 mod 7
    --        No hay solución.
    --
    --    + Caso 4: r = 6k + 3
    --        2^(6k + 3) = 1 mod 7
    --        2^s = 8 + 2 = 3 mod 7
    --        No hay solución.
    --
    --    + Caso 5: r = 6k + 4
    --        2^(6k + 4) = 1 mod 7
    --        2^s = 16 + 2 = 4 mod 7
    --        s = 3t + 2
    --
    --    + Caso 6: r = 6k + 5
    --        2^(6k + 5) = 1 mod 7
    --        2^s = 32 + 2 = 6 mod 7
    --        No hay solución.
    --
    -- Definición:
    -- ==========
    --
    -- La información que tenemos hasta ahora para así poder definir nuestra
    -- función es la siguiente:
    --    + s debe valer como mucho r/4.
    --    + Para r = 3k + 1, los valores s = 3t + 2 son solución de la ecuación.
     
    exponentes :: [(Integer,Integer)]
    exponentes = [(r,s) | r <- [1,4..], s <- [2,5..div r 4]]
     
    -- La función definida es capaz de calcular el último ejemplo.
    --    λ> exponentes !! (10^7)
    --    (26836,1826)
    --    (4.83 secs, 1,762,855,864 bytes)
  2. j0sejuan

    Puede ser divertido establecer una biyección para obtener directamente cualquier tupla:

    {-
     
      Rubén indica que debe ser
     
        r = 3k + 1
        s = 3t + 2
     
        r > 4s
     
      por tanto
     
        t = (3k - 7) / 12
        k = 3..
     
      para cada k=3.. el último `t` válido es
     
        0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, ...
            z=0         z=1         z=2         z=3
     
      y el nº de `k` hasta ese `z` incluido son (la posición en la lista es) -}
     
    posFromZ z = 2 * z * (z + 1)    {-
     
      es decir, la tupla n-ésima tiene por `z` -}
     
    zFromPos n = (integerSquareRoot(2 * n + 1) - 1) `div` 2   {-
     
      el grupo z-ésimo contiene cuatro `k` con las mismas `t` luego
      la tupla p-ésima es:  -}
     
    tupla p = let z = zFromPos p
                  b = posFromZ z
                  (k, t) = (p - b) `divMod` (z + 1)
              in  (3 * (4 * z + k + 3) + 1, 3 * t + 2)
     
     
     
     
     
    {-
     
    *Main> all (n -> (exponentes!!n) == tupla (toInteger n)) [0..100000]
    True
     
     
    *Main> and [ tupla 0       ==  (10,2)
               , tupla 23      ==  (43,8)
               , tupla (10^7)  ==  (26836,1826) ]
    True
    (0.02 secs, 151,664 bytes)
     
     
    *Main> length . show . fst . tupla $ 10^(10^7)
    5000001
    (6.21 secs, 488,108,072 bytes)
     
    -}

Leave a Reply

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