Teorema de Hilbert-Waring
El problema de Waring, propuesto por Edward Waring consiste en déterminar si, para cada número entero k mayor que 1, existe un número n tal que todo entero positivo se puede escribir como una suma de k-potencias de números positivos con n sumandos como máximo.
La respuesta afirmativa al problema, aportada por David Hilbert, se conoce como el teorema de Hilbert-Waring. Su enunciado es
Para cada número entero k, con k ≥ 2, existe un entero positivo g(k) tal que todo entero positivo se puede expresar como una suma de a lo más g(k) k-ésimas potencias.
Definir las funciones
|
1 2 |
descomposiciones :: Integer -> Integer -> Integer -> [[Integer]] orden :: Integer -> Integer -> Integer |
tales que
- (descomposiciones x k n) es la lista de descomposiciones de x como suma de n potencias con exponente k de números enteros positivos.
|
1 2 3 4 5 6 7 |
descomposiciones 9 2 1 == [[9]] descomposiciones 9 3 1 == [] descomposiciones 9 3 2 == [[1,8]] descomposiciones 9 4 9 == [[1,1,1,1,1,1,1,1,1]] descomposiciones 25 2 2 == [[9,16]] descomposiciones 133 2 3 == [[8,125]] descomposiciones 38 3 2 == [[1,1,36],[4,9,25]] |
- (orden x k) es el menor número de sumandos necesario para expresar x como suma de k-ésimas potencias. Por ejemplo,
|
1 2 3 4 5 6 7 |
orden 9 2 == 1 orden 9 3 == 2 orden 9 4 == 9 orden 10 2 == 2 orden 10 3 == 3 orden 10 4 == 10 [maximum [orden x k | x <- [1..1000]] | k <- [1..6]] == [1,4,9,19,37,73] |
Comprobar el teorema de Hilbert-Waring para k hasta 7; es decir, para todo número x positivo se verifica que
|
1 2 3 4 5 6 |
orden x 2 <= 4 orden x 3 <= 9 orden x 4 <= 19 orden x 5 <= 37 orden x 6 <= 73 orden x 7 <= 143 |
y, en general,
|
1 |
orden x k <= 2^k + floor ((3/2)^k) - 2 |
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 |
import Test.QuickCheck descomposiciones :: Integer -> Integer -> Integer -> [[Integer]] descomposiciones x k n = sumas x (takeWhile (<= x) (potencias k)) n -- (potencias n) es la lista de las potencias de n -- take 7 (potencias 2) == [1,4,9,16,25,36,49] -- take 7 (potencias 3) == [1,8,27,64,125,216,343] potencias :: Integer -> [Integer] potencias n = map (^n) [1..] -- (sumas n ys x) es la lista de las descomposiciones de x como -- sumas de n sumandos de la lista creciente ys. Por ejemplo, -- sumas 3 [1,2] 2 == [[1,2]] -- sumas 4 [1,2] 2 == [[2,2]] -- sumas 5 [1,2] 2 == [] -- sumas 5 [1,2] 3 == [[1,2,2]] -- sumas 6 [1,2] 3 == [[2,2,2]] -- sumas 6 [1,2,5] 2 == [[1,5]] sumas :: Integer -> [Integer] -> Integer -> [[Integer]] sumas _ [] _ = [] sumas x ys 1 | x `elem` ys = [[x]] | otherwise = [] sumas x (y:ys) n | y > x = [] | otherwise = map (y:) (sumas (x-y) (y:ys) (n-1)) ++ sumas x ys n orden :: Integer -> Integer -> Integer orden x k = head [n | n <- [1..] , not (null (descomposiciones x k n))] -- El teorema es teorema_Hilbert_Waring :: Integer -> Integer -> Property teorema_Hilbert_Waring x k = x > 0 && k >= 2 ==> orden x 2 <= 4 && orden x 3 <= 9 && orden x 4 <= 19 && orden x 5 <= 37 && orden x 6 <= 73 && orden x 7 <= 143 && orden x k <= 2^k + floor ((3/2)^k) - 2 -- La comprobación es -- λ> quickCheck teorema_Hilbert_Waring -- +++ OK, passed 100 tests. |
Referencia
- Basado en Hilbert-Waring theorem de ProofWiki.
Pensamiento
¡Y en la tersa arena,
cerca de la mar,
tu carne rosa y morena,
súbitamente Guiomar!Antonio Machado