Teorema de Liouville sobre listas CuCu
Una lista CuCu es una lista de números enteros positivos tales que la suma de sus Cubos es igual al Cuadrado de su suma. Por ejemplo, [1, 2, 3, 2, 4, 6] es una lista CuCu ya que
|
1 |
1³ + 2³ + 3³ + 2³ + 4³ + 6³ = (1 + 2 + 3 + 2 + 4 + 6)² |
La lista de Liouville correspondiente al número entero positivo n es la lista formada por el número de divisores de cada divisor de n. Por ejemplo, para el número 20 se tiene que sus divisores son
|
1 |
1, 2, 4, 5, 10, 20 |
puesto que el número de sus divisores es
- El 1 tiene 1 divisor (el 1 solamente).
- El 2 tiene 2 divisores (el 1 y el 2).
- El 4 tiene 3 divisores (el 1, el 2 y el 4).
- El 5 tiene 2 divisores (el 1 y el 5).
- El 10 tiene 4 divisores (el 1, el 2, el 5 y el 10).
- El 20 tiene 6 divisores (el 1, el 2, el 4, el 5, el 10 y el 20).
la lista de Liouville de 20 es [1, 2, 3, 2, 4, 6] que, como se comentó anteriormente, es una lista CuCu.
El teorema de Lioville afirma que todas las lista de Lioville son CuCu.
Definir las funciones
|
1 2 |
esCuCu :: [Integer] -> Bool liouville :: Integer -> [Integer] |
tales que
- (esCuCu xs) se verifica si la lista xs es CuCu; es decir, la suma de los cubos de sus elementos es igual al cuadrado de su suma. Por ejemplo,
|
1 2 3 |
esCuCu [1,2,3] == True esCuCu [1,2,3,2] == False esCuCu [1,2,3,2,4,6] == True |
- (liouville n) es la lista de Lioville correspondiente al número n. Por ejemplo,
|
1 2 3 |
liouville 20 == [1,2,3,2,4,6] liouville 60 == [1,2,2,3,2,4,4,6,4,6,8,12] length (liouville (product [1..25])) == 340032 |
Comprobar con QuickCheck
- que para todo entero positivo n, (liouville (2^n)) es la lista [1,2,3,…,n+1] y
- el teorema de Lioville; es decir, para todo entero positivo n, (liouville n) es una lista CuCu.
Nota: Este ejercicio está basado en Cómo generar conjuntos CuCu de Gaussianos.
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 |
import Data.List (genericLength, group, inits, sort) import Data.Numbers.Primes (primeFactors) import Test.QuickCheck esCuCu :: [Integer] -> Bool esCuCu xs = sum (map (^3) xs) == (sum xs)^2 -- 1ª definición de liouville -- ========================== liouville :: Integer -> [Integer] liouville n = map numeroDivisores (divisores n) -- (divisores x) es el conjunto de divisores de los x. Por ejemplo, -- divisores 30 == [1,2,3,5,6,10,15,30] divisores :: Integer -> [Integer] divisores n = [x | x <- [1..n], n `mod` x == 0] -- (numeroDivisores x) es el número de divisores de x. Por ejemplo, -- numeroDivisores 12 == 6 -- numeroDivisores 25 == 3 numeroDivisores :: Integer -> Integer numeroDivisores n = genericLength (divisores n) -- 2ª definición de liouville -- ============================ liouville2 :: Integer -> [Integer] liouville2 n = map numeroDivisores2 (divisores2 n) -- Se usan las funciones -- + divisores de "Conjunto de divisores" http://bit.ly/2OtbFIj -- + numeroDivisores de "Número de divisores" http://bit.ly/2DgVh74 -- (divisores2 x) es el conjunto de divisores de los x. Por ejemplo, -- divisores2 30 == [1,2,3,5,6,10,15,30] divisores2 :: Integer -> [Integer] divisores2 = sort . map (product . concat) . sequence . map inits . group . primeFactors -- (numeroDivisores2 x) es el número de divisores de x. Por ejemplo, -- numeroDivisores2 12 == 6 -- numeroDivisores2 25 == 3 numeroDivisores2 :: Integer -> Integer numeroDivisores2 = product . map ((+1) . genericLength) . group . primeFactors -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> length (liouville (product [1..11])) -- 540 -- (13.66 secs, 7,983,550,640 bytes) -- λ> length (liouville2 (product [1..11])) -- 540 -- (0.01 secs, 1,255,328 bytes) -- Propiedad -- ========= -- La propiedad es prop_Liouville :: Integer -> Property prop_Liouville n = n > 0 ==> liouville2 (2^n) == [1..n+1] -- La comprobación es -- λ> quickCheck prop_Liouville -- +++ OK, passed 100 tests. -- Teorema de Liouville -- ==================== -- La propiedad es teorema_Liouville :: Integer -> Property teorema_Liouville n = n > 0 ==> esCuCu (liouville n) -- La comprobación es -- λ> quickCheck teorema_Liouville -- +++ OK, passed 100 tests. |
Pensamiento
¡Oh, tarde viva y quieta
que opuso al panta rhei su nada corre.Antonio Machado