José A. AlonsoEl 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
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.
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,
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
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,
orden x k <= 2^k + floor ((3/2)^k) - 2 |
Soluciones
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