Raíces digitales de los números de Fermat.

Un comentario

1. Haskell

   -- Patrón: -- ====== -- -- Observamos que las raíces digitales de los números de Fermat siguen el -- siguiente patrón: -- λ> map raizDigital [2^(2^n) + 1 | n <- [0..20]] -- [3,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8] -- -- Denotemos por DF(n) la raíz digital del enésimo número de Fermat. Parece -- que DF(0) = 3 y a partir del 1 DF(n) = 5 si n es impar y DF(n) = 8 en caso -- contrario. Vamos a comprobar este comportamiento para n /= 0: -- + DF(n) = D(2^(2^n) + 1) = D(2^(2^n) + 1) = D(D(2^(2^n)) + D(1)) -- + D(2^(2^n)) = D(2^(mod (2^n) 6)) -- -- Para resolver la ecuación de congruencias 2^n = x mod 6 vamos a manipular un -- poco dicha expresión. -- + 2^n = x mod 6 <==> 6 | 2^n - x <==> 3 | 2^(n-1) - x/2 -- <==> 2^(n-1) = x/2 mod 3 -- -- Para hacer el paso anterior estamos asumiendo que x debe ser par, pues 2 -- divide tanto a 6 como a 2^n. Ahora podemos aplicar el Teorema pequeño de -- Fermat para p = 3, que afirma que dados dos números coprimos a y p, con p -- primo, se cumple que a^(p-1) = 1 mod p. -- + Si n es impar, 2^(n-1) tiene exponente par, luego se puede expresar -- como 2^(2k). De ello se deduce que 2^(n-1) = 1 mod 3 <==> x = 2. -- + Si n es par, 2^(n-1) tiene exponente impar, luego lo podemos reescribir -- como 2*2^(n-2). Entonces 2*2^(n-2) = 2 mod 3 <==> x = 4. -- -- Proseguimos ahora comprobando cuánto vale DF(n). -- + n impar ==> D(2^(2^n)) = D(2^2) = 4 ==> DF(n) = D(4 + 1) = 5 -- + n par ==> D(2^(2^n)) = D(2^4) = 7 ==> DF(n) = D(7 + 1) = 8 -- Definición: -- ========== raizDigitalFermat :: Integer -> Integer raizDigitalFermat n | n == 0 = 3 | odd n = 5 | otherwise = 8

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

   -- Patrón: -- ====== -- -- Observamos que las raíces digitales de los números de Fermat siguen el -- siguiente patrón: --    λ> map raizDigital [2^(2^n) + 1 | n <- [0..20]] --    [3,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8,5,8] -- -- Denotemos por DF(n) la raíz digital del enésimo número de Fermat. Parece -- que DF(0) = 3 y a partir del 1 DF(n) = 5 si n es impar y DF(n) = 8 en caso -- contrario. Vamos a comprobar este comportamiento para n /= 0: --    + DF(n) = D(2^(2^n) + 1) = D(2^(2^n) + 1) = D(D(2^(2^n)) + D(1)) --    + D(2^(2^n)) = D(2^(mod (2^n) 6)) -- -- Para resolver la ecuación de congruencias 2^n = x mod 6 vamos a manipular un -- poco dicha expresión. --    + 2^n = x mod 6 <==> 6 | 2^n - x <==> 3 | 2^(n-1) - x/2 --                    <==> 2^(n-1) = x/2 mod 3 -- -- Para hacer el paso anterior estamos asumiendo que x debe ser par, pues 2 -- divide tanto a 6 como a 2^n. Ahora podemos aplicar el Teorema pequeño de -- Fermat para p = 3, que afirma que dados dos números coprimos a y p, con p -- primo, se cumple que a^(p-1) = 1 mod p. --    + Si n es impar, 2^(n-1) tiene exponente par, luego se puede expresar --      como 2^(2k). De ello se deduce que 2^(n-1) = 1 mod 3 <==> x = 2. --    + Si n es par, 2^(n-1) tiene exponente impar, luego lo podemos reescribir --      como 2*2^(n-2). Entonces 2*2^(n-2) = 2 mod 3 <==> x = 4. -- -- Proseguimos ahora comprobando cuánto vale DF(n). --    + n impar ==> D(2^(2^n)) = D(2^2) = 4 ==> DF(n) = D(4 + 1) = 5 --    + n par ==> D(2^(2^n)) = D(2^4) = 7 ==> DF(n) = D(7 + 1) = 8   -- Definición: -- ==========   raizDigitalFermat :: Integer -> Integer raizDigitalFermat n   | n == 0    = 3   | odd n     = 5   | otherwise = 8

   Responder