Las conjeturas de Catalan y de Pillai
La conjetura de Catalan, enunciada en 1844 por Eugène Charles Catalan y demostrada 2002 por Preda Mihăilescu1, afirma que
Las únicas dos potencias de números enteros consecutivos son 8 y 9 (que son respectivamente 2³ y 3²).
En otras palabras, la única solución entera de la ecuación
1 |
x^a - y^b = 1 |
para x, a, y, b > 1 es x = 3, a = 2, y = 2, b = 3.
La conjetura de Pillai, propuesta por S.S. Pillai en 1942, generaliza este resultado y es un problema abierto. Afirma que cada entero se puede escribir sólo un número finito de veces como una diferencia de dos potencias perfectas. En otras palabras, para todo entero positivo n, el conjunto de soluciones de
1 |
x^a - y^b = n |
para x, a, y, b > 1 es finito.
Por ejemplo, para n = 4, hay 3 soluciones
1 2 3 |
(2,3, 2,2) ya que 2³ - 2² = 8 - 4 = 4 (6,2, 2,5) ya que 6² - 2⁵ = 36 - 32 = 4 (5,3,11,2) ya que 5³ - 11² = 125 - 121 = 4 |
Las soluciones se pueden representar por la menor potencia (en el caso anterior, por 4, 32 y 121) ya que dado n (en el caso anterior es 4), la potencia mayor es la menor más n.
Definir las funciones
1 2 3 |
potenciasPerfectas :: [Integer] solucionesPillati :: Integer -> [Integer] solucionesPillatiAcotadas :: Integer -> Integer -> [Integer] |
tales que
- potenciasPerfectas es la lista de las potencias perfectas (es decir, de los números de la forma x^a con x y a mayores que 1). Por ejemplo,
1 2 |
take 10 potenciasPerfectas == [4,8,9,16,25,27,32,36,49,64] potenciasPerfectas !! 200 == 28224 |
- (solucionesPillati n) es la lista de las menores potencias de las soluciones de la ecuación de Pillati x^a – y^b = n; es decir, es la lista de los u tales que u y u+n son potencias perfectas. Por ejemplo,
1 2 3 |
take 3 (solucionesPillati 4) == [4,32,121] take 2 (solucionesPillati 5) == [4,27] take 4 (solucionesPillati 7) == [9,25,121,32761] |
- (solucionesPillatiAcotadas c n) es la lista de elementos de (solucionesPillati n) menores que n. Por ejemplo,
1 2 3 4 5 6 7 8 |
solucionesPillatiAcotadas (10^3) 1 == [8] solucionesPillatiAcotadas (10^3) 2 == [25] solucionesPillatiAcotadas (10^3) 3 == [125] solucionesPillatiAcotadas (10^3) 4 == [4,32,121] solucionesPillatiAcotadas (10^3) 5 == [4,27] solucionesPillatiAcotadas (10^3) 6 == [] solucionesPillatiAcotadas (10^3) 7 == [9,25,121] solucionesPillatiAcotadas (10^5) 7 == [9,25,121,32761] |
Soluciones
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
import Data.List (group) import Data.Numbers.Primes (primeFactors) -- Definiciones de potenciasPerfectas -- ================================== -- 1ª definición -- ------------- potenciasPerfectas1 :: [Integer] potenciasPerfectas1 = filter esPotenciaPerfecta [4..] -- (esPotenciaPerfecta x) se verifica si x es una potencia perfecta. Por -- ejemplo, -- esPotenciaPerfecta 36 == True -- esPotenciaPerfecta 72 == False esPotenciaPerfecta :: Integer -> Bool esPotenciaPerfecta = not . null. potenciasPerfectasDe -- (potenciasPerfectasDe x) es la lista de pares (a,b) tales que -- x = a^b. Por ejemplo, -- potenciasPerfectasDe 64 == [(2,6),(4,3),(8,2)] -- potenciasPerfectasDe 72 == [] potenciasPerfectasDe :: Integer -> [(Integer,Integer)] potenciasPerfectasDe n = [(m,k) | m <- takeWhile (\x -> x*x <= n) [2..] , k <- takeWhile (\x -> m^x <= n) [2..] , m^k == n] -- 2ª definición -- ------------- potenciasPerfectas2 :: [Integer] potenciasPerfectas2 = [x | x <- [4..], esPotenciaPerfecta2 x] -- (esPotenciaPerfecta2 x) se verifica si x es una potencia perfecta. Por -- ejemplo, -- esPotenciaPerfecta2 36 == True -- esPotenciaPerfecta2 72 == False esPotenciaPerfecta2 :: Integer -> Bool esPotenciaPerfecta2 x = mcd (exponentes x) > 1 -- (exponentes x) es la lista de los exponentes de l factorización prima -- de x. Por ejemplos, -- exponentes 36 == [2,2] -- exponentes 72 == [3,2] exponentes :: Integer -> [Int] exponentes x = [length ys | ys <- group (primeFactors x)] -- (mcd xs) es el máximo común divisor de la lista xs. Por ejemplo, -- mcd [4,6,10] == 2 -- mcd [4,5,10] == 1 mcd :: [Int] -> Int mcd = foldl1 gcd -- 3ª definición -- ------------- potenciasPerfectas3 :: [Integer] potenciasPerfectas3 = mezclaTodas potencias -- potencias es la lista las listas de potencias de todos los números -- mayores que 1 con exponentes mayores que 1. Por ejemplo, -- λ> map (take 3) (take 4 potencias) -- [[4,8,16],[9,27,81],[16,64,256],[25,125,625]] potencias :: [[Integer]] potencias = [[n^k | k <- [2..]] | n <- [2..]] -- (mezclaTodas xss) es la mezcla ordenada sin repeticiones de las -- listas ordenadas xss. Por ejemplo, -- take 7 (mezclaTodas potencias) == [4,8,9,16,25,27,32] mezclaTodas :: Ord a => [[a]] -> [a] mezclaTodas = foldr1 xmezcla where xmezcla (x:xs) ys = x : mezcla xs ys -- (mezcla xs ys) es la mezcla ordenada sin repeticiones de las -- listas ordenadas xs e ys. Por ejemplo, -- take 7 (mezcla [2,5..] [4,6..]) == [2,4,5,6,8,10,11] mezcla :: Ord a => [a] -> [a] -> [a] mezcla (x:xs) (y:ys) | x < y = x : mezcla xs (y:ys) | x == y = x : mezcla xs ys | x > y = y : mezcla (x:xs) ys -- Comparación de eficiencia -- ------------------------- -- λ> potenciasPerfectas1 !! 200 -- 28224 -- (7.24 secs, 9,245,991,160 bytes) -- λ> potenciasPerfectas2 !! 200 -- 28224 -- (0.30 secs, 814,597,152 bytes) -- λ> potenciasPerfectas3 !! 200 -- 28224 -- (0.01 secs, 7,061,120 bytes) -- En lo que sigue se usa la 3ª definición potenciasPerfectas :: [Integer] potenciasPerfectas = potenciasPerfectas3 -- Definición de solucionesPillati -- =============================== solucionesPillati :: Integer -> [Integer] solucionesPillati n = [x | x <- potenciasPerfectas , esPotenciaPerfecta2 (x+n)] -- Definición de solucionesPillatiAcotadas -- ======================================= solucionesPillatiAcotadas :: Integer -> Integer -> [Integer] solucionesPillatiAcotadas c n = [x | x <- takeWhile (< (c-n)) potenciasPerfectas , esPotenciaPerfecta2 (x+n)] |
Referencia
- Catalan’s conjecture en Wikipedia.
Pensamiento
Y te enviaré mi canción:
«Se canta lo que se pierde»,
con un papagayo verde
que la diga en tu balcón.Antonio Machado
Esta es una variante de la definición de «potenciasPerfectas» recurriendo a la librería «Math.NumberTheory.Powers.General». Para poder importarla, es necesario instalarla desde el símbolo del sistema con el nombre de «arithmoi».