En la entrada anterior estudiamos la función que asigna a cada número entero positivo el máximo producto formado entre los sumandos de todas su particiones. Mediante recurrencia calculamos los valores de la función correspondiente, a la que llamamos MPP, pudiéndose formar tablas similares a la siguiente:
El objetivo de esta segunda entrada sobre el tema es demostrar que todos los valores de la función se calculan con una de estas tres expresiones: 3^n, 2*3^n, 4*3^n, de forma cíclica salvo el valor inicial 1.
Factores del producto máximo
Razonaremos a continuación que los valores de mpp(n) (n>4) solo poseen los factores 2 y 3. Todo se basa en que si un número N se descompone en dos sumandos a y b, el máximo producto a*b se produce en el interior del intervalo (1,N), debido a que la función x(N-x) presenta el máximo en N/2. Consecuencia de esto es que si una partición recibe un sumando nuevo para crear otra partición superior, ese sumando se puede ir descomponiendo en sumandos 1, 2 y 3, de forma que el producto aumente. Por ejemplo, si el nuevo sumando es 6, se puede sustituir por 3+3, cuyo producto es 9, superior al 6. Como el 6 es factor del producto, también lo será el 9, y el producto aumentará.
Con sumandos mayores se puede proceder de igual forma, Por ejemplo, el 10 se puede sustituir por 3+3+3+1, con lo que el producto final, en lugar de ser multiplicado por 10, lo hará en 27 (obsérvese que el 1 no interviene en el proceso).
Todos los valores del producto máximo presentarán la descomposición del tipo 2^p*3^q.
Concretemos algo más:
Caso 1: números del tipo 3k (múltiplos de 3)
Los primeros valores, según la tabla anterior, son: mpp(3)=3, mpp(6)=9, mpp(9)=27, es decir, las primeras potencias de 3. Si pasamos al valor 12, según el razonamiento de los párrafos anteriores, el producto máximo recibirá el factor 3, luego se dará que mpp(12)=3^4=81 y mpp(15)=3^5=243.
Si N=3*k, su función mpp(N)=3^k
Caso 2: Números del tipo 3k+2
Para ellos es inútil acudir al anterior 3k+1, pues el producto sólo perdería el factor 1 que no incrementa su valor, pero si acudimos al máximo de 3k=3^k, el nuevo factor máximo es el 2, y queda mpp(3k+2)=2*3^k.
Por ejemplo, mpp(8)=mpp(3*2+2)=2*3^2=18, como ya sabemos por la entrada anterior. Otro: mpp(14)=mpp(3*4+2)=2*3^4=162.
Si N=3*k+2, su función mpp(N)=2*3^k
Caso 3: Números del tipo 3k+1
Si acudimos al valor 3(k-1)+2, basta usar como nuevo sumando el 2 para ver que el máximo que buscamos es 4*3^(k-1).
Vemos algún ejemplo: mpp(13)=mpp(3*4+1)=4*3^(4-1)=4*27=108, como ya sabemos por casos anteriores. El valor de mpp(31) = mpp(3*10+1) = 4*3^9 = 4*19683 = 78732.
Lo hemos comprobado con la definición de función de la entrada anterior:
Si N=3*k+1, su función mpp(N)=4*3^(k-1)
Nueva definición de la función
Estas propiedades que acabamos de estudiar nos permiten simplificar mucho la definición de la función MPP. La presentamos en varias versiones para que las analices. La primera está construida con las funciones de Excel o Calc. Es esta, que la hemos copiado actuando sobre la celda D11:
=3^(ENTERO((D11)/3)-(RESIDUO(D11;3)=1))*2^RESIDUO(-D11;3)
Parece difícil. Intenta comprenderla. La primera parte decide a qué exponente elevaremos el 3, y la segunda el mismo problema para el 2. Para el primero hallamos el valor de k que acompaña al 3 y le restamos un 1 en el caso 3k+1. Para el segundo elegimos 1, 2 o 4 según el residuo respecto al 3, pero con signo menos. Ya, es complicado.
Con ella hemos construido esta tabla, para los números 40 a 45:
Código en Basic VBA:
Es quizás más fácil de entender la definición (segunda ya) de mpp en VBA. Como ya tenemos una versión, le llamaremos a esta MPP_2. Su desarrollo puede ser este:
Public Function mpp_2(n)
Dim k, m, p
k = Int(n / 3) ‘se determina el valor de k en n=3k+b
If n Mod 3 = 1 Then m = 1 Else m = 0 ‘si es múltiplo de 3, el exponente de 3 disminuye en 1
p = 3 ^ (k - m) ‘parte correspondiente al factor 3
m = 3 - n Mod 3: If m = 3 Then m = 0 ‘se prepara el exponent del 2
mpp_2 = p * 2 ^ m ‘se ensambla la función
End Function
Este código es más simple y rápido que el anterior. Hemos comprobado su equivalencia, y se demuestra aquí el poder simplificador del razonamiento matemático.
Para quienes entiendan el lenguaje PARI, copio aquí la solución de M. Somos:
mpp(n) = floor( 3^(n - 4 - (n - 4) \ 3 * 2) * 2^( -n%3))
Es muy parecida a la que proponemos.
Otra recurrencia
Si repasas la página http://oeis.org/A000792 que nos viene ayudando en este estudio, podrás leer más propiedades y fórmulas sobre estos productos máximos.
Una muy sencilla y curiosa es la de Ivan Neretin:
a(n) = a(n-1) + largest proper divisor of a(n-1), n > 2
En efecto, estudiamos los tres casos:
Si a(n-1)=3*k, sabemos que mpp(a(n-1))=3^k, y su mayor divisor propio md=3^(k-1). Sumamos y obtenemos mpp(a(n))=mpp(3*k+1)=3^k+3^(k-1)=4*3^(k-1), como ya sabemos.
Si a(n-1)=3*k+1, se tendrá: mpp(a(n-1))=4*3^(k-1), su mayor divisor propio md=2*3^(k-1). Sumamos: mpp(a(n))=mpp(3*k+2)=4*3^(k-1)+2*3^(k-1)=2*3^k, expresión ya conocida.
Si a(n-1)=3*k+2, mpp(a(n-1))=2*3^k, su mayor divisor propio md=3^k y al sumar obtenemos la esperada 3^(k+1).
Si dispones de la función en VBA de “mayor divisor”, en una columna de hoja de cálculo puedes engendrar la sucesión completa. En este blog disponemos de la función MAYORDIV (no la desarrollamos porque acude a otras más complicadas), lo que nos permite desarrollar la recurrencia:
Se ha adosado la recurrencia a la derecha de una tabla de MPP, para ver la equivalencia.
Si no dispones de la función MAYORDIV, puedes copiar la que sigue:
Public Function mayordiv(n)
Dim f, m
Dim es As Boolean
f = 2
m = 1
If n / 2 = n \ 2 Then es = True: m = 2 Else es = False
While f * f <= n And Not es
If n / f = n \ f Then es = True: m = f
f = f + 1
Wend
If m = 1 Then mayordiv = 1 Else mayordiv = n / m
End Function
No hay comentarios:
Publicar un comentario