miércoles, 23 de noviembre de 2016

Máximo producto en la partición de un número (2)


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

lunes, 14 de noviembre de 2016

Máximo producto en la partición de un número (1)


Ya sabemos que una partición de un número entero positivo N es una suma de números también enteros positivos cuyo resultado es ese número. Ya hemos tratado en este blog el tema de las particiones, y lo volveremos a desarrollar próximamente. Si no tienes claro el concepto puedes acudir a las direcciones

http://hojaynumeros.blogspot.com.es/2011/02/particiones-de-un-numero.html

https://es.wikipedia.org/wiki/Partici%C3%B3n_(teor%C3%ADa_de_n%C3%BAmeros)

Está muy estudiado el tema del desarrollo de las particiones y el del cálculo de su número. Aquí nos interesará el máximo producto que se puede lograr multiplicando los sumandos de cada partición. Lo introducimos con ejemplos:

Máximo producto logrado con particiones

Tomemos el número 6. Mentalmente se pueden escribir sus particiones (no se tiene en cuenta el orden): 6=5+1=4+2=3+3=4+1+1=… En cada partición calculamos el producto entre sumandos: 6, 5, 8, 9, 4,… y nos quedamos con el máximo. En el esquema lo verás mejor:



Figuran las once particiones del 6 y en la columna de la derecha los productos de sumandos. En la partición de sumando único lo elegimos como producto. Se observa que el máximo producto es 9. Como el resultado es único, constituye una función del número elegido, que podríamos escribir como MPP (Máximo Producto en Particiones) y se tendría que MPP(6)=9.

Otro ejemplo: En PARI las particiones se obtienen con la función partitions. Si pedimos las particiones del número 8 las obtenemos como vectores independientes:



Si multiplicas los sumandos dentro de cada vector descubrirás que el máximo producto es 18=2*3*3, luego MPP(8)=18

Estos resultados figuran en la página de OEIS http://oeis.org/A000792 con una definición recursiva que ya trataremos:

1, 1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 81, 108, 162, 243, 324, 486, 729, 972, 1458, 2187, 2916, 4374, 6561, 8748, 13122, 19683, 26244, 39366, 59049, 78732, 118098, 177147, 236196, 354294, 531441, 708588, 1062882, 1594323, 2125764, 3188646, 4782969,…

Como era de esperar, los valores son crecientes (cada uno es un máximo que se apoya en los anteriores) y pronto adquieren una buena tasa de crecimiento. La página citada contiene una fórmula recursiva que es fácil de entender.

a(n) = max{ (n-i)*a(i) : i<n}; a(0) = 1

Se define a(0) como 1, y también es fácil entender las siguientes: a(1)=1, a(2)=2, a(3)=3,… La recursividad tampoco es difícil de captar. Se trata de multiplicar cada valor menor que n por el máximo correspondiente a su diferencia con n. En efecto, las particiones de n se forman eligiendo esos valores i:1…n-1 para luego unirlos con las particiones de n-i. Por ejemplo, en las particiones del 7, si elegimos el valor 4, se deberá combinar con las particiones del 3 para formar las particiones del 7 que contengan un 4. Igual ocurre con todos los valores: 5 se añadirá a las particiones del 2 y 3 se unirá a las particiones de 4.

Si conservamos los valores máximos de cada partición de n-i, al multiplicarlos por i resultarán productos de la partición superior, candidatos a ser máximos. Al recorrer todos los valores menores que n dispondremos de n-1 posibles máximos, y uno de ellos será el MPP.

Algoritmo de construcción de la función MPP

Las ideas anteriores nos permitirán construir la función  MPP. En VBA de Excel se puede usar esta definición de función:

Public Function mpp(n)
Dim mx, i, m, j, mm
Dim a(50) ‘Está preparado para n<=50. Se puede ampliar a otro número

If n = 0 Or n = 1 Then mpp = 1: Exit Function
If n = 2 Then mpp = 2: Exit Function ‘Casos particulares
a(0) = 1: a(1) = 1: a(2) = 2: mx = 2
If n > 2 Then
For i = 1 To n ‘Se recorren los valores anteriores para la recursión
m = 1 ‘Valor provisional del máximo
For j = 1 To i
mm = j * a(i - j)
If m < mm Then m = mm ‘Se busca un máximo nuevo mediante los productos con los anteriores
Next j
mx = m: a(i) = m ‘Se incorpora el máximo a la lista
Next i
End If
mpp = mx ‘Máximo final
End Function

Con esta función podemos encontrar el máximo producto entre particiones de cualquier número. Si es mayor que 50 bastará cambiar la dimensión del vector de máximos. En la tabla siguiente hemos recogidos los valores de MPP para los números comprendidos entre 30 y 40:


Para quienes conozcan el lenguaje PARI (gratuito y muy recomendable para estos temas) se inserta un código para esta función, que también devuelve los valores entre 30 y 40:

mpp(n)=my(a=vector(50), m, mm, mx=2,mp=1);a[1]=1;a[2]=2;if(n<2,mp=1,if(n==2,mp=2,for(i=3,n,m=1;for(j=1,i, d=i-j;if(d>0,mm = j * a[d],mm=j);if(m<mm,m=mm));mx=m;a[i]=m));mp=mx;mp)
for(k=30,40,print1(mpp(k),", "))

Aquí tienes el resultado, que coincide con el de Excel:



Interpretación algebraica

Estos valores coinciden con los cardinales máximos de los subgrupos del grupo simétrico S(n). Usando la descomposición en ciclos se les puede dar un significado (ver http://hojaynumeros.blogspot.com.es/2013/10/ciclos-2-descomposicion-en-ciclos.html)

Por ejemplo, en el caso del 8 visto más arriba, mpp(8)=18, y puede dársele el significado de que es el cardinal máximo de un subgrupo propio del grupo de permutaciones de 8. En concreto, usando la descomposición en ciclos, podría ser G=(1,2)(3,4,5)(6,7,8) o cualquiera de sus isomorfos. En el caso del 6 es fácil ver que el subgrupo maximal es el GM=(1,2,3)(4,5,6), de cardinal 3*3=9, que es el valor de mpp(6).

Existe una forma directa y simple para calcular mpp(n), sin recurrencias ni algoritmos. Como es un cambio importante en el desarrollo que hemos llevado hasta ahora, lo dejamos para la próxima entrada.

jueves, 3 de noviembre de 2016

Conjetura de Rassias


Esta conjetura recibe el nombre de su autor, M. Th. Rassias, que la enunció siendo muy joven, mientras preparaba una Olimpiada Matemática. Se puede formular de varias formas, pero la que preferimos es la siguiente:

Para cada número primo p>2 existen dos primos p1 y p2, con p1<p2 tales que

(p-1)p1=p2+1

Es decir, que si el primer primo lo multiplicamos por p-1, conseguimos un número al que precede otro número primo. Por ejemplo:

Para el número 17, el par de primos puede ser 2 y 31, porque (17-1)*2=32=31+1. Para el primo 47 los primos pueden ser 3 y 137, porque (47-1)*3=138=137+1

La conjetura afirma que siempre se pueden encontrar esos dos primos para uno dado.

Obtención con hoja de cálculo

En teoría se podría comprobar esta conjetura mediante una tabla de doble entrada con los primeros números primos, pero sería un procedimiento costoso en espacio y tiempo. Es preferible acudir al VBASIC o lenguaje similar. En Excel puedes intentar una función que nos devuelva el más pequeño q de los dos primos, suficiente para comprobar la conjetura, ya que el otro lo podemos calcular mediante (p - 1) * q - 1

Public Function rassias(p)
Dim a, q

If Not esprimo(p) Then rassias = 0: Exit Function  ‘Si no es primo nos devuelve un cero
q = 2 ‘Posible valor del primo más pequeño
a = 0 ‘Si a=0 significa que aún no se han encontrado los primos
While a = 0
If esprimo((p - 1) * q - 1) Then ‘Prueba para saber que se encontraron los primos
a = q
End If
q = primprox(q) ‘Se prueba con el siguiente primo
Wend
rassias = a ‘Se encontró el primo menor
End Function

Las funciones ESPRIMO y PRIMPROX las puedes copiar desde nuestra entrada

http://hojaynumeros.blogspot.com.es/2012/04/proposito-de-ormiston.html

Con esta función y el cálculo posterior podemos construir una tabla en la que para cada número primo contenga los dos primos más pequeños que verifican la conjetura. Sería similar a esta:



Programa en PARI

Para quienes conozcan el lenguaje PARI, con este programa comprobamos la conjetura para los primos inferiores a 200:

p=2;while(p<200,p=nextprime(p+1);q=2;a=0;while(a==0,b=(p-1)*q-1;if(isprime(b),a=q);q=nextprime(q+1));print(p,", ",a,", ",b))

Resultado:



Con los cambios oportunos se puede lograr la comprobación para otros conjuntos de primos.

Otros puntos de vista

En la tabla anterior destaca la frecuencia con la que aparecen los valores 2 y 3 para el primo más pequeño. Es una indicación de que la conjetura no es algo complicado, sino que se comprueba fácilmente para valores pequeños. Podemos plantear una búsqueda para saber cuándo aparecerán otros valores, si es que lo hacen. Aquí tienes los resultados para la primera aparición de otros primos:



Esta tabla sugiere que la conjetura también se cumple para todo p1. El problema radica en que no hay tope en la búsqueda de p y de  p2 , por lo que de no cumplirse para algún valor, entraríamos en un bucle sin fin. No obstante, lo intentamos con esta función:

Public Function rassias2(p)
Dim q, b, a

If Not esprimo(p) Then rassias2 = 0: Exit Function
q = 2
a = 0
While a = 0
b = (q - 1) * p - 1
If esprimo(b) Then
a = b
End If
q = primprox(q)
Wend
rassias2 = a
End Function

Con ella vemos que a todo valor de  p1 le corresponde otro de  p2. No tienen que resultar los mismos valores anteriores, porque al cambiar el punto de vista se encuentran otros mínimos, pero lo importante es que existe siempre una solución.

Aquí tienes un resultado:



Por ejemplo, para 2081 como  p1, el valor de  p2 es 20809, calculado mediante p=11, ya que 20809=2081*10-1, y 20809 es primo.

No resistimos la elaboración de una función para p2:

Public Function rassias3(p)
Dim q, b, a

If Not esprimo(p) Then rassias3 = 0: Exit Function
q = 2
a = 0
While a = 0
b = (p + 1) / q + 1
If esprimo(b) Then
a = b
End If
q = primprox(q)
Wend
rassias3 = a
End Function

Con ella se puede construir una tabla que relaciones  p2 con  p1 y p:


Todas estas tablas se podrían prolongar hasta números mucho mayores, y siempre existe una solución de dos primos respecto al dado, luego se puede dar por comprobada la conjetura dentro de la herramienta que hemos usado.

Primos relacionados con uno fijo

Por último, nos podríamos plantear si para cada valor de p podemos encontrar infinitos pares  p1 y  p2 que cumplan la conjetura. Lo dejamos como ejercicio. En la tabla observamos pares de seis cifras que cumplen la conjetura para p=11:




Como los primos de la primera columna se multiplican por 10, los de la segunda terminan todos en 9. Este ejercicio lo podemos repetir para cualquier valor, y dentro del rango que deseemos. Terminamos con los primos de siete cifras que corresponden a p=137: